环LWE上NTRU型的全同态加密方法

摘要

本发明公开了一种环LWE上NTRU型的全同态加密方法，经过定义参数；进行一个部分同态的加密过程；进行无需启动的全同态加密过程等步骤。通过密钥交换和模交换技术，在加密过程中运用加法加密和乘法加密，输出密文的噪音小于输入密文的噪音，起到了更新密文的作用，但其实现的效率要由于启动的过程，从而实现了无需启动的全同态加密方法，加密效率高，获得的密文也较短。

说明书

技术领域

本发明涉及加密方法领域，具体地讲是一种环LWE上NTRU型的全同态加密方法。

背景技术

全同态加密能够在不知道密钥的情况下，对密文进行任意函数的计算，这一特殊性质 使得全同态加密有广泛的应用需求，例如；云计算安全、数据库密文搜索、安全多方计算、 密文数据可编程系统等等。在云计算环境下应用全同态加密，用户可以将加密后的数据外 包给云端，然后云端可以根据用户的请求(例如查询、统计等)，做相应的计算(是对密 文进行的，一般形式的加密是不能对密文进行计算的，只有全同态加密才可以)，再将结 果返回给用户，用户解密后就可以得到想要的结果。用户因为自己的数据被加密而没有暴 露给云端，其数据隐私安全性得到了保障，云端因为无需解密就可以对密文做任意运算处 理，从而实现了云计算的安全。全同态加密研究受到学术界和工业界的极大关注，具有重 要的科学意义与应用价值。

全同态加密早在1978年就由Rivest，Adleman和Dertouzos提出，之后就成为密码学 界的一个开放难题，被誉为密码学界的“圣杯”。随后相继产生过许多同态加密方案，这 些方案要么是满足加法同态，要么是满足乘法同态，还有一些能够同时满足有限次加法与 乘法的同态方案，但是没有一个是全同态的(全同态的“全”指的是能够对任意函数进行 计算)。直到2009年Gentry突破性的构造出第一个全同态加密方案。Gentry是在电路计 算模型下，基于理想格构造全同态加密方案的。尽管全同态加密方案实现了，但是Gentry 的方案有两个缺陷：第一是效率差(渐进复杂度约为)，其中λ是安全参数)；第二是 构造方案的过程中所依赖的两个假设(循环安全问题和稀疏子集和问题)没有被人们深入 的研究过。所以Gentry的方案就像是一块带有瑕疵的白玉，尽管具有突破性的意义，但也 存在一些问题。

Gentry的构造方法分为三步：第一步，构造一个Somewhat同态加密方案，即只能执 行有限次乘法与加法计算；第二步，压缩解密电路，即简化解密电路，使得解密电路的深 度小于Somewhat同态方案所能执行的电路深度；第三步，启动方案，即每次密文计算后， 对密文同态执行解密电路，似的所得密文的噪音始终保持在一个固定的大小上，相当于降 噪。

第一代全同态加密方案遵循Gentry最初的构造方法。第二代全同态加密方案基于LWE 问题或RLWE问题，构造形式更加简单。尤其是在BGV方案中，引入了一个有效的噪音 管理技术：模交换技术，使得无需启动就能够约减密文的噪音。其原理是每次密文乘积后， 对密文向量乘以一个比例因子进行缩小。使用模交换技术可以获得指数级乘法层数的噪音 的提高，与密钥交换技术结合，可以获得无需启动的层次型全同态加密方案。

NTRU加密方案是最早的加密方案之一，而且以高效著称，因此构造NTRU上的全同 态加密方案非常有意义，现有技术没有基于NTRU上的全同态加密方案。基于以上对于全 同态加密方法的分析，现有技术的全同态加密方法也还存在加密效率差，密文太长的缺陷。

发明内容

本发明要解决的技术问题是，提供一种加密效率高、密文较短的环LWE上NTRU型 的全同态加密方法。

本发明的技术解决方案是，提供以下步骤的环LWE上NTRU型的全同态加密方法， 包括以下步骤：

一、定义参数：

对于整数q，定义加密是在和R_q＝R/qR上进行 的，其中φ(x)＝χⁿ+1是分圆多项式，n是2的幂次方，q是素数且

若多项式f∈R且满足||f||_∞≤B，则称f是B边界的；

｛χ_n｝(n∈N)是一个R上的分布集合，若对于任意f←χ_n都有||f||_∞≤B，则称｛χ_n｝ 是B边界分布，即一个R上的B边界分布输出一个B边界多项式；

