基于RLWE困难假设的NTRU型代理重加密方案*

王 超,韩益亮,段晓巍,李 鱼

武警工程大学 密码工程学院,西安 710086

1 引言

大数据时代的到来、云计算的飞速发展以及数据平台跨域联合体系的构建,对云安全提出了更高层次的需求,单一的公钥加密体制难以满足大数据云安全的发展需要.随着代理重加密的出现,半可信代理作为中间方,对密文数据进行代理转换,有效解决了电子文件安全分发、跨域信息传输、云数据安全存储等问题.近年来,量子算法深入发展,给基于传统数学困难问题的密码体制带来了不可忽视的威胁,因此,对抗量子算法攻击的实用化后量子密码算法的需求日渐迫切.NTRU(number theory research unit)作为格密码中最实用的密码体制,在NIST后量子密码算法标准化第三轮的评估中成功胜出,预示着NTRU有望成为标准化的实用后量子密码算法.自2015年Nuñez提出第一个基于NTRU的代理重加密方案[1]以来,其密钥尺寸小、结构简洁、计算高效的优势有效推动了实用化后量子代理重加密算法的研究发展.

1996年,Hoffstein、Silverman和Pipher提出了NTRU公钥加密体制[2],该体制基于NTRU格上的NTRU假设,虽然自提出至今还没有有效的攻击算法对此假设产生威胁,但该假设一直未能归约到格上的经典困难问题,导致NTRU密码体制长期缺乏形式化的安全性证明[3].2011年,Stehlé和Steinfeld[4]将私钥采样自格上的离散高斯分布提出了一个可证明安全的NTRU变体,其IND-CPA安全性可以归约为RLWE困难问题,但是该方案对标准差参数要求过大,导致效率较低且实用性较差.2016年,NIST征集后量子密码标准化算法以来,在第二轮评估中成功入围公钥加密算法的NTRU密码体制共有两个:NTRU[5](NTRUEncrypt[6]与NTRU-HRSS[7]的结合版)和NTRU-Prime[8],其中NTRU成为第三轮评估中成功入围仅留的4个密钥封装(key encapsulation mechanism,KEM)算法之一,但以上三个方案中核心的公钥加密(public key encryption,PKE)算法,都未能归约到格上困难问题并提供严格的形式化安全性证明,仅能达到OW-CPA安全.2019年,Seck等[9]提出一种新型可证明安全的NTRU公钥加密变体BI-NTRU-LPR,该方案是继Stehle和Steinfeld对NTRU公钥体制的安全性进行形式化归约之后,对NTRU公钥体制进行形式化安全性证明的最新尝试,将私钥和随机多项式分别采样自多项式环和RLWE(ring learning with errors)噪声分布,最终将方案的IND-CPA安全性归约到D-RLWE问题.

自2010年Xagawa[10]首次在格上构造了代理重加密方案以来,基于格的代理重加密体制逐渐代替基于传统困难问题的代理重加密体制,成为研究的热点问题.围绕Xagawa方案双向且不抗合谋以及如何使格基代理重加密方案更加实用化的问题,基于格的单一代理重加密方案[11-13]和与身份、属性、条件、门限、区块链等相结合的代理重加密方案[14-18]相继被提出.目前基于格的代理重加密方案大都基于LWE困难假设,密钥采样算法为格上的高斯采样算法或陷门生成算法采样,其矩阵形式的密钥尺寸较大、方案计算复杂度较高.而基于RLWE困难假设中的多项式环和错误分布采样密钥可以有效解决密钥尺寸大的问题,另外通过快速傅里叶变换算法(fast Fourier transform,FFT)加速多项式乘法可以有效提升计算效率,降低计算复杂度.NTRU作为格密码中最实用的密码体制,随着其IND-CPA安全性在RLWE困难假设下得到证明,基于可证明安全的NTRU变体构造密钥尺寸小、实用性强的格基代理重加密体制具有重要的意义.2015年,Nuñez首次提出了两个基于NTRU的代理重加密方案[1]—NTRUReEncrypt和PS-NTRUReEncrypt,其中PS-NTRUReEncrypt方案在RLWE困难性假设下可以达到IND-CPA安全,但两个方案都是双向且不抗合谋的.2017年,Nuñez等[19]总结了经典的格基代理重加密方案并给出了方案性能对比,在对比中NTRU代理重加密方案[1]较LWE型方案具有更实用的密钥尺寸和计算复杂度优势.2017年,Polyakov等[20]基于NTRU-RLWE和BV同态加密方案在RLWE困难假设下,提出两个IND-CPA安全的单向抗合谋的代理重加密方案—NTRU-ABD-PRE和BV-PRE.2019年,张明武等[21]基于NTRUReEncrypt方案重新设计了重加密密钥生成算法,提出了一个单向抗合谋的NTRU代理重加密方案,但该方案未能在格困难问题假设下进行形式化的安全性归约.

