基于有错配对的新密码系统

摘要

本发明建立了新的密钥交换系统,密钥分配系统,基于身份的加密系统.这些系统基于相同的数学原理,即有错配对原理.有错配对原理可以看成LWE问题的拓展.这些新系统效率高,安全性好,可以证明安全,能够抵御量子计算机攻击。

说明书

背景技术

本申请拥有在2012年4月12日提交的美国临时专利申请(题目：安全通信 和安全信息系统的新方法,序列号：61623272)中的发明优先权,其中包括完整 的参考资料,适用于所有目的.

本发明是有关密码系统设计,尤其是,密钥交换系统(KE),密钥分配系统 (KD)和基于身份的加密系统(IBE),本质上都是基于相同的数学原理,即有错配 对原理.

在现代通信系统中,如互联网、手机等,出于对保护通信信息的秘密性考虑, 我们需要对信息进行加密.目前有两种不同的加密方法.第一,用对称密码系 统加密信息,此时,发送方用于加密的密钥与接收方用于解密的密钥相同.对 称密码系统要求发送方和接收方有一个安全的渠道来交换共享密钥.因为在开 放的通信渠道中,没有可信的第三方来交换密钥,所以需要用某种方法在对开放 的渠道中交换密钥.此外,在一个有中央服务器的系统中,如电话公司的手机 服务系统,需要一个有效的和可以扩展的密钥分配系统,使得任意两个用户都 可以利用通过中央服务器所建的密钥分配系统获得一个共享密钥.因此,建立 安全有效的密钥交换系统和密钥分配系统是十分重要和必要的.第一个密钥交 换系统由Diffie和Hellman[DiHe]提出,该系统的安全性基于离散对数问题 的困难性.Shor[SHO]的工作表明,该系统可以被将来的量子计算机攻破.目前 有许多密钥分配系统,包括利用二次型对的密钥分配系统[BSHKVY]和基于椭圆 曲线上的双线性型对的密钥分配系统(美国专利7,590,236).但是,现有的系 统存在计算效率或可扩展性方面的问题,如基于椭圆曲线上的双线性型对的密 钥分配系统的计算效率很低.

第二,利用非对称密码系统,即公钥密码系统加密.此时,接收方有一组 公钥和一组私钥,但发送方只有公钥.发送方利用公钥加密信息,接收方利用 私钥解密信息,只有私钥拥有方才能解密信息.在通常的公钥系统中,我们需 要认证公钥,因此每一个公钥需要有一个认证证书,即一个由可信的权威中心 提供的数字签名.证书用来确认公钥是否属于合法的使用方,即信息接收方. 为了让公钥加密系统完全可用,我们需要一个称为公钥基础设施的系统.

1984年,Shamir提出了另外一种公钥加密系统[SHA].在此密码系统中,一 个人或实体的公钥,由一个能够唯一识别个人或实体的信息的公开算法生成. 例如,对一个人来说,这些信息可能包括姓名、住址、生日、指纹信息、电子邮 箱、社会安全号等.由于公钥是由可以识别个人的信息决定的,所以这类公钥密 码系统被称为基于身份的加密系统(IBE).

基于身份的公钥加密系统并不多,目前正在使用的是Boneh和Franklin 发明的基于椭圆曲线上的双线性型对的基于身份的加密系统(美国专利： 7,113,594).在基于身份的加密系统中,发送方用基于接收方身份的公钥加密 信息.接收方用其私钥解密信息.接收方从一个中央服务器获得私钥,其中中 央服务器有一个生成和分配私钥给合法用户的系统.基于身份的加密系统不需 要发送方搜索接收方的公钥,发送方利用鉴别接收者身份的信息,如电子邮箱、 身份证号或其他信息等,从基于身份的加密系统中可获得任意接收者对应的公 钥.现有的基于身份加密系统复杂,且计算效率不高.并且这些基于椭圆曲线 上的双线性型对的加密系统可被量子计算机攻破.此外,还有一些基于格理论 的构造[ABB][ABVVW][BKPW],但在实际应用中,这些都是相当复杂的系统.因 而设计安全有效的基于身份的加密系统是十分重要和必要的.

显然,在实际应用中,我们仍然需要更有效和更安全的KE,KD和IBE系 统.

发明内容

本发明首次提出了一种用于开放渠道中新的安全的密钥交换方法.这种方 法基于用不同的方法计算相同的双线性型,其中每种不同的计算方法会产生一 些错误.在密钥交换过程中,交换双方A，B各自保密选择一个私钥矩阵S_A，S_B其中矩阵的元素是小的且服从某种的错误分布,然后任意选择一个公开矩阵M. 密钥交换双方用各自的私钥矩阵与公开矩阵M相乘,但有些错误,交换相乘后 的矩阵,用基于M的同一个双线性型、两种不同的方法、并加入一些错误计算一 对S_A，S_B的配对这种数学计算被称为有错配对.共享密钥来自于有错配对.此 方法可以看做错误学习思想的拓展,该思想在2005年被Regev发现[Reg].本系 统的安全性依赖于某个可用数学证明的格问题的困难性[DiLi].本系统只涉及 矩阵乘法,因而计算效率极高.本系统还可以抵御将来的量子计算机攻击.