高斯分布具有以下性质：对于，任意实数有：

环上元素的乘积有如下性质： $\left|\right|s·t\left(\mathrm{mod}\phi \left(x\right)\right)\left|\right|\le \sqrt{n}·\left|\right|s\left|\right|\left|\right|t\left|\right|,{\left|\right|s·t\left(\mathrm{mod}\phi \left(x\right)\right)\left|\right|}_{\infty }\le n·{\left|\right|s\left|\right|}_{\infty }·{\left|\right|t\left|\right|}_{\infty };$χ是R 上的B边界分布，且S₁，···S_k←χ，则有是n^k-1B^k边界的；

二、进行一个部分同态的加密过程；

(一)参数建立：选择μ位模q，以及n＝(λ，μ)和高斯分布χ＝χ(λ，μ)，使得这些参 数能够保障在环LWE上获得2^λ安全；令参数params＝(q，n，χ)；

(二)密钥的生成：选取f’←χ，计算f←2f’+1使得f≡1(mod2)；若f在R_q中是 不可逆的，则重新选取f’，设置私钥sk＝f∈R；

(三)公钥的生成：选取g←χ，设置公钥pk＝h＝2gf^-1∈R_q；

(四)加密：选取s，e←χ，输出密文c←hs+2e+m∈R_q，即使公钥加一位信息 m得到密文c；

(五)解密：计算μ←fc∈R_q；输出m←μmod2；

由于fc＝fhs+2fe+fm＝2gs+2fe+fm，若||fc||_∞＜q/2，则 μ＝fc，μ(mod2)＝fm(mod2)＝m，所以只要满足||fc||_∞＜q/2，则上述步骤正确；

三、进行无需启动的全同态加密过程；

(一)参数建立：L是电路的层数，令μ＝μ(λ，L)＝θ(logλ+logL)，对j＝0，…，L， 获得递减的模序列q₀，…，q_L，每一层使用相同的高斯分布χ和环参数params_j＝｛q_j，λ，χ，n｝(j＝0，…，L)；

(二)密钥公钥的生成：以步骤二的第二步的方法生成密钥f_j，以步骤二的第三步的 方法生成公钥h_j；令对f′_j和f_j+1进行密钥交换，令密钥sk包括f_j， 公钥pk包含h_j和其中j＝0，...，L，当j＝L时没有ζ，电路每一层有相应的公钥 与私钥三元组

(三)加密：对公钥pk加一位信息m进行加密；

(四)解密；假设密文c是在第j层电路，对应的密钥f_j，对私钥sk进行解密得到明 文m，

(五)加法过程：假设c₁、c₂的解密密钥是f_j，即在同一层电路，若不在同一层电路 可以进行密钥交换；令c₃的密钥是f_j，将c₃的密钥设为即f′_j再 通过约减密文噪音的方法，得出新的密文c₄；

(六)乘法过程：假设c₁、c₂的解密密钥是f_j，即在同一层电路，若不在同一层电路 可以进行密钥交换；令c₃的密钥是再通过约减密文噪音的 方法，得出新的密文c₄。

采用本发明的方法，与现有技术相比，本发明具有以下优点：本发明通过密钥交换和 模交换技术，在加密过程中运用加法加密和乘法加密，输出密文的噪音小于输入密文的噪 音，起到了更新密文的作用，但其实现的效率要由于启动的过程，从而实现了无需启动的 全同态加密方法，加密效率高，获得的密文也较短。

作为改进，所述的约减密文噪音的方法包含两步：第一步是密钥交换，将密文转换成 下一层电路的密文，密钥由转变成f_j+1，c₁对应的密钥是f_j+1，对应的模是q_j，第二步 进行模交换，约减密文的噪音，c₂对应的密钥是f_j+1，对应的模是q_j+1；f_j+1取值较小， 选取自高斯分布χ，从而保证了模交换的有效性。

作为改进，所述的密钥交换包含两个过程：第一个过程是输入两个密钥和模，输出辅 助信息以保证交换；第二个过程是输入辅助信息和初始密文，输出一个新密文，初始密文 和新密文是对同一明文的加密。

具体实施方式

下面就具体实施例对本发明作进一步说明。

本发明的环LWE上NTRU型的全同态加密方法，包括以下步骤：

一、定义参数：

