阅读此文前，诚邀您点击一下“ 关注 ”，方便您随时查阅一系列优质文章，同时便于进行讨论与分享，感谢您的支持~
文|三月十
编辑|hshdhdjehd
引言
格密码学的一个吸引人的特征是可以构造密码原语，其安全性基于最坏情况格问题的难度[Ajt96]。更具体地说，平均案例问题（例如SIS和LWE）的定义方式是，可以使用能够解决这些问题的对手在任何格中找到短向量。
虽然从最坏情况到平均情况的减少并不能帮助我们找出使SIS和LWE变得困难的确切参数设置， 但它们绝对值得称赞，因为它们引领研究人员正确定义了这些问题。
近年来出现了很多基于SIS和LWE构建的密码协议。然而，这些方案并不是特别有效，因为SIS和LWE固有地产生密钥大小和/或在安全参数λ中为O~(λ2 )的输出。出于这个原因，几乎所有实用的基于格的构造都建立在平均案例问题Ring‑SIS和Ring‑LWE之上。
Ring‑SIS和Ring‑LWE问题的代数结构是Zq[x]/f形式的多项式环，在[PR06,LM06,SSTX09,LPR13]中显示， 在这个环上求解RingSIS和Ring‑LWE意味着在Z[x]/f的所有理想中找到短向量。
一、构建数字签名
构建数字签名方案的直觉是让公钥是随机多项式,在有界度n−1的Zq[x]中的ak ,和t=aisi其中所有操作都在Zq[x]上执行。我们希望选择si使得它们的度数d略小于n，并且还使得定义为f(s1, . . . ,sk)=aisi的函数f是压缩的。
然后，我们可以为来自[Lyu09 ,Lyu12 ]的Σ‑协议采用“Fiat‑ShamirwithAborts”技术来创建一个独立于si并满足与t和Σ‑协议的“提交”和“挑战”步骤。
然后可以证明，可以使用能够破坏数字方案不可伪造安全属性的对手来提取范数较小的多项式z1, . . . ,zk和c在Zq[x]上满足方程aizi=tc 。
然后，我们证明 满足多项式zi 、c以及用于构造t的多项式si的系数大小和次数的特定条件的该方程的解， 意味着对于任何f的f‑SIS问题的解其度数在d+deg(c)和n之间。
1.讨论和未解决的问题
虽然我们的方案在安全参数中具有大小为O~(λ)的密钥和密文，就像基于Ring‑SIS和Ring‑LWE问题的签名方案一样，具体实例比那些更糟糕最实用的方案。与BLISS[DDLL13]相比，密钥大约大20倍，公钥大10倍，签名大约大30倍。
二、预赛
1.符号
R将表示多项式环Zq[x]。 我们还将假设所有多项式运算都发生在这个环中（因此我们不会写modq，因为它是隐式的元素。
多项式a∈R具有有限次deg(a)，我们将a∞表示为max|ai|和a1是deg( a)−1 ，是多项式a∈R<n且a∞≤i。对于多项式a∈R和n次一元多项式f，表达式amodf表示R<n中的唯一多项式a，其中存在r∈Zq[x]使得a+rf=a。
Z[x]中的n−1次多项式与Zn中的向量之间存在自然映射，它简单地将多项式的每个系数映射到向量坐标。
2.格问题
设Λ是对应于多项式环Z[x]/f中的理想的格，并且γ≥1是一些实数。f‑SVPγ(Λ)问题要求找到一个元素v∈Λ使得v∞≤γ·min(w∞)，w∈Λ\{0}。
主要结果是将Z[x]/f中所有格子的f‑SVPγ问题的难度与f‑SISK,q,β问题联系起来。 如果元素的长度是由简单地查看最大系数的函数定义的，那么缩减的质量就依赖于f的某个属性，该属性被称为“扩展因子”。这个扩展因子解释了Z[x]中多项式的系数在减少模f时增长了多少。
对于任何不可约（整数）f和q>2θfβkn1.5logn，如果有一个多项式时间算法以一些不可忽略的概率解决f‑SISK,q,β问题，则有一个多项式时间算法可以解决f‑SVPγ问题，其中γ=8θfβknlog2n对于对应于Z[x]/f中的理想的任何格子Λ。
3.离散正态（高斯）分布
Rm上以v为中心的具有标准差的连续正态分布， Zm上的离散正态分布以某个v∈Zm为中心，具有标准偏差。
令V为Z的子集， 其中所有元素的范数均小于T，σ定义为11·T，h :V→R为概率分布。那么概率如下算法：
4.数字签名定义，签名方案由多
项式时间（可能是概率）算法（G，S，V）的三元组组成，使得对于G（1n）的每对输出（s，v）和任何n位消息m，Pr[V(v,m,S(s,m))=1]=1。
其中概率取代了算法S和V的随机性， G称为密钥生成算法，S是签名算法，V是验证算法，s和v分别是签名和验证密钥。
签名方案(G,S,V )被认为是安全的，如果对于每个多项式时间（可能是随机的）伪造F，在看到公钥和{(µ1,S(s,µ1)) , . . . ,(µq,S(s,µq))}对于它选择的任何q消息µi（其中q是n的多项式），F可以产生(µ=µi ,σ)使得V(v,µ,σ)=1，小到可以忽略不计。
一旦我们生成了系数bm−j到bm，我们就完全确定了乘积的系数cm+n−j到cm+n 。我们现在可以通过归纳来证明引理的主张。系数cm+n=bm，因此是均匀随机的模q。
现在假我们已经选择了 系数bm−k到bm，因此完全确定了cm+n−j到cm+n的系数， 并且它们联合均匀随机模q。一旦我们选择了系数bm−j−1，我们将有：
三、签名方案
我们现在通过密钥生成、公钥生成、签名和验证算法正式描述我们的方案，我们方案中的固定公共参数如下所述。值n、k、q、s、d1、d2、c直观地与R<n‑SIS问题的参数化相关，标准差σ与参数β相关。
我们进一步定义了一个 密码函数H，其范围是集合C，它由具有小的有界多项式组成。
为了生成µ的签名，签名者从特定分布中选择“屏蔽”变量yi ，计算c=H(aiyi ,µ)，然后创建zi=sic+yi 。通过设置参数的方式，每个zi都在R<d2中。因此，可以将k个向量z=(z1| . . .|zk)的串联视为Zkd2中的一个向量。
如果我们类似地定义向量s=(s1c| . . . . ,skc)∈Zkd2，那么我们可以看到 向量z是按照离散高斯分布分布的Dkd2摆脱对s的依赖， 我们使用拒绝抽样通过运行算法从[Lyu12]中提取过程。
通过设置参数的方式，有1/3的概率输出签名，有2/3的概率需要重新启动签名程序，一些(z1, . . . ,zk)最终通过拒绝抽样程序后，其分布恰好为Dkd2因为该分布是从Zkn中抽样的，它是一个正交格，所以zi的每个系数都按照D1进行分布。
1.安全
假设随机预言机H已经根据v值进行了编程。然后是签名过程的输出与后面的Hybrid签名之间的统计距离不以任何密钥si作为输入的算法最多为 ：
在HybridSign中随机统一设置，而在真正的签名方案中， H首先会检查H是否已经被评估，aiyi ,µ并且只给它一个随机值。
最后一个不等式成立是因为最多有一个可能的z1满足这个方程（因为Zq[x]是一个积分域）并且因为离散高斯分布中最可能的元素是0，其概率小于(√2πσ−1 )−n 。
因此，如果已经设置了随机预言机的v个值，则小于av·( √2πσ−1)−d2的概率是会有碰撞的。
结语
为简单起见，我们现在将公钥称为（a1， ...，ak，t）。在攻击期间，对手可能会以三种方式之一与模拟器交互。他可能会要求模拟器使用Hybrid2的消息µ的签名，或者在{0,1}中的任何元素上查询哈希函数H或生成伪造的µ。
如果对手要求µ的签名，模拟器简单地返回混合2的输出。如果对手查询H的某个值，那么模拟器首先检查该值是否已经分配并返回它， 否则只是选择一个随机的元素c∈C并将其编程为H在对手输入上的输出。
如果敌手为消息µ提出一个签名(z1, . . . ,zk,c)，那么这个签名满足等式c=H，在签名查询或随机oracle查询期间编程，那么对手只有1/|C|。
我们将首先处理在签名查询期间设置的情况。在这种情况下，消息µ的k ,c) 。我们现在转向对手为他尚未看到的消息构造签名的情况。 如果对手为新消息µ提出了有效的伪造(z1, . . . ,zk,c)。
参考文献：
1、 Martin Albrecht、Shi Bai 和 L´eo Ducas。对过度拉伸的 NTRU 假设的子场格攻击：一些 FHE 和分级编码方案的密码分析。 IACR 密码学 ePrint 存档，，2016 年。
2、Jean‑Francois Biasse 和 Fang Song。用于计算类群和解决任意度数域中主要理想问题的高效量子算法。在 SODA 中，2016 年。
3、Daniele Micciancio 和 Oded Regev。基于格的密码学，在 Daniel J. Bernstein、Johannes Buchmann 和 Erik Dahmen 的编辑中，后量子密码学章节，第 147‑191 页。施普林格出版社，2008 年。
4、Damien Stehl´e、Ron Steinfeld、Keisuke Tanaka 和 Keita Xagawa。基于高效公钥加密在理想格子上。在 ASIACRYPT，2009 年。
5、 Jung Hee Cheon、Jinhyuck Jeong 和 Changmin Lee。 NTRU 问题和密码分析的算法，没有零编码的 GGH 多线性映射。 IACR 密码学 ePrint 档案，2016 年。
6、 Tim G¨uneysu、Vadim Lyubashevsky 和 Thomas P¨oppelmann。实用的基于格的密码学：嵌入式系统的签名方案，在 CHES 中，2012 年。