本发明第二项内容包括建立密钥分配系统的新方法.在本系统中,中央服 务器或权威机构以矩阵A_i的形式分配给每个用户一个公开的ID,或者以矩阵A_i的形式为每个用户建立一个ID,其中A_i的元素是小的并服从某种错误分布,这 些错误信息可以唯一识别被所有者.此外,中央服务器或权威机构给每个用户分 配一个私钥,这个私钥是矩阵M与ID矩阵A_i的乘积.然后任意两个用户可以用 相同的二次型不同的方式和某些错误计算用户两个ID矩阵对,从而获得共享密 钥.此方法可以视为错误学习思想的拓展,该思想在2005年被Regev发现[Reg]. 本系统的安全性依赖于有错配对相关问题的困难性.本系统只涉及矩阵乘法, 因而计算效率极高.本系统还可以抵御将来的量子计算机攻击.

本发明的第三项内容包括建立基于身份的加密系统的新方法.在本系统中, 中央服务器或权威机构以矩阵A_i的形式分配给每个用户一个公开的ID,或者以 矩阵A_i的形式为每个用户建立一个ID,其中A_i的元素是小的并服从某种错误分 布,这些错误信息可以被所有者唯一识别.系统给每个用户一个私钥S_i,私钥是 由ID矩阵与系统密钥矩阵S(有错)相乘而得,而这里的错误矩阵与系统公钥矩 阵M相关.中央服务器或权威机构通过M和S相乘建立另一个密钥M₁,其中矩阵 相乘时加入一些错误.任意一个用户希望发送给另一个用户i一个信息,可以计 算用户i的公钥,用户i的公钥由M和矩阵对M和A_i有错组成.然后用基于MLWE问 题的加密系统加密信息,用户i用密钥S_i解密信息.此方法可以看为错误学习思 想的拓展,该思想在2005年被Regev发现[Reg].本系统的安全性依赖于某个可 用数学证明的格问题的困难性[DiLi].本系统只涉及矩阵乘法,因而计算效率 极高.本系统还可以抵御将来的量子计算机攻击.

在我们的构造中,可以用格理想的元素代替矩阵,我们还可以利用其他舍 入技术.本系统可以以分布式的方式使多个服务器同时服务,即建立分布式的 KD和IBE系统.

总之,我们用相同的数学原理建立安全有效的KE,KD和IBE系统,该原 理可以看成LWE问题的扩展.

虽然本发明是用具体的实例描述的,但是显然对那些熟悉密码学技术的人 来说,可以很容易根据我们的具体实例变型、替换和修改.因此本文档里的实例 仅仅是示范性的,本发明并非局限于此,各种在本发明精神和范围的变化都在 本发明的优先权请求之内.本发明基本基于在2012年4月12日提交的美国临时 专利申请(题目：安全通信和安全信息系统的新方法,序列号：61623272)，只 增加了技术细节。

具体实施方式

1.1有错配对理论基础

2005年,Regev在[Reg]中介绍了错误学习理论问题,和以后作为该理论的 拓展的在环上的错误学习理论(RLWE)问题[LPR]，它们被广泛的应用于密码学设 计,并有可证明安全的性质,原因在于它们可以归结为某个最坏情形的格上的 问题,因而可用于密码设计.

LWE问题描述如下,首先,我们需要有一个参数n,q个元素的有限环或有 限域F_q上的错误概率分布κ.为简单起见,不妨设q是奇素数,但通过微小的 变更,我们的发明可用于其他整数.

F_q中的元素可用集合{-(q-1)/2,..,0,...,(q-1)/2}描述.错误分布指 的是以很高的概率选择F_q中较小数的概率分布.有较多这样的分布选择并且分 布选择直接影响系统的安全性.我们必须选择一个好的错误概率分布使得系统 更有效更安全.

令∏_Sκ为F_q上的一个概率分布,此分布通过以下方式获得,从中任意 选择A,然后再从F_q中按照分布κ选择元素e,最后得到(A,<A,S>+e),其 中+指的是F_q上的加法.对任意的和∏_Sκ任意独立样本,解决关于q和分 布κ的LWE问题的算法以很高的概率输出S.

为了完成基于LWE问题的密码设计的安全性证明,设q是关于n的特殊的 多项式函数,记为q(n).设κ是一个离散的正态分布,期望为0,标准差为 将此分布另记为κ_σ.的元素表示为[-(q-1)/2,(q-1)/2)]中 的整数.

在最初的基于LWE问题的加密系统中,一次只能加密一位,因此该系统是 相当低效率的,并且密钥很大.为了进一步改进基于LWE问题的密码系统的效 率,文献[LPR]提出了基于多项式环F_q[x]的商环的LWE问题,即(RLWE)环问题. 在基于RLWE问题的密码系统中,它们的安全性归结为格的子类的困难性问题, 用格理想的类代替通常的格.

随后，文献[ACPS]提出了LWE的变种.我们用m×n矩阵A代替向量A,S是 n×1矩阵,使得矩阵乘法A×S相容.e也用m×1矩阵代替.但仍然用q个元 素的有限域.

为简化说明起见,设A是n×n方阵,S和e是n×1矩阵.

令是F_q上的概率分布,任意选择一个n×n矩阵A,矩阵A的元素属于 F_q,以某种错误分布κ_n任意选择e的元素,其中e是n×1矩阵.例如,每个元 素分别按照错误分布κ任意选择.输出(A,A×S+e),其中+指的是F_q上的加 法.一个解决关于q和错误分布κ的LWE问题的算法,如果对任意的和 任意独立样本,以很高的概率输出为S.

若S的元素较小,且S的元素独立地按照错误分布κ_n选择，称为LWE问题 (SLWE).如果A为对称矩阵,称为小对称LWE(SSLWE).如果秘密矩阵S的元素 是从-z,…,0,1,…,z(z是小正整数)中任意独立地选择的，称为均匀小LWE问 题(USLWE).