对于整数q，定义加密是在和R_q＝R/qR上进行 的，其中φ(x)＝χⁿ+1是分圆多项式，n是2的幂次方，q是素数且

若多项式f∈R且满足||f||_∞≤B，则称f是B边界的；

｛χ_n｝(n∈N)是一个R上的分布集合，若对于任意f←χ_n都有||f||_∞≤B，则称｛χ_n｝ 是B边界分布，即一个R上的B边界分布输出一个B边界多项式；

高斯分布具有以下性质：对于任意实数有：

环上元素的乘积有如下性质： $\left|\right|s·t\left(\mathrm{mod}\phi \left(x\right)\right)\left|\right|\le \sqrt{n}·\left|\right|s\left|\right|\left|\right|t\left|\right|,{\left|\right|s·t\left(\mathrm{mod}\phi \left(x\right)\right)\left|\right|}_{\infty }\le n·{\left|\right|s\left|\right|}_{\infty }·{\left|\right|t\left|\right|}_{\infty };$χ是R 上的B边界分布，且S₁，…S_k←χ，则有是n^k-1B^k边界的；

二、进行一个部分同态的加密过程；

(一)参数建立：选择μ位模q，以及n＝(λ，μ)和高斯分布χ＝χ(λ，μ)，使得这些参 数能够保障在环LWE上获得2^λ安全；令参数params＝(q，n，χ)；

(二)密钥的生成：选取f’←χ，计算f←2f’+1使得f≡1(mod2)；若f在R_q中是 不可逆的，则重新选取f’，设置私钥sk＝f∈R；

(三)公钥的生成：选取g←χ，设置公钥pk＝h＝2gf^-1∈R_q；

(四)加密：选取s，e←χ，输出密文c←hs+2e+m∈R_q，即使公钥加一位信息 m得到密文c；

(五)解密：计算μ←f_c∈R_q；输出m←μmod2；

由于fc＝fhs+2fe+fm＝2gs+2fe+fm，若||fc||_∞＜q/2，则 μ＝fc，μ(mod2)＝fm(mod2)＝m，所以只要满足||fc||_∞＜q/2，则上述步骤正确；

三、进行无需启动的全同态加密过程；

(一)参数建立：L是电路的层数，令μ＝μ(λ，L)＝θ(logλ+logL)，对j＝0，…，L， 获得递减的模序列q₀，…，q_L，每一层使用相同的高斯分布χ和环参数params_j＝｛q_j，λ，χ，n｝(j＝0，…，L)；

(二)密钥公钥的生成：以步骤二的第二步的方法生成密钥f_j，以步骤二的第三步的 方法生成公钥h_j；令对和f_j+1进行密钥交换，令密钥sk包括f_j， 公钥pk包含h_j和其中j＝0，...，L，当j＝L时没有ζ，电路每一层有相应的公钥 与私钥三元组

(三)加密：对公钥pk加一位信息m进行加密；

(四)解密；假设密文c是在第j层电路，对应的密钥f_j，对私钥sk进行解密得到明 文m，

(五)加法过程：假设c₁、c₂的解密密钥是f_j，即在同一层电路，若不在同一层电路 可以进行密钥交换；令c₃的密钥是f_j，将c₃的密钥设为即再 通过约减密文噪音的方法，得出新的密文c₄；

(六)乘法过程：假设c₁、c₂的解密密钥是f_j，即在同一层电路，若不在同一层电路 可以进行密钥交换；令c₃的密钥是再通过约减密文噪音的 方法，得出新的密文c₄。

所述的约减密文噪音的方法包含两步：第一步是密钥交换，将密文转换成下一层电路 的密文，密钥由转变成f_j+1，f₁对应的密钥是f_j+1，对应的模是q_j，第二步进行模交换， 约减密文的噪音，f₂对应的密钥是f_j+1，对应的模是q_j+1；f_j+1取值较小，选取自高斯分 布χ，从而保证了模交换的有效性。

所述的密钥交换包含两个过程：第一个过程是输入两个密钥和模，输出辅助信息以保 证交换；第二个过程是输入辅助信息和初始密文，输出一个新密文，初始密文和新密文是 对同一明文的加密。

以上仅就本发明较佳的实施例作了说明，但不能理解为是对权利要求的限制。本发明 不仅局限于以上实施例，其具体结构允许有变化。总之，凡在本发明独立权利要求的保护 范围内所作的各种变化均在本发明的保护范围内。