一种环域上误差学习问题的加密方法及电路

摘要

本发明公开了一种环域上误差学习问题的加密方法，该方法通过采样多项式和噪声多项式并进行数论变换，对数论变换后的结果进行运算，获得公钥和密文，完成对待加密信息的加密。本发明还公开了一种实现该方法的电路，包括：加密控制器、待加密信息存储器、高斯采样模块、只读存储器、高斯数据存储模块、数论变换处理器、迭代模乘法模块以及密文存储模块；所述高斯采样模块采样生成多项式和噪声多项式；所述数论变换处理器用于对多项式、噪声多项式以及常量多项式进行数论变换，对待加密信息、噪声多项式以及公钥进行运算后形成密文。本发明的方法和电路极大地提高电路的运行效率，减小电路损耗，降低环域上误差学习问题加密电路的实现成本。

说明书

技术领域

本发明属于信息安全算法及电路实现领域，特别涉及一种环域上误差学习问题的加密方法及实现该方法的电路。

背景技术

基于格理论的密码算法是目前公钥加密技术中一个新的研究热点。随着量子计算机的出现，传统的公钥加密体制如基于大整数分解的RSA(Rivest Shamir Adleman)和基于离散对数问题的椭圆曲线密码算法(Elliptic Curve Cryptography，ECC)变得不再安全可靠。相较而言，基于格理论的密码算法具有加密效率高，硬件实现简单，抗量子攻击等方面的优点，是后量子时代极具潜力的能解决信息安全问题的密码方案。

目前基于格困难性构造的加密方案中，效率最高的是基于误差学习问题(learning with error，LWE)而构造的加密方案。环域上的误差学习问题(Ring-LWE)加密方案是在LWE加密方案上的改进，不同的是它整个的加密解密都是在环域(Ring)中进行的，加密和解密过程中的乘法运算是多项式乘法。与LWE方案相比，Ring-LWE方案的性能整体上优于LWE方案：Ring-LWE方案的错误率更低，密文扩展更小，最重要的一点是，Ring-LWE方案的公钥长度很小，能够控制在2kbits～5kbits，和RSA方案的公钥长度差不多。并且，Ring-LWE方案运算速度也更快，准确率也更高。考虑到Ring-LWE加密方案具有的抗量子攻击的特性以及易实现性，为了该加密方案能在未来日常应用中的实现，设计出资源占用少、功耗小、成本低的Ring-LWE硬件加密电路是一个值得深入研究的问题。

文献“Towards Practical Lattice-Based Public-Key Encryption onReconfigurable Hardware”(T,Güneysu T.Selected A：reas inCryptography--SAC 2013.Springer Berlin Heidelberg,2013:68-85.)公开了一种Ring-LWE加密处理器。但该文献公开的Ring-LWE加密处理器存在如下缺陷或不足：

(1)从最终现场可编程门阵列(Field－Programmable Gate Array,FPGA)平台上的资源消耗和运算性能进行折中分析，可以看到，该文献中所提出的Ring-LWE加密处理器需要大量的LUT单元以及复杂的数字信号处理(Digital Signal Process，DSP)模块和存储器模块，消耗电路资源过于庞大。且该Ring-LWE加密处理器过于追求速度和吞吐量，并不具备实用性和通用性。

(2)在轻量级应用或资源限定的应用场合，如：金融IC卡或射频标签中，需要低成本、易实现的安全加密电路。显然，文献中的Ring-LWE加密处理器由于其设计上的复杂度而很难在这些场合得以实现和应用。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种环域上误差学习问题的加密方法及电路，其目的在于通过高斯采样模块用于采样系数满足高斯分布的多项式和噪声多项式，所述多项式形成公匙和私匙，所述噪声多项式形成密文，采用数论变换处理器在采样后对所述多项式和噪声多项式进行数论变换，并在所述密文解密完成后对其进行数论逆变换，通过加密控制器用于控制所述电路对所述密文和私匙在所述环域上进行加解密运算，实现加解密工作，极大地缩减加解密过程的计算复杂度，从而减少运算时间，提高电路的运行效率，减小电路损耗，降低Ring-LWE加解密电路的实现成本。

为了实现上述目的，作为本发明的一个方面，提供一种环域上误差学习问题的加密方法，包括如下步骤：