在实际应用中,S和e的元素可以用不同的分布选择.

由[ACPS]的结果可知,如果密钥S和e的元素根据同一个LWE错误分布κ_σ独 立选择,那么解决对应的LWE问题的困难性与解决任意选择密钥S的LWE问题 的困难性相同.这意味着解决SLWE问题的困难性与解决与之相对应LWE问题的 困难性相同.RLWE问题的情形与之 相似,如果能够解决密钥元素比较小的环上的LWE问题,那么也能解决对应的 LWE问题.

我们进一步将此问题扩展到矩阵的形式.

令为F_q上的概率分布,此分布通过以下方式获得,任意选择一个 n×n矩阵A,阵A的元素属于F_q,任意选择n×n矩阵e,e的元素属于F_q且服从 分布例如,每个元素分别按照错误分布κ任意选择.输出(A,A×S+e), 其中+指的是上的加法.一个解决关于q和错误分布的LWE问题的算法, 如果对任意的n×n矩阵和为任意独立样本,以很高的概率输出为S.

我们记矩阵形式的LWE问题为(MLWE).如果S的元素较小,S的元素独立地 按照错误分布选择,我们称之为小矩阵MLWE问题,记为(SMLWE).如果A为 对称矩阵,称为小对称MLWE问题,记为SSLWE.如果秘密矩阵S的元素是从 -z,…,0,1,…,z(z是小正整数)中任意独立地选择的,称为均匀小MLWE问题,记 为USMLWE.所谓MLWE问题可以看成n个LWE问题的叠加,然后以矩阵形式共享 密钥.因此它与对应的LWE问题的困难性相当.

对于S和e元素的选择,我们可以选择不同的分布.

我们的设计的一个数学原理是矩阵乘法的结合律，即对矩阵A,B,C,有

A×B×C＝(A×B)×C＝A×(B×C).

从数学的角度，这可看成双线性对——矩阵A得行向量与矩阵C的列向量的双线 性对的计算.

对于以某种错误分布选择的元素较小的矩阵A和B,我们不是直接相乘, 而是按以下步骤计算,首先计算

AB+E_a,

然后计算

(AB+E_A)C或者(AB+E_A)C+E_AC,

或者计算

BC+E_C,

最后计算

A(BC+E_C)或者(AB+E_A)C+E_BC,

其中E_A,E_B,E_AC,E_BC是元素较小的矩阵,选择矩阵的错误分布可以相同也可以 不同.于是,我们有两种不同的方式计算矩阵乘法ABC,计算时有些错误.我们 称此为有错配对计算.我们的所有设计都基于有错配对和这样的事实——即如 果A和C的元素较小,那么任意两个不同的对相近.

我们可以证明MLWE问题的困难性与对应的LWE问题的困难性相同。这是 我们的设计可证明安全性的基础.

1.2基于有错配对的新的密钥交换系统的设计

在开放的通信信道中,Alice(A)和Bob(B)决定交换密钥.这意味着 通信信道对任何人开放,包括恶意的攻击者.为简便起见,我们假设本节中的 所有矩阵都是n×n方阵.实际应用时,所选的矩阵不必是方阵,但必须保证 所选矩阵可以相乘.

密钥交换的详细步骤.

(1)Alice和Bob首先公开选取F_q,n和在F_q上的任意矩阵M,其中q是关 于n的多项式,例如

q≈n³,错误分布是关于F_q上的n×n矩阵的错误分布,例如每一个部 分错误分布与LWE情形时的离散错误分布κ_σ相似,即F_q上的中心为零方 差为的离散正态分布.再选择并公开小素数t(t＜＜n).

(2)双方按照错误分布选择n×n密钥矩阵S_i(i＝A,B)和e_i.

Alice计算

M_A＝MS_A+te_A

其中t是小整数(t＜＜n).

Bob计算

M_B＝M^tS_B+te_B.

(3)双方在开放信道中交换矩阵M_i.这意味着M_i(i＝A,B)是公开的,但S_i和e_i(i＝A,B)是保密的.

(4)Alice计算:

$K_A=S_A^t\times M_B=S_A^t{M}^t{S}_B+t{S}_A^t{e}_B.$

Bob计算:

$K_B=M_A^t\times S_B=S_A^t{M}^t{S}_B+t{e}_A^t{S}_B.$

(5)双方运用舍入技术获得共享密钥:

(a)Bob将K_B在[-(q-1)/4,(q-1)/4]中的元素的位置列出,记为T₁, 将K_B不在

[-(q-1)/4,(q-1)/4]中的元素的位置列出,记为T₂.然后将表T₁发送给Alice.

(b)对表T₁的数,双方都计算它们除以t的余数；对表T₂的数,加上 (q-1)/2后计算它们除以q的余数,然后再模t这样双方可以 得到共享密钥.

Alice和Bob可以通过K_A,K_B和舍入技术交换密钥的原因在于:e_i和S_i的 元素较小,从而导致K_A,K_B相近.我们称这样的密钥交换系统为SMLWE密钥交 换协议.我们还可以证明这个有效的系统的安全性[Dili].

从通信和计算效率的角度,本系统表现相当出色.双方只需要交换F_q上的 n²个元素,利用Strassen快速矩阵乘法进行大约2n^2.8次计算,得到n²位bit 输出(如果t＝2).

对于S和e元素的选择,我们可以选择不同的分布.

我们可以证明,如果选择相同的系统参数n和q和选择恰当的错误分布,矩 阵SLWE密钥交换协议是可证明安全的[DiLi].证明基于有错配对问题的困难 性.

