阅读本文前，请先点击“关注”，方便您随时获取系列优质文章，方便讨论分享，谢谢支持~
文本 | 3月10日
编辑|
介绍
基于格的密码学的多功能性使其成为基于标准安全假设（例如因式分解和离散对数）的密码学的有希望的潜在替代方案。
但是在格成为数论方案的可行替代方案之前，必须拥有基于格的有效构造，以用于实际应用的最通用的密码原语，可以说是加密方案和数字签名。
对于合理的安全参数，后一种方案给出的签名长度约为 60,000 位，这更接近实际情况，但仍然不像人们希望的那么小。
随后，人们也构造了不采用随机预言机的基于格的签名方案[,Boy10]，但它们在实践中的效率远低于使用随机预言机的类似方案。
一、相关工作与成果
无论是使用散列和签名还是 Fiat 技术，随机预言模型中数字签名构建的共同主线都是强制签名的分布在统计上独立于密钥。
如果实现了这个特性，那么通过编程随机预言机，人们可以在不知道密钥的情况下，以较低的安全性生成潜在伪造者请求的有效签名。
然后，当伪造者为新消息生成签名时，它可用于解决底层难题。在格的情况下，底层难题通常是小整数解 (SIS) 问题，其中给定一个矩阵 A，并要求找到一个小向量 v，使得 Av = 0 mod q。
签名方案也非常简单，不需要在任意网格上进行预图像采样。我们所做的只是从 Zm 上的正态分布中采样，计算向量矩阵乘积，进行随机查询，计算另一个向量矩阵乘积（这次向量是稀疏的），然后拒绝样本。
事实上，在线/离线设置中，我们可以在接收要签名的消息之前进行预先计算，在线阶段仅包括进行一些向量加法（因为矩阵乘法是稀疏向量）和拒绝采样。
2. 初步
1. 符号
我们假设 q 是一个小的（即多项式大小的）素数，并且 Zq 中的元素由 -2 范围内的整数表示。我们将用粗体字母表示向量，用粗体大写字母表示矩阵。我们假设所有向量都是向量 v 的范数。
列向量 v 表示向量 v 的转置，记为 vp。我们通常避免将 p 写为 2 范数。每当我们处理 Zq 中的元素时，我们总是明确假设涉及它们的所有操作都是规范化的。模 q 结束。因此，对于矩阵 A ∈ Z 和向量 s ∈ Z 的乘积。
2. 数字签名
签名方案由一个三元组的多项式时间（可能是概率的）算法（G，S，V）组成，使得对于 G（1n）的每对输出（s，v）和任何 n 位消息 m。
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 的内积的绝对值，并说如果绝对值最多为 q/ 4，则 (A, t) 来自 SISq,n,m,d 分布，否则，它说 (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 来设置参数。
IV. 拒绝抽样和正态分布
在 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 在区分真实签名方案和混合 1 时最多具有 s(h + s)2−n+1 的优势。真实签名算法和混合 1 中的算法之间的唯一区别在于 1。
随机预言机H的输出是从{v : v ∈ {−1, 0, 1} v1 ≤κ}中随机选择的，然后编程为H(Az−Tc,µ)=H(Ay,µ)，而不检查(Ay,µ)的值是否已经设置。由于D调用H h次，签名算法调用s次，因此最多会设置s+h个(Ay,µ)的值。
我们现在证明，每次调用该过程时，生成 ay 且 Ay 等于之前查询的值之一的概率最多为 2 − n + 1。以至少 1 − e −Ω(n) 的概率，矩阵 A 可以写成“范式”，即 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ησ√ m。
2.基于低密度SIS和LWE的签名
这打破了 m ≈ 64 + n · log q/ log (2d + 1) 的要求（这是引理 5.2 所要求的），并且表明这仍然为我们提供了一个可证明安全的签名方案（基于 SISq,n,m,d 问题的事实），但签名和密钥的大小要小得多。
而由于 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, David Cash, Chris, 和 Amit Sahai，通过硬学习问题实现快速密码原语和循环安全加密，中文，2009。
2. Mihir 和 Neven，《多重签名和通用公钥模型中的一般分叉引理》，ACM 计算机和通信安全会议，2006 年。
3. 和 Chris 。基于 LWE 的加密的更佳密钥大小（和攻击），CT-RSA，2011 年。
4. Oded Regev。基于格的密码学。J. Regev、J. Regev 和 Erik Regev 编，后量子密码学章节。-，2008 年。
5. Chris 。最坏情况下最短向量问题的公钥密码系统：扩展摘要。STOC，2009 年。