本文主要研究NTRU公钥和代理密码体制的可证明安全性,构造IND-CPA安全的单向抗合谋的高效代理重加密方案.首先改进BI-NTRU-LPR公钥加密方案,将双密钥结构简化为单密钥结构,设计一种在RLWE困难假设下达到IND-CPA安全的公钥加密方案.结合文献[21]提出的抗合谋重加密密钥算法,构造出标准模型下可证明安全的单向抗合谋代理重加密方案.本文方案进一步完善了NTRU代理密码体制,与已有的NTRU代理重加密方案相比,既保证了单向抗合谋的安全属性又保证了方案的可证明安全性,且没有增加计算复杂度和密钥尺寸.与基于LWE的代理重加密方案相比,计算复杂度和密钥尺寸更小,实用性更强.

2 相关知识

2.1 RLWE

RLWE分布:定义整系数多项式环为R=Z(x)/x n+1,其中n∈Z为2的幂次方,设R q=Zq(x)/x n+1是模为素整数q的多项式商环.在R q上随机均匀选取多项式向量a和秘密值s,在χq上随机均匀选取错误向量e,χq在R q上服从某种公开的特定分布,令b=as+e,则(a,b)为R q×R q上的RLWE分布A s,χ.

RLWE判定问题(D-RLWE):给定样本分布(a,b),能否以不可忽略的优势区分(a,b)为RLWE分布A s,χ和R q×R q上的随机均匀分布.

2.2 单向代理重加密的系统定义

定义1根据文献[21]可知一个单向代理重加密方案由授权者、代理者和被授权者等三个参与方和以下五个算法组成.

(1)初始化阶段Setup(k):输入安全参数k,输出公共参数pp.

(2)密钥生成算法KeyGen(pp):输入公共参数pp,利用密钥生成算法为用户i生成公钥pki和私钥ski.

(3)加密算法Encrypt(pki,m):输入授权者i的公钥pki和明文m,输出密文C i.

(4)重加密密钥生成算法ReKeyGen(ski,pki,skj,pkj):输入授权者i和被授权者j的密钥ski,pki,skj,pkj,输出重加密密钥rki→j.

(5)重加密算法ReEncrypt(C i,rki→j):输入密文C i和重加密密钥rki→j,输出被授权者j可解密的重加密密文C j.

(6)解密算法Decrypt(C j,skj):输入重加密密文C j和被授权者j的私钥skj,输出明文m.

定义2单向代理重加密的正确性定义.

(1)对于密钥生成算法生成的任意密钥对(pki,skj)和明文空间中的任意明文m,都有下式成立:Decrypt(Encrypt(pki,m),ski)=m.

(2)对于重加密密钥生成算法生成的任意密钥rki→j和任意加密算法生成的密文C i以及任意明文m,都有下式成立:Decrypt(ReEncrypt(C i,rki→j),skj)=m.

2.3 单向代理重加密的IND-CPA安全模型

下面通过挑战者和攻击者Λ之间的安全游戏来定义本文方案的IND-CPA安全性,游戏共分为以下三个阶段.