假设给定

(1)n×n矩阵M,素数q,小正整数t,错误分布κ_n.

(2)

M′_A＝MS′_A+te_A,M′_B＝MS′_B+te_B,

其中e_i是n×1向量,其元素服从错误分布κ_n,S_i是n×1向量,其 元素服从相同的分布；

(3)已知

$K_B^{\prime }=M_A^t\times S_B^{\prime }={\left(S_A^{\prime }\right)}^t{M}^t{S}_B^{\prime }+t<e_A,S_B^{\prime }>$

是否属于[-(q-1)/4,(q-1)/4]；

我们的问题在于寻找一个算法得到:

K′_A＝(S′_A)^t×M_B＝(S′_A)^tM^tS′_B+t<S′_A,e_B>

其中,如果K′_B的元素属于[-(q-1)/4,(q-1)/4]时,模t.否则K′_A+(q- 1)/2首先模q,然后再模t.我们称这样的问题为有错配对问题(PEP).

安全性证明基于以下事实:SMLWE问题的困难性与SLWE问题相同.事实上 矩阵版本的SLWE问题实例可看为一组SLWE问题的叠加.

我们指出,如果选择的矩阵对乘法运算相容,那么可以选择长方矩阵设计 系统,但是必须选择恰当的参数确保系统安全.

同理,根据文献[LNV]对RLWE问题的描述,我们可以建立基于环错误问题 的密钥交换系统(RLWE)[LPR].

对RLWE问题,我们考虑环其中f(x)是上的n次多项式,为整环,q是素数.若q是奇素数,则的 元素表示为-(q-1)/2,...,-1,0,1,..,(q-1)/2,即可看成的元素.的元素 可以表示为n-1次单变量多项式,或该多项式系数向量.对的元素

a(x)＝a₀+a₁x+…+a_n-1x^n-1,

定义向量(a₀,a₁…,a_n-1)的范数l_∞为:

‖a‖＝max|a_i|.

向量(a₀,a₁…,a_n-1)可以看成的元素,a_i可看成的元素.经过微小的修改, q为偶数的情形与奇数的情形相似.

RLWE_f,q,χ问题的参数为:次数为n的多项式f(x),素数q,上的错误分 布χ.

RLWE_f,q,χ问题定义如下.

RLWE_f,q,χ问题就是给定任意多项式实例

(a_i,b_i＝a_i×s+e_i),

求的元素s的值.其中e_i的选择服从错误分布χ.

RLWE_f,q,χ问题的困难性基于b_i在计算上的不可区分性.可以证明解决 RLWE_f,q,χ问题可归结为用量子计算机解决相关参数的短向量问题.我们相信即 使是量子计算机,解决某些格问题的复杂度是指数的.

根据文献[ACPS]和[LPR],RLWE_f,q,χ问题等价于一个变种,在这个变种中, s的选择服从错误分布χ,而不是从中任意选择,错误元素e_i乘以某个小整数 t.

为了可证明安全性,我们需要考虑RLWE问题的特殊参数选择.

(1)我们选择f(x)为割圆多项式xⁿ+1,其中n＝2^u；

(2)错误分布χ是离散的高斯分布其中

(3)q＝1(mod 2n),q是关于n的多项式,q≈n³；

(4)t是小素数且t<<n<<q.

对于某些特别的应用,我们也可以选取其他特殊的参数.

在密钥交换系统RLWE_f,q,χ中,有两个必不可少的要素,

(1)向量在标准差为σ的离散高斯分布的长度的上界为σn,即对分布χ的 任意样本,有

Pr(‖X‖)>σn)≤2^-n+1.

(2)环上的乘法被界定在合理的范围内,即对有

‖X×Y(mod f(x))‖≤n‖X‖‖Y‖,

其中范数l_∞定义如上.

RLWE_f,q,χ系统环境如上,Alice(A)和Bob(B)在开放信道交换信 息步骤如下:

(1)Alice和Bob首先公开RLWE_f,q,χ的所有参数:q(≈n³或者关于n 的多项式)、n、

f(x)、χ.并公开从中任意选择的元素M.

(2)双方按照错误分布选择自己的密钥s_i∈R_q,按照错误分布独立选择 e_i∈R_q,但是加入一个小素数t(t<<n)Alice计算,

M_A＝S_A M+te_A

其中t是小素数(t＜＜n).

Bob计算

M_B＝S_BM+te_B.

(3)双方交换M_i.这意味着M_i是公开的,但s_i和e_i必须保密.

(4)Alice计算:

K_A＝S_A×M_B＝S_A MS_B+te_BS_B.

Bob计算:

K_B＝M_A×S_B＝S_A MS_B+te_AS_B.

(5)双方应用舍入(rounding)技术共享密钥,具体过程如下:

(a)Bob建立一张长为n的表,表格由(i,j)组成,其中i＝0,…,n-1, 如果K_B的xⁱ的系数在集合[-(q-1)/4,(q-1)/4]中,那么 j＝1,否则,j＝0.

(b)Bob将建立的表格发送给Alice.双方计算表格(i,j)元素对应 K_A和K_B的元素除以t的余数如下:

1)如果j＝1,则分别计算K_A和K_B第i个元素模t；

