阅读此文前，诚邀您点击一下“关注”，方便您随时查阅一系列优质文章，同时便于进行讨论与分享，感谢您的支持~

文|三月十

编辑|hshdhdjehd

引言

基于格的密码学的多功能性使其成为基于标准安全假设（如因式分解和离散日志）的密码学的有前途的潜在替代方案。

但在格能够成为数论方案的可行替代品之前，在实际应用中拥有最普遍的密码原语的有效的基于格的构造是至关重要的，这些原语可以说是加密方案和数字签名。

对于合理的安全参数，后一种方案的签名长度约为 60000 位，虽然更接近实用，但仍然没有人们想要的那么小。

随后，还构建了不带随机预言机的基于格的签名方案 [CHKP10,Boy10]，但它们在实践中的效率都远低于使用随机预言机的同类方案。

一、相关工作和结果

无论是使用散列和签名还是 Fiat‑Shamir 技术，在随机预言机模型中贯穿数字签名构造的一个共同主线是强制签名的分布在统计上独立于密钥。

如果实现此属性，则通过对随机预言机进行编程，人们可以希望在不知道密钥的情况下，在安全性降低中生成潜在伪造者所请求的有效签名。

然后，当伪造者生成新消息的签名时，它可以用来解决底层的难题。在格的情况下，潜在的难题通常是小整数解 (SIS) 问题，其中给定矩阵 A 并要求找到一个小向量 v，使得 Av = 0 mod q。

签名方案也非常简单，不需要在任意格子上进行图像前采样。我们所做的就是对 Zm 上的正态分布进行采样，计算向量矩阵乘积，进行随机 oracle 查询，计算另一个向量矩阵乘积（这次向量是稀疏的），然后拒绝样本。

事实上，在在线/离线设置中，我们可以在收到要签名的消息之前进行预计算，在线阶段仅包括进行一些向量加法（因为矩阵乘以稀疏向量）和拒绝采样。

二、预赛

1.符号

我们将假设 q 是一个小的（即多项式大小的）素数，并且Zq中的元素由 − 2范围内的整数表示。我们将用粗体字母表示向量，用粗体大写字母表示矩阵。我们假设所有向量都是向量 v 的范数。

列向量，v 表示向量 v 的转置，用vp 表示，我们通常会避免将 p 写为2范数，每当处理Zq 中的元素时，我们总是明确地假设涉及它们的所有操作都以归约模 q 结束。因此对于矩阵 A ∈ Z 和向量 s ∈ Z 的乘积。

2.数字签名

签名方案由多项式时间（可能是概率）算法（G，S，V）的三元组组成，使得对于 G（1n ）和任何 n 位消息 m的每对输出（s，v）。

三、SIS 问题及其变体

在本节中，我们将定义我们的签名方案将基于其安全性的平均情况问题。所有这些问题都属于小整数解 (SIS) 问题的范畴，本质上是 Z 中元素的背包问题。

为了使上述问题不至于空难，我们需要有 β ≥ √ mqn/m才能存在解 v。

1.SIS 变体之间的关系

由于 v ≤ β 且 s 的所有系数至多为 d，因此我们有|v1, t| ≤ βd√ m ≤ q/4。如果 t 是一致随机的，那么v1, t 在Zq中也将是一致随机的。

因此， SISq,n,m,d决策问题的区分器仅查看v1和 t的内积的绝对值，并表示 (A, t) 来自SISq,n,m,d分布，如果绝对value 最多为 q/4，他说 (A, t) 是一致的，否则。

在(A,t)来自SISq,n,m,d分布的情况下，区分器永远是正确的，而在均匀分布的情况下，他会以1/2的概率出错。

SIS所属的背包问题的计算难度自20世纪80年代初就开始研究，解决背包问题随机实例的主要技术是晶格约简。基本思想是定义格子L(A)={v∈Z:Av=0}，然后使用格子缩减算法在L(A)中找到短向量。

其中δ是取决于β的参数≤δm所使用的晶格缩减算法的质量。目前最好的算法的因子δ在1.01左右，据推测，在可预见的未来，1.007的因子可能是我们无法企及的。我们使用值δ=1.007来设置参数。

四、拒绝抽样与正态分布

R m上以 v 为中心的具有标准差的连续正态分布， 只是制作所需的缩放量，将函数转化为概率分布。还要注意，对于所有 v ∈ Z m, ρ，因此比例因子对于所有 v 都是相同的。

我们将证明关于 Z m 上的离散正态分布的几个事实。第一个引理限制了离散正态变量与 R m 中任何向量的内积。

其中最后一个不等式。我们现在继续通过应用马尔可夫不等式和上述结果来证明引理的主张。特别地，对于任何 t > 0，我们有：

1.基于SIS的签名方案

在本节中，我们将展示我们的主要理论结果，随机预言机模型中，基于2‑SISq,n,m,β问题的平均案例难度的签名方案，其中 β = O~(n)。其参数的定义和一些示例实例如图 所示。我们现在将解释该方案的工作原理并概述其安全性的直觉。