S1：将待加密信息m中的常量多项式a进行数论变换，得到NTT(a)；

S2：采样生成私钥r₂，并对r₂进行数论变换，得到NTT(r₂)；

S3：作点乘运算NTT(r₂)*NTT(a)，计算结果为NTT(r₂*a)；

S4：采样得到多项式r1，并对r1进行NTT变换，得到NTT(r1)，并将NTT(r1)与NTT(r2*a)做运算NTT(r1)–NTT(a)·NTT(r2)，计算结果NTT(p)作为环域上的困难学习问题加密方案的公钥；

S5：采样得到噪声多项式e1，并对e1进行NTT变换，得到NTT(e1)；

S6：依次作点乘运算NTT(e1)*NTT(a)和NTT(e1)*NTT(p),将计算结果NTT(e1*a)和NTT(e1*p)按照地址顺序依次保存；

S7：采样得到噪声多项式e2，并对e2进行NTT变换，得到NTT(e2)，并将NTT(e2)与NTT(e1*a)做运算NTT(e2)+NTT(a)·NTT(e1)，将计算结果NTT(c1)按照地址顺序依次保存，得到密文的第一部分；

S8：采样得到噪声多项式e3，对待加密信息内容进行编码运算得到f(m)∈Rq，进行模加运算得到e3’＝e3+f(m)，结果按照地址顺序依次保存，其中，Rq为模值q下的整数环，q为模值；

S9：对e3’进行NTT变换，得到NTT(e3’)，并将NTT(e3’)与NTT(e1*p)做运算NTT(e3’)+NTT(p)·NTT(e1)，计算结果NTT(c2)按照地址顺序依次保存，得到密文的第二部分，从而实现对待加密信息m的加密。

进一步地，所述多项式r1、私钥r₂、噪声多项式e1、e2及e3的系数满足高斯分布。

进一步地，所述常量多项式a满足均匀分布。

作为本发明的另一个方面，提供一种实现所述的环域上误差学习问题的加密方法的电路，该电路包括：加密控制器、待加密信息存储器、高斯采样模块、只读存储器、高斯数据存储模块、数论变换处理器、迭代模乘法模块以及密文存储模块；

其中，所述加密控制器的第一输出端与所述待加密信息存储器的输入端连接，用于对所述待加密信息在环域上进行编码并存储到所述待加密信息存储器中；

所述加密控制器的第二输出端与所述高斯采样模块的输入端连接，用于发出控制信号给所述高斯采样模块，控制所述高斯采样模块采样生成所述多项式和噪声多项式，并存储到所述高斯数据存储模块中；

所述只读存储器的输出端与所述高斯数据存储模块的输入端连接，用于读取储存所述常量多项式；

所述数论变换处理器的输入端与所述高斯数据存储模块的输出端连接，所述数论变换处理器的输出端与所述密文存储模块的输入端连接，用于对所述多项式、噪声多项式以及常量多项式进行数论变换；

所述迭代模乘法模块的输入端与所述高斯数据存储模块的输出端连接，所述迭代模乘法模块的输出端与所述密文存储模块的输入端连接，用于对所述数论变换后的多项式和常量多项式进行运算得到公钥；并对所述待加密信息、噪声多项式以及所述公钥进行加密运算后形成密文，并存储到密文存储模块中，实现对所述待加密信息的加密。

进一步地，所述高斯采样模块包括伪随机数发生器，用于产生随机数，所述随机数的范围为[1,N-1]，N为所述多项式的长度。

进一步地，所述高斯采样模块还包括查找表和比较器，所述比较器的输入端与所述伪随机数发生器和查找表连接，所述查找表用于与所述随机数进行比较，由比较器输出对应的高斯分布采样值。

进一步地，所述高斯采样模块还包括选择器，所述选择器的输入端与所述比较器连接，所述选择器用于根据所述高斯分布采样值决定最终输出系数满足高斯分布的多项式和噪声多项式。

进一步地，所述迭代模乘法模块包括第一寄存器、第二寄存器、状态控制器、选择器以及左移位器，其中，所述状态控制器用于控制所述第一寄存器存储值输入到选择器中作为选择信号，并控制所述第二寄存器存储值输入给左移位器，左移位器用于对其进行移位后输出到所述选择器的一个输入端，所述选择器的另一个输入端的输入值恒为0，在选择信号的作用下，所述选择器对所述移位后的存储值进行选择并输出。