初始阶段.挑战者将安全参数k输入Setup(),输出公共参数pp,并将公共参数pp发送给Λ,根据Λ是否知道用户的私钥信息,将用户分为诚实用户(HU)和腐化用户(CU).

学习阶段.攻击者Λ可以向挑战者发起任意多项式次以下查询

(1)私钥查询:Λ向挑战者发起私钥查询,若查询的用户为腐化用户,挑战者返回给Λ相应的用户私钥ski,否则返回终止符⊥.

(2)重加密密钥查询:Λ向挑战者发起用户i到用户j的重加密密钥查询,挑战者运行ReKeyGen算法得到重加密密钥rki→j,并将其返回给Λ.如果i=j或者用户i为诚实用户,用户j为腐化用户,则挑战者忽略Λ的请求,返回一个随机值.

(3)重加密查询:Λ向挑战者发起密文C i到密文C j的重加密查询,挑战者利用重加密密钥rki→j运行ReEncrypt算法得到重加密密文C j,并将其返回给Λ.如果i=j或者用户i为诚实用户,用户j为腐化用户,则挑战者忽略Λ的请求,返回一个随机值.

挑战阶段.当Λ认为学习阶段可以结束时,选择两个明文(m0,m1)和攻击目标用户i∗(要求i∗不能为腐化用户)并提交给挑战者,挑战者随机选择一个随机数d∈{0,1},然后返回用户i∗的加密密文C i∗=Encrypt(pki∗,m d)给Λ作为挑战密文.

Λ在收到挑战密文之后可以继续发起学习阶段中的私钥查询、重加密密钥查询、重加密查询,要求是不能针对用户i∗,挑战者应答的方式与上阶段一致.

猜测.最后Λ停止查询并输出一个猜测值d′∈{0,1},如果d′=d则宣布Λ获胜,其优势为:

如果对于任意多项式时间攻击者,攻击者的优势是可忽略的,则称基于NTRU的单向代理重加密方案是IND-CPA安全的.

2.4 符号说明

3 NTRU型公钥和代理重加密方案

3.1 NTRU公钥加密变体

在尝试基于BI-NTRU-LPR方案设计可证明安全的单向抗合谋代理重加密方案时,由于BI-NTRULPR方案的双密钥特性,使得该代理重加密方案的重加密密钥尺寸扩张为PS-NTRUReEncrypt方案的两倍,且重加密过程中噪声扩张严重,方案解密正确率无法达到PS-NTRUReEncrypt方案中的正确界限1−n−ω(·).为了减小密钥尺寸,实现低噪声的代理重加密方案的设计,在本小节中,设计了一个单密钥的IND-CPA安全的NTRU公钥加密变体NTRU-LPR,方案的安全性可以归约到D-RLWE困难问题,方案的加法运算为多项式加法,乘法运算为多项式卷积乘法.

(1)NTRU-LPR密钥生成算法(KeyGen):从L t上随机均匀的选取多项式B∈R q,从L t上随机选取小系数多项式g∈R q(系数取为0、1和−1),g满足以下两个条件:g q·g≡1(modq),g≡1(modp),如果g不满足条件则重新进行选取,从χq上随机选取小系数多项式e′∈R q,计算公钥pk为h=g q B+e′(modq),私钥sk为g.

(2)NTRU-LPR加密算法(Encrypt):输入公钥pk=h,从明文空间M中选取明文m,从χq上选取两个随机多项式u,e∈R q,计算密文C=p(uh+e)+m.

(3)NTRU-LPR解密算法(Decrypt):输入密文C和私钥sk=g,计算C′=C·g(modq),解密得m=C′(modp).

(4)NTRU-LPR公钥加密方案正确性分析:首先计算:

定理1当|puB+pue′g+peg+mg|∞

证明:当|puB+pue′g+peg+mg|∞

定理2根据文献[9]中引理3和引理4可知,在选择适当的参数t=3,αq≥n1/4,n3/2+3αqω(logn)pn1/2