2)如果j＝0,则K_A和K_B第i个元素首先加上(q-1)/2,然 后模q,使得第i个元素在集合[-(q-1)/4,(q-1)/4之中,最 后模t.

S_i和e_i可以使用不同的分布.

这样双方可以共享密钥.我们称此系统为RLWE密钥交换系统.此系统可 以将密钥交换失败的概率降到很低.环的交换律和结合律对本系统的设计 十分重要.

在安全性分析方面,于环上的PEP相似,本系统是可证明安全的.

假设给定

·M∈R_q,素数t,q和错误分布χ,分布参数与RLWE_f,q,χ相同；

·$M_A=M_{S_A}+t_{e_A}$和$M_B=M_{S_B}+t_{e_B},$其中e_i和s_i服从错误分布χ；

·已知K_B＝M_A×S_B＝S_A MS_B+te_AS_B的x_i的系数是否在 [-(q-1)/4,(q-1)/4]之中；

环上的有错配对的问题(RPE),即找到某种算法以高概率计算K_B(或K_A)模 t或者K_B+(q-1)/2(或K_A+(q-1)/2)模q再模t.

基于RLWE_f,q,χ问题的困难性的RLWE密钥交换系统是可证明安全的,证 明方法与SLWE密钥交换系统相似.

对相同的参数q和n本系统十分有效,因为可以用环上FFT型算 法快速进行乘法运算.

1.3基于有错配对的新的密钥分配系统的设计

在大型网络中,怎样给合法的用户分配密钥是一个关键的问题.通常,建 立一个真正有效且可扩展的密钥分配系统是十分困难的.例如,在文献[BSHKVY] 中提出的密钥分配系统,本质上,中心服务器的主密钥是一个n×n对称矩阵M, 用户的认证可以看成n个元素的行向量H_i.中心服务器给每个用户一个密钥 H_i×M.两个用户之间可获得共享密钥M的对称性质使得

$.H_i\times M\times H_j^t=H_j^t\times M\times H_i.$

但是,大量的用户可以合作,从而获得主密钥.如果敌手能够收集到足够多(n 个)的H_i×M.那么敌手也能得到主密钥M,从而将系统攻破.

我们可以建立一个基于有错配对的真正可扩展的密钥分配系统,此系统可 看成是以上方法与LWE思想的综合.

本系统建立在有限域F_q上,其中F_q的元素可以表示为-(q- 1)/2,...,0,...,(q-1)/2.令q≈n^3或者q是其他关于n的相似多项式函 数,令是n×n矩阵空间上的错误分布.例如,每个部分都服从κ_σ分 布的联合分布,其中κ_σ为前述LWE中的离散分布,即期望为0,标准差约为n 的离散正态分布.当然,分布的参数可以更改.

密钥分配系统建立步骤如下.

(1)中央服务器选择一个主密钥n×n矩阵S,矩阵的元素属于F_q,且

S＝S^t.

(2)对每个用户i,中央服务器分配一个矩阵A_i(通常非对称)作为用户ID 矩阵,矩阵A_i服从错误分布ID矩阵是公开的,它也可以由用户可 以唯一识别的信息,如电子邮箱、姓名等生成.

(3)对每个用户,服务器分配一个安全的密钥:

E_i＝A_iS+te_i,

其中e_i是一个非对称矩阵且服从错误分布

两个用户i和j想获得共享密钥,用户i计算

$K_i=E_i\times A_j^t=A_{i}S{A}_j^t+{\mathrm{te}}_i{A}_j^t;$

用户j计算

$K_j=A_i\times {\left(E_j\right)}^t=A_i{S}^t{A}_j^t+{\mathrm{tA}}_i{e}_j^t=A_{i}S{A}_j^t+{\mathrm{tA}}_i{e}_j^t.$

此步骤是可行的,因为ID矩阵是公开的.可以通过以下步骤获得共享密钥.

·当用户j想和用户i建立共享密钥时,用户j选出K_j在集合 (-(q-1)/4,(q-1)/4)中的所有元素,包括它们在矩阵的位置,并且,在集 合中的元素标记为1,不在集合中的元素标记为0.然后用户j把这些元素的位 置(不发送元素值)以表格的形式发送给用户i,用户i按照接收到的表格，从自 己的矩阵E_i×A_i中选出表格对应位置的元素.于是用户i和j拥有了同一 张表格,即矩阵元素的位置,从而也可以知道自己的矩阵中对应的元素.对于 标记为1的元素,双方计算对应元素除以t的余数；对于标记为0的元素,双 方用该元素加上(q-1)/2后再模t.从而得到共享密钥.

由于S是对称矩阵,我们有

$A_i{\mathrm{SA}}_j^t=A_i{S}^t{A}_j^t,$

因而对用户j,可得

$A_i{\mathrm{SA}}_j^t+t{A}_i{e}_j^t.$

两个用户计算上的不同点在于:

$\left(\begin{array}{c}{E}_i\times A_j^t-A_i\times E_j^t\\ =A_i{\mathrm{SA}}_j^t+{\mathrm{te}}_i{A}_j^t-(A_i{\mathrm{SA}}_j^t+{\mathrm{tA}}_i{e}_j^t)\\ ={\mathrm{te}}_i{A}_j^t-{\mathrm{tA}}_i{e}_j^t.\end{array}\right)$

两者的不同是很小的,这是因为t是很小的,且和也是很小的, 事实上e_i,e_j A_i和A_j全是很小的.再通过舍入技术,我们能够给用户i和j 共同的密钥,从而建立密钥分配系统.

因为矩阵te_iA_j和的错误项是很小的,A_iSA_j中标记为1的元素几 乎全部属于[-(q-1)/4,(q-1)/4].因而错误项不会导致A_iSA_j的元素值超出 (-(q-1)/2或(q-1)/2),即加上错误项后,我们仍然不需要模q元素. 标记为0的情况也一样.这就确保双方可以共享密钥.

从K_i,K_j的构造可知,K_i和K_j的元素服从均匀分布.用户j每次根据 矩阵K_j构造的表格长度达n².因而如果适当选择n,本系统能提供足够的共 享密钥位.

当然,我们也可以构造非对称矩阵情形的密钥分配系统,此时,服务器需 要多计算一些矩阵,如A_iS+e和因此,非对称矩阵情形的密钥 分配系统效率没有对称的情形高.

另一方面,因为RLWE问题可以看成基于矩阵的LWE的特殊版本,所以我们 可以用相同的方式通过RLWE建立密钥分配系统.

我们接下来研究本密钥分配系统为何可以扩展的.显然,每个用户都有A_i和E_i＝A_iS+te_i对,许多用户通过合作可以得到许多对,恢复主密钥矩阵S就 是要解决对应的MLWE问题,但是,主密钥矩阵S为对称矩阵的情况除外.因 为给定一个LWE问题,通过对称矩阵,我们可以将它转化为MLWE问题,所以不 难证明MLWE问题于LWE问题的困难性相同.所以本系统是可扩展的.

在本系统的安全性证明方面,与文献[DiLi]的证明方法相似,我们也可以 证明本系统是安全的.

综上所述,因为RLWE可以看成特殊的MLWE,所以我们可以利用RLWE建 立十分简单的密钥分配系统.

我们首先选择环为了保障系统的可证明安全性, 我们必须恰当的选择参数n,q,例如,n＝2^k,q＝1mod(2n)[LPR].对于本 系统的可证明安全性,我们按照文献[LPR]来设置参数和错误分布χ.

本设计基于前面的系统.假设我们定义了一个环R_q,且环服从错误分布χ, 则环R_q上的错误学习问题定义如下:

给定对(A,E),其中

E＝A×S+te′,

e′的元素属于R且服从错误分布χ,t是小整数,S是固定元素,A是任意 选择的.环R_q上的错误学习问题就是求S的问题.

对中央服务器,我们建立简单的密钥分配系统如下.

(1)中央服务器按照均匀分布从R_q中任意选择M.

(2)对每个用户,中央服务器分配一个公开的ID A_i,其中A_i是R_q的小元 素,即服从错误分布χ.

(3)中央服务器给每个用户一个密钥:

S_i＝MA_i+te_i

其中e_i服从错误分布χ.

(4)如果用户i和j试图建立共享密钥,那么用户i可以用自身的密钥和 用户j的ID矩阵A_i与用户j建立共享密钥,为此,用户i计算

K_i＝A_j×S_i＝A_jMA_i+tA_je_i

用户j计算

K_j＝A_i×S_j＝A_jMA_i+tA_ie_j

应用舍入技术,共享密钥可通过以下方式获得:

(a)用户i建立一个长为n的表,表由对(a,b)组成,其中a＝0,...,n- 1,如果K_i中x^a的系数在集合[-(q-1)/4,(q-1)/4里,那么 b＝1,否则b＝0.

(b)用户i将上一步建立的表发送给用户j.对表中的元素(a,b),双方计 算表中的元素对应的K_i中的元素模t的值如下:

1)如果b＝1,双方分别计算K_i和K_j的第a个元素模t的值；

2)如果$＝0,K_i和K_j的第a个元素首先加上(q-1)/2,然后模 q,使其在[-(q-1)/4,(q-1)/4中,最后将所得值模t；

因为A_i是e_i环R_q中的小元素,所以A_i×e_i仍然是小的.这就保证可 以得到共享密钥并建立密钥分配系统.

在密钥分配的整个过程中,我们经常用到这样的一个事实:RLWE问题的 乘法可交换.

我们构造的系统的特点是:简单,直接.它的安全性证明也是显然的.

1.4基于有错配对的基于身份加密系统的设计

我们首先建立基于MLWE的公钥加密系统.为了建立加密系统,我们选择 的参数如前述,q≈n³或n⁴或其它关于n的多项式,错误分布为例如, 每个部分都服从κ_σ分布的联合分布,其中κ_σ为前述LWE中的离散分布,即期望 为0,标准差约为的离散正态分布,为了方便证明安全性,我们也可以选择 高维高斯正态分布.当然,分布的参数可以更改.

选择这些参数后,与MLWE情形相似,我们可以建立加密系统,步骤如 下:

(1)选择n×n矩阵S,使得S的元素服从错误分布例如,S的每个元 素依据分布κ_σ独立地任意地选择.

(2)在MLWE环境下,我们可以得到一对输出(A,E),其中

E＝A×S+e,或E＝A×S+te,

且t是小整数,t<<n,这对输出(A,E)就是系统的公钥,其中e服从某 种错误分布,例如前述分布.

(3)S是系统的私钥.

(4)消息m用n×n矩阵表示,矩阵的元素为0,1或者模t的剩余类环 0,1,...,t-1.

(5)发送者选择一个n×n矩阵B,矩阵B的选法与S相同,即服从错误分 布例如,B的每个元素依据分布κ_σ独立地任意地选择.发送者加密 信息如下:

(D₁,D₂)＝(B×A+e₁,B×E+e₂+m(q/2)),

(D₁,D₂)＝(B×A+te₁,B×E+te₂+m),

其中e₁和e₂是错误矩阵,它们的选择方式与e相同,即按照某错误分布 独立地任意地选择.

(6)合法的解密者解密信息如下:计算

$D_2-D_1\times S=(\mathrm{BE}+e_2+m\left(\frac{q}{2}\right)-(\mathrm{BA}+e_1)S)=\mathrm{eE}+e_2-e_{1}S+m\left(\frac{q}{2}\right),$

其中每一个运算都在F_q中进行,矩阵的元素如果接近0,则输出0；如 果接近(q-1)/2,则输出1；或者按照实数域上的除法,将矩阵元素除 以(q-1)/2,然后四舍五入输出0或1.最后的输出就是明文$m$；在第 二种情况下,合法解密者计算

D₂-D₁×S＝(BE+te₂+m-(BA+e₁)S)＝teE+te₂-te₁S+m,

然后模t.这样可得到明文m.

A,B,e_i可以选择不同的分布.

对大数n,解密成功的概率很高,原因如下:

$\left(\begin{array}{c}{D}_2-D_1\times S\\ =(\mathrm{BE}+e_2+m\left(\frac{q}{2}\right)-(\mathrm{BA}+e_1)S)\\ =B(\mathrm{AS}+e)+e_2+m\left(\frac{q}{2}\right)-(\mathrm{BA}+e_1)S\\ =\mathrm{Be}+e_2-e_{1}S+m\left(\frac{q}{2}\right),\end{array}\right)$

Be+e₂-e₁S可以看成错误项,它由任意变量的分布决定.与KE或KD系统的 情况相似,如果选择恰当的参数,那么解密成功,我们将得到长为n的明文. 第二种情形与此相似.

本加密系统的一大亮点在于位加密速度极快,因为在加密解密过程中,我 们可以用快速矩阵乘法[CW].

必须指出,矩阵乘法不可交换,所以两个元素相乘时,相乘顺序是十分重 要的,这一点与RLWE相关系统不同.

我们也可以类似地建立环上的LWE的加密系统(RLWE)[LPR],所有元素都 在环R_q中.于是有

E＝A×S+te,

其中,t是小正整数,S服从错误分布因为

D₂-D₁×S

＝BE+te₂+m-(BA+t₁e₁)S

＝B(AS+te)+te₂+m-(BA+te₁)S

＝tBe+te₂-te₁S+m,

所以加密如下:

(D₁,D₂)＝(B×A+te₁,B×E+te₂+m).

解密如下:

(BE+te₂+m-B(AS+te₁))(mod t).

因为错误项模t后是很小的所以我们可以得到明文.

对于MLWE问题,我们根据需要选择分布,使得系统是可证明安全的.

目前,有一些基于格相关问题(包括LWE问题)的基于身份的加密系统 [ABB],[ABVVW],[BKPW].但是这些系统都是十分复杂的.我们可以利用MLWE建 立基于身份的加密系统.

我们建立一个简单的基于身份的加密系统如下.

(1)中央服务器首先选择一个n×n矩阵S作为主密钥,其中S的元素是小的 并服从错误分布这与密钥交换系统和密钥分配系统相似.

(2)中央服务器任意选择一个可逆矩阵M,其中M服从均匀分布或相似的分 布.如果q足够大,那么M可逆的概率就很大,从而我们可以很容易找 的这样的可逆矩阵.然后中央服务器计算

M₁＝MS+te,

其中e的元素很小,并服从错误分布

(3)中央服务器公开M和M₁作为公钥.

(4)对每一个用户,中央服务器分配一个ID矩阵A_i,其中A_i的元素是小的 并服从错误分布它可以由能够识别用户的信息生成.

(5)分配给每个用户一个密钥:

S_i＝SA_i+tM^-1e_i,

其中e_i的元素是小的并服从错误分布κ.诚然,这相当于给定

MS_i＝MSA_i+te_i,

因为M是公开的.

(7)由于任何人都可以利用ID矩阵A_i,故中央服务器可以为拥有ID矩阵A_i的 用户建立新公钥(A_i,B_i),其中

A_i＝M,

B_i＝M₁A_i＝MSA_i+teA_i,

利用此公钥和MLWE加密系统就可以加密任何信息.

此即为矩阵上的基于身份的加密系统.

S,A_i,e_i,e可以服从不同的分布.

因为A_i和e的元素是小的,所以A_i×e的元素也是小的.此外我们还有

MS_i-B_i

＝M(SA_i+tM^-1e_i)-MSA_i-teA_i

＝MSA_i+tMM^-1e_i-MSA_i-teA_i

＝te_i-teA_i,

因为S,A_i,e_i的元素是小的,所以e_i-eA_i和te_i-teA_i的元素也是小的.因此, 对于MLWE问题的输入对(A_i,B_i),S_i是MLWE问题的解.所以S_i是密钥,从而可以 用来加密.最后,我们必须选择恰当的参数确保系统安全.

本系统的特点是简单,直观.其安全性证明也是显然的.

我们可以将此设计扩展到RLWE问题.我们选择环F_q[x]/(xⁿ+1).为了确 保安全性,我们必须选择恰当的参数,如n＝2^k,q＝1mod(2n)[LPR].当然 我们也可以选择其他参数.

这个设计直接依赖于RLWE加密系统[LPR],即我们有一个环R,在环上恰 当定义错误学习问题如下:

对给定的对(A,E),其中E＝AS+te′,A,S,e′的元素属于R_q且服从错误分布χ, t是小正整数,S是固定的,A服从均匀分布,关于环R的错误学习问题就是求等 式E＝AS+te′,的解的问题.如前所述,我们可以利用RLWE问题[LPR]建立公 钥加密系统,其中A和E是公钥,S是私钥,S的元素是小的.我们可以利 用环LWE问题上的乘法是可交换的这一事实.

我们建立简单的基于身份的加密系统如下.

(1)中央服务器首先从R中选择S作为主密钥,其中S的元素是小的且服 从错误分布χ.

(2)中央服务器任意选择一个可逆矩阵M,其中M服从均匀分布或相似的分 布.如果q足够大,那么M可逆的概率就很大,从而我们可以很容易找 的这样的可逆矩阵.然后中央服务器计算

M₁＝MS+te,

其中e的元素很小,并服从错误分布χ.

(3)中央服务器公开M和M₁作为公钥.

(4)对每一个用户,中央服务器分配一个ID矩阵A_i,其中A_i的元素是R_q中的小元素并服从错误分布χ.

(5)分配给每个用户一个密钥:

S_i＝SA_i+tM^-1e_i,

其中e_i的元素是R中的小元素并服从错误分布χ.诚然,这相当于给定

MS_i＝MSA_i+te_i,

因为M是公开的.

(6)由于任何人都可以利用ID矩阵A_i,故中央服务器可以为拥有ID矩阵 A_i的用户建立新公钥建立新公钥(A_i,B_i),其中

A_i＝M,

B_i＝M₁A_i＝MSA_i+teA_i,

利用此公钥和MLWE加密系统就可以加密任何信息.

此即为环上的基于身份的加密系统.

S,A_i,e,e_i可以选择不同的分布.

因为A_i和e的元素是R中的小元素,所以A_i的元素也是R中的小元素. 又由于环是交换环,我们有

S_iA_i-B＝S_iM-B_i

＝M(SA_i+tM^-1e_i)-MSA_i-A_ite

＝MSA_i+tMM^-1e_i-MSA_i-A_ite

＝te-tA_ie_i,

所以e_i-eA_i和te_i-teA_i的元素也是小的.因此,对于MLWE问题的输入对 (A_i,B_i),S_i是MLWE问题的解.所以S_i是密钥,从而可以用来加密.最后,我们 必须选择恰当的参数确保系统安全.

我们可以用相同的方法建立一个分层的IBE系统,每个用户可以作为一个 中央服务器.

本系统的特点是简单,直接,高效.安全性证明也是显然的.

在上述建立在环的的有错配对的系统,可以用如下形式的多项式:

f(x)＝∏f_i(x)+g(x),

其中fi,g(x)是极其稀疏的,只包括少数非零项,如2或3个非零项.

利用此类多项式可以提高加密和解密的计算速度.

引用

[ABB]

S.Agrawal,D.Boneh,X.Boyen:Efficient Lattice(H)IBE in the Standard  Model.In proceedings of Eurocrypt 2010,Lecture Notes in Computer Science, Volume 6110,pp.553-572,2010.

[ABVVW]S.Agrawal,X.Boyen,V.Vaikuntanathan,P.Voulgaris,H.Wee: Fuzzy Identity Based Encryption from Lattices.IACR Cryptology ePrint  Archive 2011:414(2011)

[ACPS]B.Applebaum,D.Cash,C.Peikert,A.Sahai；Fast Cryptographic  Primitives and Circular-Secure Encryption Based on Hard Learning Problems. Advances in Cryptology-CRYPTO 2009,Lecture Notes in Computer Science, Volume 5677pp 595-618,2009

[BKPW]M.Bellare,E.Kiltz,C.Peikert,B.Waters:Identity-Based (Lossy)Trapdoor Functions and Applications.In Proceedings of EUROCRYPT 2012,Lecture Notes in Computer Science,Volume 7237,pp 228-2452012.

[BSHKVY]C.Blundo,A.De Santis,A.Herzberg,S.Kutten,U.Vaccaro,M. Yung:Perfectly-Secure Key Distribution for Dynamic Conferences.in  Advances in Cryptology--Crypto 92,Lecture Notes in Computer Science, Volume 740,pp 471-486,1993

[BKW]A.Blum,A.Kalai,and H.Wasserman.Noise-tolerant learning,the  parity problem,

and the statistical query model.Journal of the ACM,50(4),pp506-19, 2003.

[COPP]D.Coppersmith,Shmuel Winograd,Matrix multiplication via  arithmetic progressions,Journal of Symbolic Computation-Special issue  on computational algebraic complexity archive 9(3),pp 251-280,1990

[DiHe]W.Diffie,M.Hellman,New directions in cryptography,IEEE  Transactions on Information Theory 22(6),pp 644-54,1976.

[DiLi]J.Ding,X.Lin,A Simple Provably Secure Key Exchange Scheme Based  on the Learning with Errors Problem,Cryptology ePrint Archive,Report 688,2012[LNV]K.Lauter,M.Naehrig,V.Vaikuntanathan,Can  Homomorphic Encryption be Practical？,Cryptology ePrint Archive,Report 2011/405,2011,http://eprint.iacr.org,

[LPR]V.Lyubashevsky,C.Peikert,O.Regev,On ideal lattices and  learning with errors over rings  In Eurocrypt 2010

[REGEV]O.Regev,On lattices,learning with errors,random linear  codes,and cryptography,in Proceedings of the 37th Annual ACM Symposium  on Theory of Computing–STOC 05,ACM,pp 84-93,2005

[SHA]A.Shamir,Identity-based cryptosystems and signature schemes,in  Advances in Cryptology--Crypto'84,Lecture Notes in Computer Science, Vol.196,Springer-Verlag,pp.47-53,1984

[SHO]P.Shor,Polynomial-time algorithms for prime factorization and  discrete logarithms on a quantum computer,SIAM Journal of Computing 26, pp.1484-1509,1997.

[STR]V.Strassen,Gaussian Elimination is not Optimal,Numer.Math.13, p.354-356,1969