进一步地，所述迭代模乘法模块还包括模加法器和第三寄存器，所述模加法器用于对所述选择器输出的值进行累加，并存到所述第三寄存器中。

进一步地，所述密文存储模块包括区域1和区域2，分别用于储存所述密文第一部分和密文第二部分。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

(1)本发明的方法，在加解密运算过程里，密钥产生和加密阶段中不需要inv_NTT运算，因此能够极大地缩减加解密过程的计算复杂度，占用电路资源极少，且内部LUT数据可修改，能与不同参数下的Ring-LWE加密方案匹配，满足了Ring-LWE加密方案在未来不同应用中低成本、可重构的要求，而且该Ring-LWE加密方案低成本、低功耗。

(2)本发明的电路，通过高斯采样模块用于采样系数满足高斯分布的多项式和噪声多项式，采用数论变换处理器在采样后对所述多项式和噪声多项式进行数论变换，所述多项式经过运算得到公钥和私钥，所述待加密信息、噪声多项式以及所述公钥进行加密运算后形成密文，并存储到密文存储模块中，实现对所述待加密信息的加密，极大地缩减加密过程的计算复杂度，从而减少运算时间，提高了电路的运行效率，减小了电路损耗，降低了Ring-LWE加密电路的实现成本。

(3)作为优化，本发明设计了一种基于查找表(LUT)的高斯采样模块，用于生成系数满足高斯分布的多项式和噪声多项式。在模块内部的LFSR(线性反馈移位寄存器)产生的伪随机数源经由LUT后，即可输出对应的高斯采样值。由于无需涉及任何高斯采样中复杂的指数运算，该高斯采样模块占用电路资源极少，且内部LUT数据可修改，能与不同参数下的Ring-LWE加密方案匹配，满足了Ring-LWE加密方案在未来不同应用中低成本、可重构的要求。

(4)作为优化，本发明设计了一种精简的迭代模乘法模块。考虑到Ring-LWE加密方案中最核心的运算是模q下的乘法运算，迭代模乘法模块能通过循环迭代，仅由简单的模加和移位操作完成复杂的模乘运算，能让Ring-LWE加密方案以低成本、低功耗的电路结构得以实现。

附图说明

图1为本发明实施例的一种环域上误差学习问题的加密电路结构图；

图2为本发明实施例的一种环域上误差学习问题的加密电路涉及的高斯采样模块结构图；

图3为本发明实施例的一种环域上误差学习问题的加密电路涉及的模乘法模块结构图。

所有附图中，相同的附图标记表示同一个电路元件，其中：M1-伪随机数发生器、M2-查找表、M3-比较器、M4-选择器、M5-左移位器、M6-模加法器。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

图1为本发明实施例的一种环域上误差学习问题的加密电路结构图。如图1所示，该电路包括加密控制器、待加密信息存储器、高斯采样模块、高斯数据存储模块、数论变换处理器、迭代模乘法器、密文存模块、私钥读写存储器以及只读存储器；

其中，所述加密控制器的第一输出端与所述待加密信息存储器的输入端连接，所述待加密信息存储器的输出端与所述高斯数据存储模块的输入端连接；

所述加密控制器的第二输出端与所述高斯采样模块的输入端连接，所述高斯采样模块的输出端与所述高斯数据存储模块的输入端连接，所述只读存存器的输出端与所述高斯数据存储模块的输入端连接；

所述高斯数据存储模块的输出端分别与所述数论变换处理器、迭代模乘法模块以及私钥读写存存器的输入端连接，所述迭代模乘法模块的输出端与所述密文存储模块的输入端连接；所述数论变换处理器的输出端与所述密文存储模块的输入端连接，所述密文存储模块的输出端与所述迭代模乘法模块输入端连接；

如图1所示，所述加密控制器用于对输入的加密信息m进行编码，让m的值限定在环域Rq中，即f(m)∈Rq，并存储到所述待加密信息存储器中。

所述高斯采样器用于采样系数满足高斯分布χ_σ的多项式r₁∈Rq和r₂∈Rq，得到公钥：