3.2 NTRU型代理重加密方案

本节基于上节提出的NTRU-LPR公钥加密方案,结合文献[21]提出的重加密密钥生成算法,设计了一个基于NTRU的IND-CPA安全的单向抗合谋的代理重加密方案NTRU-LPR-ReEncrypt,具体方案如下:

(1)初始阶段(Setup):输入安全参数k,选取多项式环R q=R/q R=Zq(x)/x n+1,n为2的幂

(2)密钥生成算法(KeyGen):运行NTRU-LPR公钥加密方案的密钥生成算法,为授权者i生成一对密钥(pki,ski)=(h i,g i),为被授权者j生成一对密钥(pkj,skj)=(h j,g j).

(3)加密算法(Encrypt):输入授权者i的公钥h i和明文m,从χq选取随机多项式u,e i∈R q,计算密文C i=p(uh i+e i)+m(modq),并发送给代理者.

(4)重加密密钥生成算法(ReKeyGen):本算法基于文献[21]提出的NTRU重加密体制的抗合谋交互式重加密密钥生成算法.输入授权者i和被授权者j的私钥g i和g j,首先授权者从R q中选取一个随机多项式f,从χq中选择随机多项式e j,计算f′=f(g i+pe j)(modq)发送给被授权者j,并将f发送给代理者,被授权者j收到f′后,计算f′′=f′g j q(modq)并发送给代理者,代理者收到f和f′′后,计算重加密密钥rki→j为:

(5)重加密算法(ReEncrypt):代理者运行重加密密钥生成算法,输入授权者i的密文C i和重加密密钥rki→j,计算C j=C irki→j,将授权者i的密文C i转换为被授权者的密文C j,并将C j发送给被授权者j.

(6)解密算法(Decrypt):被授权者收到转换密文C j后,输入自己的私钥g j,计算m′=C j g j(modq),最终得明文为m=m′(modp).

4 安全性分析

本节对NTRU-LPR-ReEncrypt方案的正确性、单向性、多跳性和抗合谋性进行分析,在D-RLWE困难问题下对方案的IND-CPA安全性进行形式化的安全性证明.

4.1 正确性分析

本节从方案的输入面(授权者的解密正确性)和输出面(被授权者的解密正确性)两个方面进行分析.

(1)由于NTRU-LPR-ReEncrypt方案是基于3.1节提出的NTRU-LPR设计的,输入面授权者的解密正确率与NTRU-LPR方案的解密正确率一致,详见3.1节.

(2)对方案输出面被授权者的解密正确性如下:被授权者接收到转换密文C j后,计算:

当|puB+pue′g i+pe i g i+pug iq B pe j+pue′pe j+pe i pe j+pme j+mg i|∞

m′=puB+pue′g i+pe i g i+pug iq B pe j+pue′pe j+pe i pe j+pme j+mg i,

而后计算m=m′(modp),由于g i≡1(modp),最终可得m=m′,在选择适当的参数t=3,αq≥n1/4,n3/2+αqω(logn)p(4n1/2+2p+pn3/2)

4.2 单向性

根据密文的转换方向,代理重加密可以分为单向代理重加密和双向代理重加密.单向代理重加密在实际应用中信息保密性更强,有效控制代理者的密文转换能力,防止代理者未经自己同意向腐化用户转换密文信息造成信息泄漏.即代理者只能将Alice的密文转换成Bob的密文或是将Bob的密文转换成Alice的密文,而不允许双向同时转换.在NTRU-LPR-ReEncrypt方案中,由于噪声多项式的存在,代理者无法将重加密密钥rki→j=g i g j q+pe j g j q(modq)求逆或其它运算得到rkj→i,因此NTRU-LPR-ReEncrypt方案是一个单向代理重加密方案.

4.3 多跳性

多跳性是指代理者多次运行重加密算法C j=C irki→j实现i从1取到N−1,j=i+1时,连续重加密得到重加密密文C N=C1rk1→2rk2→3···rkN−1→N,仍有Decrypt(C N,g N)=m(E表示剩余2N−1−1个提出因子p后的所有多项式).