这种签名算法结构背后的主要思想是使签名 (z, c) 的分布独立于密钥 S。我们将针对的 z 的目标分布是 Dm，但元素z在签名方案来自分布Dm ，其中 v = Sc。

以表明对于适当选择的 M 和 σ 值，签名算法将输出概率约为 1/M 的内容及其输出之间的统计距离在统计上接近于从Dm中选择 z 的分布。

一旦我们将签名的分布与密钥的分布分离，我们就可以使用成功破解签名的伪造者来解决2‑SISq,n,m,β问题，因为 β ≈ O~(z)。

我们首先证明区分器 D 最多具有 s(h + s)2−n+1的优势来区分真实签名方案和混合 1。实际签名算法与混合 1 中的算法之间的唯一区别是在 Hybrid 1 中。

随机预言 H 的输出是从 {v : v ∈ {−1, 0, 1} v1 ≤ κ}中随机选择的，然后编程为 H( Az − Tc, µ) = H(Ay, µ) 而不检查 (Ay, µ) 的值是否已经设置。由于 D 调用 H h 次，而签名算法调用 s 次，因此最多会设置 (Ay, µ) 的 s + h 值。

我们现在表明，每次调用 Hybrid 1 过程时，生成 ay 且 Ay 等于先前查询的值之一的概率最多为 2 − n +1。概率至少为 1 − e −Ω(n)时，矩阵 A 可以写成“Hermite 范式”，即 A = [A¯ ||I]。

假设签名者在签署消息 µ 时对随机预言机 H ((Az − Tc), µ ) = c 进行了编程。如果伪造者为某些（可能不同的）消息 µ 输出有效伪造 (z, c)，则我们有 H ((Az − Tc), µ ) = H ((Az − Tc), µ)。

如果 µ = µ 或 Az − Tc = Az− Tc，则意味着 F 找到了rj的原像。因此，我们有 µ = µ 和 Az − Tc = Az− Tc，因此 A(z−z ) = 0。

我们知道 z − z = 0（否则 (z, µ) 与旧签名 (z , µ ) 完全相同），并且由于 z, z ≤ ησ√ m，我们有 z − z ≤ 2ησ√米。

2.基于低密度 SIS 和 LWE 的签名

打破 m ≈ 64 + n · log q/ log (2d + 1)（这是引理 5.2 所要求的）要求的结果，并表明这仍然为我们提供了一个可证明安全的签名方案（基于在低密度SISq,n,m,d问题上），但签名和密钥大小要小得多。

并且由于Hybrid 2不使用秘钥来产生签名，对于给定的A，我们可以在实际签名中使用系数小的秘钥S，但是使用系数大的S（所以存在一个S使得AS = AS) 在证明中。

如果验证密钥 (A, AS) 的分布在计算上与 (A, AS ) 的分布无法区分（并且基于定义 3.4 中低密度 SISq,n,m,d 问题的难度） ，辨别器将无法判断他获得了无效的密钥对。

并且由于在引理 5.4 中我们从不使用密钥向伪造者提供签名，伪造者应该以同样的方式行事，并且我们将能够找到一个非零 v 使得 Av = 0。

结语

一般来说，基于 SIS 和 LWE 问题的密码方案往往具有非常大的密钥大小，在我们的例子中，原因是矩阵 S 和 T 具有相当大的维度和矩阵中的每个条目都独立于其他条目。减小密钥大小的一种方法是使所有矩阵都不是独立的。

考虑按如下方式构造矩阵 A ∈ Z：从 Z 中随机均匀地选取其第一列a0 ，然后让接下来的 n − 1 列a1, . . . , an−1是n 次单变量多项式 f(x) 的环 Zq[x]/f 中q的系数表示。

然后随机选择 A 的第n + 1列，然后以与上述相同的方式填充接下来的 n‑1 列（为简单起见，假设 m 是 n 的整数倍）。请注意，对于 A 的这种构造，As 等效于环Zq[x]/f 中的多项式乘法和加法。

参考文献：

1、Benny Applebaum、David Cash、Chris Peikert 和 Amit Sahai，快速加密原语和基于硬学习问题的循环安全加密， CRYPTO 中，，2009 年。

2、Mihir Bellare 和 Gregory Neven，普通公钥模型中的多重签名和一般分叉引理，在 ACM 计算机和通信安全会议上，2006 年。

3、理查德·林德纳 (Richard Lindner) 和克里斯·佩克特 (Chris Peikert)。基于 lwe 的加密的更好的密钥大小（和攻击），在 CT‑RSA 中，2011 年。

4、Daniele Micciancio 和 Oded Regev。基于格的密码学，在 Daniel J. Bernstein、Johannes Buchmann 和 Erik Dahmen 的编辑中，后量子密码学章节，施普林格出版社，2008 年。

5、克里斯佩克特。来自最坏情况最短向量问题的公钥密码系统：扩展摘要，在 STOC，2009 年。