p＝r₁-a·r₂∈Rq；

其中，多项式p为环域上的困难学习问题加密方案的公钥，多项式r₂作为私钥，a为系数满足均匀分布U(0,q)的常量多项式，q为模值，Rq为模值q下的整数环；

高斯采样器用于采样得到三个系数满足高斯分布χ_σ的噪声多项式e₁，e₂，e₃∈Rq，得到第一段密文c₁：

c₁＝a·e₁+e₂∈Rq；

以及第二段密文c₂：

c₂＝p·e₁+e₃+f(m)∈Rq。

如图1所示，所述数论变换处理器用于对所述多项式和噪声多项式进行数论变换；

所述公钥p的数论变换为：

NTT(p)＝NTT(r₁)–NTT(a)*NTT(r₂)∈Rq；

其中，NTT为数论变换。

所述密文c₁和c₂的数论变换为：

NTT(c₁)＝NTT(a)*NTT(e₁)+NTT(e₂)∈Rq；

NTT(c₂)＝NTT(p)*NTT(e₁)+NTT(e₃+f(m))∈Rq。

所述迭代模乘法模块用于对所述多项式和常量多项式进行运算得到公钥；并对所述待加密信息、噪声多项式以及所述公钥进行加密运算后形成密文；

所述加密控制器的第三输出端与所述密文存储模块的输入端连接，用于控制所述密文存储模块存储所述密文，实现对所述待加密信息的加密。

本发明的电路，通过高斯采样模块用于采样系数满足高斯分布的多项式和噪声多项式，采用数论变换处理器在采样后对所述多项式和噪声多项式进行数论变换，所述多项式经过运算得到公钥和私钥，所述待加密信息、噪声多项式以及所述公钥进行加密运算后形成密文，并存储到密文存储模块中，实现对所述待加密信息的加密，极大地缩减加密过程的计算复杂度，从而减少运算时间，提高了电路的运行效率，减小了电路损耗，降低了Ring-LWE加密电路的实现成本。

图2为本发明实施例的一种环域上误差学习问题的加密电路涉及的高斯采样模块结构图。为满足环域上误差学习问题加解密算法电路低成本的要求，本发明设计了一种基于查找表(LUT)的高斯采样模块。如附图2所示，所述高斯采样模块包括伪随机数发生器M1、查找表M2、比较器M3、选择器M4。

工作时，一个由log₂N>

在本发明的一个优选实施例中，假设由8bit-LFSR构建伪随机数发生器(PRNG)M1产生了一个随机数r0＝160，通过比较器M3内部的判断函数freq(x-1)<r0≤freq(x)，freq(x)为高斯采样值x的频数分布函数，可以找到查找表M2中对应的freq(1)＝150、freq(2)＝172和x＝2。由于r0[0]＝1’b0，通过选择器M4的选择，得到最终高斯采样模块输出的高斯采样值为2。

本发明设计了一种基于查找表(LUT)的高斯采样模块，用于生成系数满足高斯分布的多项式和噪声多项式。在模块内部的LFSR(线性反馈移位寄存器)产生的伪随机数源经由LUT后，即可输出对应的高斯采样值。由于无需涉及任何高斯采样中复杂的指数运算，该高斯采样模块占用电路资源极少，且内部LUT数据可修改，能与不同参数下的Ring-LWE加密方案匹配，满足了Ring-LWE加密方案在未来不同应用中低成本、可重构的要求。

图3为本发明实施例的一种环域上误差学习问题的加密电路涉及的迭代模乘法模块结构图。为满足环域上误差学习问题加解密算法电路低成本、低功耗的要求，本发明设计的迭代模乘法模块仅需数据在三个寄存器(第一寄存器Ra，第二寄存器Rb，第三寄存器S)中进行简单的模加和移位运算：第一寄存器Ra和第二寄存器Rb存储乘法器的两个输入数据，第三寄存器S中存放累加运算和并在控制信号的调度下输出最终的乘积结果。