解密C N过程如下:

经过验证,代理者连续重加密N−1次得到的密文C N仍然可以解密出明文m,方案满足多跳性.

4.4 抗合谋性

本方案是满足抗合谋性的,代理者与被授权者合谋不能得到授权者的私钥信息,代理者与授权者合谋也不能得到被授权者的私钥信息.

假设被授权者是一个腐化用户,此时被授权者的私钥g j对于代理者是透明的,代理者计算rki→j g j=(g i g j q+pe j g j q)g j(modq)=(g i+pe j)(modq),由于噪声多项式pe j的存在,代理者无法获得授权者的私钥g i.

假设授权者是一个腐化用户,此时授权者的私钥g i对于代理者是透明的,代理者计算rki→j g iq=(g i g j q+pe j g j q)g iq(modq)=(g j q+pe j g j q g iq)(modq),由于噪声多项式pe j g j q g iq的存在,代理者无法获得被授权者的私钥g j.

4.5 安全性证明

本小节证明NTRU-LPR-ReEncrypt方案在D-RLWE困难假设下是IND-CPA安全的.

学习阶段.攻击者Λ可向算法β查询任意多项式次以下查询

(1)私钥查询:攻击者Λ向算法β发起私钥查询,若查询的用户不是攻击目标用户i∗,算法β运行KeyGen算法返回给攻击者相应的用户私钥g i,否则返回终止符⊥.

(2)重加密密钥查询:攻击者Λ向算法β发起用户i到用户j的重加密密钥查询,在私钥查询的基础上,算法β运行ReKeyGen算法得到重加密密钥rki→j=g i g j q+pe j g j q(modq),并将其返回给攻击者Λ.如果i=j或者用户i为诚实用户,用户j为腐化用户,则挑战者忽略攻击者Λ的请求,返回一个随机值.

(3)重加密查询:攻击者Λ向算法β发起密文C i到密文C j的重加密查询,算法β利用重加密密钥rki→j运行ReEncrypt算法得到重加密密文C j=C irki→j,并将其返回给攻击者Λ.如果i=j或者用户i为诚实用户,用户j为腐化用户,则挑战者忽略攻击者的请求,返回一个随机值.

5 效率分析

本节分为两个小节对方案进行效率分析,5节对本文提出的公钥加密变体NTRU-LPR方案进行效率分析,5.2节对基于NTRU-LPR构造的NTRU型代理重加密方案进行效率分析.

5.1 NTRU-LPR方案对比分析

对比方案的参数选择,不同的多项式采样空间使方案具有不同的加密结构和安全性,目前NTRU体制的多项式采样空间主要分为三种.传统NTRU公钥加密方案NTRU-HPS[5]及其变体NTRU-HRSS[7]的多项式采样空间为R=Z(x)/x n−1,该采样空间的方案在理论上还未能归约到格上的困难问题,安全性仅能达到OW-CPA安全.NTRU prime[8]的多项式采样空间为素数域R=Z(x)/x n−x−1,可最小化攻击者可用的环同态数,与传统NTRU公钥加密方案一致,在理论上也未能归约到格上的困难问题,仅能达到OW-CPA安全.RLWE型NTRU变体[4,9]的多项式采样空间为R=Z(x)/x n+1,其IND-CPA安全性可以归约为格上的RLWE问题.本方案为RLWE型NTRU变体,其安全性可以归约为RLWE判定问题,具体对比如表1所示.

表1 NTRU公钥加密变体参数选择Table 1 Parameter selection of NTRU public key encryption variant

对比方案的密钥尺寸和通信成本,与原BI-NTRU-LPR[9]相比,保证原有的IND-CPA安全性的同时,单密钥的加密结构使通信成本和密钥尺寸降低了50%,与NIST后量子密码算法标准化提交的NTRU-HPS-DPKE[5]、NTRU-HRSS-DPKE[7]和NTRU prime core[8]方案相比,减小了私钥尺寸并将安全性由OW-CPA安全提升为IND-CPA安全.与Stehlé和Steinfeld提出的第一个IND-CPA安全的NTRU公钥加密变体[4]相比,私钥尺寸减小了log2q倍,新方案的公钥均匀性依赖于RLWE判定问题,在一定程度上解决了该方案通过密钥采样自离散高斯分布来保证IND-CPA安全性,造成对参数要求过大导致方案不实用的问题.具体对比如表2所示.

表2 NTRU公钥加密变体性能对比Table 2 Parameter comparision of NTRU public key encryption variant

5.2 NTRU-LPR-ReEncrypt方案对比分析

在安全属性方面,与目前已知的NTRU代理重加密方案NTRUReEncrypt[1]、PS-NTRUReEncrypt[1]、张明武方案[21]和基于格上LWE问题构造的代理重加密方案[13,14]以及基于RLWE问题构造的NTRU-ABD-PRE方案[20]相比,本文方案将方案的困难性归约为RLWE问题,并证明方案在RLWE困难假设下可以达到IND-CPA安全,同时方案满足单向性、抗合谋性和多跳性,具体对比如表3所示.

在方案的密钥尺寸方面,与NTRU体制的代理重加密方案相比,完善了代理重加密安全属性的同时,没有增加密钥尺寸,保留了NTRU体制密钥尺寸小的实用性优势.与LWE体制的代理重加密方案相比,由于在文献[14]中为保证方案的正确性,设置参数为m>6nlog2q,所以有m>n,O(mlog2q)>O(nlog2q),在文献[13]中,设置参数为m>(5+3δ)nlog2q,同样有m>n,O(mlog2q)>O(nlog2q),因此本文方案的密钥尺寸远小于LWE体制的代理重加密方案[13,14].与基于RLWE问题的NTRUABD-PRE方案[20]相比,将重加密密钥尺寸减小为NTRU-ABD-PRE方案的1/log2q.具体对比如表4所示.

表4 渐近密钥尺寸对比Table 4 Asymptotic key size comparison

在方案的计算复杂度方面,本文方案的核心运算的多项式环上的乘法运算,通过快速傅里叶变换算法FFT(fast Fourier transform)可以有效加快运算效率,使得方案计算复杂度为O(nlogn),而基于LWE体制的代理重加密方案中的运算为矩阵运算,加密、解密和重加密计算复杂度为O(n2),本文方案较LWE体制的代理重加密方案在计算复杂度方面具有较大优势,与目前已有NTRU和RLWE体制的代理重加密方案相比,没有增加方案的计算复杂度.具体对比如表5所示.

表5 计算复杂度对比Table 5 Computing complexity comparison

在方案的时间成本方面,定义多项式卷积乘法的时间成本为t m,随机多项式的采样成本t e,由于LWE体制的代理重加密运算为矩阵运算,无法与多项式环上的运算统一比较,这里只选取PSNTRUReEncrypt方案[1]、NTRU-ABD-PRE方案[20]和文献[21]的代理重加密方案进行对比分析,由表6可知,本文方案较PS-NTRUReEncrypt和NTRU-ABD-PRE方案,提升了重加密的效率,减小了重加密操作中随机多项式采样带来的时间成本.

表6 时间成本对比Table 6 Time cost comparison

6 结束语

本文总结了NTRU公钥加密目前的研究成果并改进BI-NTRU-LPR方案,在保证方案IND-CPA安全性的同时减小了密钥尺寸.基于改进的新型可证明安全NTRU变体,构造了一个可证明安全的单向抗合谋代理重加密方案,进一步完善了NTRU代理密码体制.与目前已有的LWE型代理重加密方案相比,具有密钥尺寸小、计算复杂度低、实用性强的优势.但在实际应用场景下需要进一步完善NTRU代理重加密方案的功能特性,以实现对被授权者的细粒度访问控制和对半可信代理者的代理转换能力的条件及门限控制.