在本发明的一个优选实施例中，如图3所示，迭代模乘法模块在内部状态控制器的调度下，在第i次迭代循环中，第一寄存器Ra存储的值的第i位输入到选择器M6中，作为选择信号；第二寄存器Rb存储的值输入给左移位器M5后，由左移位器M5输出左移i位并取模q的结果Rb’。左移位器M5输出到选择器M4的一个输入端，M4的另一个输入端口的输入值恒定为0。在选择信号的作用下，选择器M4将输出值Ra[i]*(Rb<<1)mod q通过模加法器M6累加到第三寄存器S中。直到i＝MSB(Ra)，迭代计算完毕，将寄存器S的结果输出。

本发明设计了一种精简的迭代模乘法模块。考虑到Ring-LWE加密方案中最核心的运算是模q下的乘法运算，迭代模乘法模块能通过循环迭代，仅由简单的模加和移位操作完成复杂的模乘运算，能让Ring-LWE加密方案以低成本、低功耗的电路结构得以实现。

在本发明的一个优选实施例中，如图1所示，基于格理论的环域上误差学习问题加解密算法过程如下：

步骤一：向所述加密电路中输入待加密的信息m，将m保存至待加密信息存储器中；

步骤二：从存有常量多项式a的待加密信息存储器中将a读入到高斯数据存储模块中，接着数论变换处理器对高斯数据存储模块中的a进行数论变换(NTT)，得到NTT(a)；

步骤三：将NTT(a)先后存储到读写存储器块密文存储模块的区域1和区域2中，区域1和区域2为读写存储器块内部地址大小为N的区域。

步骤四：高斯采样模块采样以生成私钥r₂，存储在高斯数据存储模块中。数论变换处理器对高斯数据存储模块中的r₂进行NTT变换，得到NTT(r₂)，并将NTT(r₂)保存到私钥读写存储器等待解密时进行使用；

步骤五：调用迭代模乘法模块作点乘运算NTT(r₂)*NTT(a),计算结果NTT(r₂*a)按照地址顺序依次保存在密文存储模块的区域2中。

步骤六：高斯采样模块采样得到多项式r₁，存储在高斯数据存储模块中。数论变换处理器对高斯数据存储模块中的r₁进行NTT变换，得到NTT(r₁)，并将NTT(r₁)与区域2中的NTT(r₂*a)做运算NTT(r₁)–NTT(a)·NTT(r₂)，计算结果NTT(p)按照地址顺序依次保存在密文存储模块的区域2中；

至此密钥产生的工作完成，进入加密运算的部分；

步骤七：高斯采样模块采样得到噪声多项式e₁，存储在高斯数据存储模块中。数论变换处理器对高斯数据存储模块中的e₁进行NTT变换，得到NTT(e₁)；

步骤八：调用迭代模乘法模块依次作点乘运算NTT(e₁)*NTT(a)和NTT(e₁)*NTT(p),计算结果NTT(e₁*a)和NTT(e₁*p)按照地址顺序依次保存在密文存储模块的区域1和区域2中；

步骤九：高斯采样模块采样得到噪声多项式e₂，存储在高斯数据存储模块中。数论变换处理器对高斯数据存储模块中的e₂进行NTT变换，得到NTT(e₂)，并将NTT(e₂)与区域1中的NTT(e₁*a)做运算NTT(e₂)+NTT(a)·NTT(e₁)，计算结果NTT(c₁)按照地址顺序依次保存在密文存储模块的区域1中，得到密文的第一部分；

步骤十：高斯采样模块采样得到噪声多项式e₃，存储在高斯数据存储模块中。对R_m中的信息内容进行编码运算，0编码为0，1编码为2/q，得到f(m)∈Rq。进行模加运算得到e₃’＝e₃+f(m)，结果按照地址顺序依次保存在高斯数据存储模块中，其中，Rq为模值q下的整数环，q为模值。

步骤十一：数论变换处理器对高斯数据存储模块中的e₃’进行NTT变换，得到NTT(e₃’)，并将NTT(e₃’)与区域2中的NTT(e₁*p)做运算NTT(e₃’)+NTT(p)·NTT(e₁)，计算结果NTT(c₂)按照地址顺序依次保存在密文存储模块的区域2中。得到密文的第二部分。

至此，加密运算已经完成，电路内部的读写存储器块密文存储模块存有密文NTT(c₁)和NTT(c₂)、读写存储器块存有私钥NTT(r₂)供解密使用。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。