标准模型下格上基于身份的门限解密方案

吴立强1杨晓元1,2张敏情1

1(武警部队网络与信息安全保密重点实验室(武警工程大学) 西安 710086)2(网络信息安全教育部重点实验室(西安电子科技大学) 西安 710071)

基于身份的门限解密体制(identity-based threshold decryption, IBTD)是将秘密共享方法和基于身份加密算法有效结合.在(t,N)门限解密方案中,N个解密服务器共享用户私钥,当解密时,至少需要t个服务器参与并计算相应解密份额,才能正确恢复出明文.然而,少于t个或更少的服务器无法获取关于明文的任何信息.目前现存的格上IBTD方案都是在随机预言模型下证明的,主要方法是对服从高斯分布的私钥直接分割.针对该问题,构造了一种非交互的IBTD方案,采用拉格朗日秘密分割方法对一个公共向量进行拆分,每个解密服务器得到各自的特征向量,通过用户的私有陷门,对特征向量进行原像抽样,得到私钥份额,有效隐藏了用户完整私钥,提高方案的安全性.在解密份额验证时,采用离散对数问题的难解性,实现了可公开验证性.在解密份额组合时,通过公共向量分割合并和解密份额分割合并之间运算的同态性,保证解密的正确性.在标准模型下,将该方案的安全性规约为判定性LWE(learning with errors)困难假设,证明了其满足IND-sID-CPA安全.

关键词基于身份的门限解密;格;标准模型;可公开验证性;非交互性

门限解密体制是将秘密共享方法和加密算法有效结合.在(tN)门限解密体制中,N个解密服务器共享解密私钥,当对密文进行解密时,至少需要t个服务器共同参与并返回相应的解密份额,才能正确恢复出密文所对应的明文.然而,少于t个或更少的服务器无法获取关于明文的任何信息.门限解密体制能够降低或避免因个体完全掌握解密密钥而导致的滥用权限、密钥丢失,或某个服务器被攻击者完全控制而造成系统瘫痪等安全风险,使系统的容错率和安全性得到较大提高.

传统公钥加密体制必须明确公钥与其拥有主体的对应关系.1984年,Shamir创造性地引入了基于身份密码学(identity-based encryption, IBE),在该体制中,公钥直接就是其拥有者的身份信息,如手机号码、Email等,这种公钥密码体制天然地确定了公钥与实体之间的绑定关系,无需借助可信第三方,因此简化了繁琐的证书管理环节,具有较强的实用性.

将基于身份的思想引入到门限解密环境中,某个身份所对应私钥的持有者不再是某个单一个体,而可能是多个实体.比如某个公司的总经理,当他不能处理以公司名义加密的文件时,他可以选择将解密私钥分割并分发给公司的3个副经理,当且仅当其中的2个副经理合作才能够解密公司的文件,而任何1个副经理是无法独自解密的.这样的机制,一方面限制了某个副经理独自解密的过大权限,另一方面即使在某一个副经理缺席的情况下,仍然能够正常处理公司业务.

在基于身份的门限解密系统中,非交互性和可验证性是2个重要属性.非交互性是指解密服务器在解密过程中不需要相互进行数据交换.可验证性是指可公开验证密文的合法性.如果一个基于身份的门限解密方案满足上述2个性质,那么每一个解密服务器只需要使用自己的私钥份额即可完成解密,而无需通过某种交互机制来验证密文份额合法性,从而使方案更为简洁和高效.

本文通过借鉴利用双线性映射构造基于身份门限解密的方法,采用格上陷门产生函数生成系统主密钥,采用左右基扩展技术为用户生成私钥,私钥本身是身份所对应的陷门.在秘密分割时,没有对用户私钥进行直接分割,而是采用拉格朗日方法对一个公共向量进行分割,得到每个解密服务器的特征向量.通过用户拥有的私有陷门,对特征向量进行原像抽样,得到私钥份额,有效隐藏了用户完整私钥,从而使其更为安全.在解密份额的验证中,采用离散对数问题的难解性,保证其可公开验证性.在解密份额组合时,通过公共向量拆分合并和解密份额拆分合并之间运算的同态性,保证方案解密的正确性.在标准模型下,将该方案的安全性规约为判定性LWE困难假设,证明了其能够满足IND-sID-CPA安全.同现存的格上基于身份的门限加密方案相比,本文是对满足均匀分布的向量进行分割,安全性更高,同时证明过程在标准模型下完成.

1相关工作

门限密码体制起源于著名密码学家Shamir和Blakley提出的(t,N)门限秘密共享方法[1-2].前者采用多项式插值的方法设计了门限秘密共享方案,而后者则使用了有限几何方法.Boneh等人[3]最早将门限思想引入到了基于身份的加密中.其初衷是解决密钥管理中心PGK完全掌握系统主私钥,从而造成权限过大的问题,主要方法是将主PKG的系统主密钥采用秘密分割方法分发给了N个分PKG,每个分PKG为用户生成部分私钥份额,至少需要t个分PKG产生的私钥份额,才能构成用户的完整私钥,完成解密功能,因此该机制也称为分布式PKG.2006年,Boneh等人[4]扩展了这种思想,构造了基于身份的(t,N)门限加密体制(threshold iden-tity-based encryption, TIBE).之后,考虑到分PKG也可以执行解密的功能,因而解密操作由原来的用户端转移到了分PKG上,但是这种机制存在2个弊端:1)要求分PKG必须实时在线处理解密请求;2)如果可用的PKG数量不足t个,就无法完成解密.

因此,Baekand和Zheng认为[5]:在基于身份密码学中,对用户私钥进行分割比对系统主密钥进行分割更为合适,每个解密服务器拥有用户部分私钥,可直接解密基于身份的密文,得到解密份额,合并这些解密份额即可恢复出明文.利用这种思路,他们提出了基于身份的门限解密方案(identity-based thre-shold decryption, IBTD),并基于双线性对,构造了一个选择密文攻击安全的基于身份门限解密方案,同时将其扩展为了一个可仲裁的身份加密方案.文献[6-7]分别构造了选择明文攻击安全的IBTD方案.

上述IBTD方案都是基于双线性映射实现.量子计算具有天然的并行性,其超强的计算能力,可用于密码破译.特别是 Shor量子算法,可对目前广泛使用的、基于经典困难问题构造的公钥密码方案进行有效攻击,严重威胁其安全性.在目前已知的抗量子攻击候选密码体制中,基于格上困难问题设计的密码体制[8],不但能够抵抗Shor算法攻击,而且具有最困难实例与一般实例等价、高效易实现等优势,是后量子密码中最典型的代表,已经成为当前密码学领域研究的热点.

在利用格上困难问题,构造门限加解密方面,已有部分成果.Bendlin等人[9]利用Regev加密系统[10],构造了第一个格上门限公钥加密方案,其安全性能够规约到格上困难问题的最难实例.Xie等人[11]利用有损陷门函数,给出了一种高效门限加密方案的构造方法,并利用格工具进行了实例化.Singh等人[12]提出了一个高效的TPKE 方案,其满足可重拆分属性,即如果拆分算法输出腐化私钥份额的数量小于t,则私钥的拆分能进行任意多项式次.

上述这些格上TPKE都是非基于身份环境下的.2014年,Singh等人[13]将格上门限解密方案[12]扩展到了基于身份环境中,构造了格上第1个基于身份的门限解密方案.在该方案中,用户身份所对应的私钥满足正态分布,直接对于该私钥进行分割,每个参与者获得一个私钥份额,当需要解密时,采用私钥份额进行解密得到解密份额,合并即可恢复出明文.文献[14]在标准模型下,基于LWE困难问题,采用Shamir门限秘密共享的方法,构造了一种标准模型下选择身份安全的模糊身份加密方案(fuzzy identity based encryption, FIBE),即当用户公钥属性集与加密公钥属性集的交集等于或大于规定的门限值时,可正常解密.文献[15]基于格上困难问题提出了一种基于身份的门限加密方案,同时利用通用转化方法,得到了一种带关键字的密文搜索加密方案.

当前,格与双线性是设计密码方案的两大重要工具,双线性对映射群具有灵活代数结构,已经存在很多成熟的关键技术、安全模型、证明方法,而格密码学主要依赖于线性运算及巧妙的陷门设计,且具有抗量子攻击的性能,因此,将格这一新兴的密码学工具与成熟的双线性密码方案构造方法相结合,可以有效推动格密码学的发展.本文工作就是基于这样的思路展开.

2预备知识

定义[j]={1,2,…,j},表示整数.假设a,b,c表示列向量,用A,B,C表示矩阵.对矩阵AB,符号[A|B]代表他们横向联结,[A;B]表示纵向联结.表示从N个不同元素中取出t个元素的组合数.

2.1格和LWE假设

定义1. 整数格.设B=[b1,b2,…,bm]∈n×m是一个矩阵,其列向量b1,b2,…,bmn线性无关,B生成的n维满秩格为

L(B)={yns.t. ∃sm,

对于素数qAu格定义为

Λq(A)={ems.t. ∃s满足ATs=e(modq)};

ms.t.Ae=0(modq)};

ms.t.Ae=u(modq)}.

定义2. 格的高斯分布.用ρσ(x)表示标准n维高斯分布,其均值为0,方差为σ,即对于一个给定的格L和实数σ>0,若是有限的,可以定义格的高斯分布为

定义3. LWE问题[10].包括计算性LWE问题和判定性LWE问题.

计算性LWE问题:选取一个公开参数n>1,一个模数q≥2,定义噪声概率分布为ψs=D,s,秘密选取均匀分布的向量s随机选取均匀分布的向量A输出样本(A,ATs+e)∈如果存在一个算法,能够利用给定的若干个样本以很大的概率恢复出s那么该算法能够解决计算性LWE问题.

判定性LWE问题:存在一个敌手A和LWE预言机O,该预言机包含2个抽样算法OS(根据LWE分布输出样本(A,ATs+e)∈其中随 机选择矩阵A选择服从分布的e选择服从均匀分布的s实际上,同样可以被证明是安全的)和O$(从均匀分布U(中输出一个随机样本),如果A可以解决判定性LWE问题当且仅当优势

Adv(A)=|Pr[AOS=1]-Pr[AO$=1]|

是不可忽略的.

下面的定理将LWE困难假设规约到了格上经典困难问题.

定理1[10]. 设nq是整数,a∈(0,1),取如果存在一个高效的算法解决了LWE问题,就存在一个有效的量子算法,在最坏的情况下以复杂度解决判定性的最短向量问题(gap shortest vector problem, GapSVP)和最短无关向量问题(shortest independent vectors problem, SIVP).

2.2相关的函数和数学工具

1) 陷门产生函数

定理2[16]. 假设q>3是奇数,m=6nlogq,TrapGen是一个概率多项式时间内算法,能够以绝对的优势同时输出一组矩阵(A其中A统计上满足均匀分布,TA是格的一个优良基,且以压倒一切的概率满足通常称为陷门.

2) 抽样算法

引理1[16]. 假设q>2,整数m>n,矩阵ATA是格的一个陷门,且那么,对于cmu

② 对于任意的u存在多项式时间内的随机原像抽样算法SamplePre(A,TA,u,σ),能够返回一个统计上服从分布的向量

③ 存在多项式时间内的高斯抽样算法Sample(A,TA,u,c),能够返回一个统计上服从DΛ,σ,c分布的向量

④ 如果采用SamplePre获取O(mlgm)个采样那么从中找到m个线性无关向量,形成满秩矩阵E={e1,e2,…,em} ∈的概率接近于1.

3) 左采样基算法

在HIBE方案中[16],左采样基算法使用一个低维格的陷门生成一个更高维数格的陷门,从而实现格基授权.具体方法是利用矩阵A的陷门TA进行多次采样,形成一个扩展矩阵的短基.根据引理1中第④条,这些短基是满秩的且尺寸较短,可以作为陷门,为更高维数的矩阵进行抽样.

算法1. 左抽样基算法SampleBasisLeft(A0,A1+H(id)B,TA,σ).

输入:用户id,A1+H(id)B,和陷门

输出:身份Fid=(A0|A1+H(id)B)的陷门TidD2m×2m,σ,满足Fid·Tid=0.

① 随机选取统计服从Dm×n,σ分布的e1m

② 计算u1=(A1+H(id)Be1

e2=SamplePre(A0,TA,-u1,σ)∈m×n

④ 设置e=(e2,e1),重复上述过程,直到得到2m个线性无关向量;

⑤ 将上述2m个向量组合成Tid2m×2m.

4) 身份编码

在基于身份的门限解密方案中,采用有限域qn维向量表示用户身份.选择域,对于系数小于n的多项式g[x],定义coeffs(g)∈n表示gn维系数向量,如果g系数小于n-1,可以给右边填充0使其成为n位.如果f[x]是一个次数为n的不可逆多项式,那么对于任何一个多项式g[x],多项式gmodf的次数不超过n,系数coeffs(gmodf)∈n即为n维向量.设用户身份为g=(g1,g2,…,gn)∈定义

n×n.

定义4. 假设q是素数,n是一个整数,定义身份编码函数H:差分满秩编码函数,它具有2个性质[16]

① 对于所有不同的身份g1,g2矩阵H(g1)-H(g2)∈是满秩的;

H的计算能够在多项式时间内完成.

5) Shamir的(t,N)门限方案

使用Shamir的(t,N)门限方案分享一个秘密S的过程为:

① 随机选择t-1个系数a1,a2,…,at-1q.

② 构造一个t-1阶多项式函数:

f(x)=S+a1x+a2x2+…+at-1xt-1.

③ 定义用户的编号为1,2,…,N,对于1≤iN,计算每个份额Si=f(i),并发送Si给第i个用户.

④ 当用户的有效份额数达到门限值t时,函数f(x)可以被重构:

其中,Mj表示Lagrange系数:

那么,秘密S=f(0),秘密被恢复.

Shamir门限方案具有一些优良性质:

① 完善性.对于每个秘密S,当份额数量大于或者等于t个,有且仅有唯一的一个t-1次多项式满足条件;而少于t个份额得不到关于S的任何有用信息.

② 同态性.

Ⅰ.如果对所有的秘密份额Si(1≤iN)都相加或者相乘一个常数,那么新的秘密相当于原来秘密S与这个常数相加或者相乘.

Ⅱ.如果存在2个秘密值ST,选择的多项式是分别是f(x)和g(x),相应的份额分别为f(1),f(2),…,f(N)和g(1),g(2),…,g(N).定义一个新的秘密份额为h(j)=f(j)+g(j), 1≤jN,那么这些新份额可重构出秘密f(0)+g(0)=S+T.

6) 离散对数问题

定义5. 离散对数(discrete logarithm, DL)假设. 循环群G1的阶是素数pG1的生成元是g.离散对数(DL)问题是指,给定二元组(g,ga),求出a的值,其中a该问题在密码学的典型离散对数群上是困难问题,设敌手为A,则:

成立,其中ε是可忽略的概率,表示攻击DL问题成功的概率.DL假设是指没有多项式时间内运行的概率性算法能够解决离散对数困难问题.

2.3相关定义和安全模型

1) TIBE的定义

定义6. 一个基于身份的门限解密IBTD方案包含7个算法:

① 系统初始化算法Setup.输入安全参数λ,密钥生成中心PKG输出公共的系统参数pp,以及主私钥msk.

② 密钥生成算法KeyGen.输入一个用户身份id,以及PKG私钥msk,输出用户私钥Sid.

③ 私钥分割算法DisKey.输入一个身份id和对应私钥Sid,解密服务器的个数N,以及门限参数t.该算法生成id对应的N个私钥份额TSKid,i(1≤iN).同时,为了能够验证各个解密服务器输出的解密份额是否有效,还应当生成与秘密份额TSKid,i相对应的验证信息TVKid,i.注意,TSKid,i被秘密交给对应的第i个解密服务器,而TVKid,i(1≤iN)公开.

④ 加密算法Enc.输入一个用户的身份id和待加密的明文M,输出密文C.

⑤ 部分解密算法SubDec.输入一个密文C,解密服务器i的私钥份额TSKid,iTVKid,i,输出一个解密份额θi.

⑥ 份额验证算法ShareVery.输入一个密文C,解密服务器i的解密份额θi,以及验证密钥TVKid,i,验证θi是否为有效的解密份额,如果无效,则算法输出“⊥”.否则,验证通过.

⑦ 联合算法Combine.输入至少t个解密份额{θi,C},iS,S∈{1,2,…,N},|S|≥t.首先检测θi的有效性,如果无效,返回“⊥”.否则联合t个有效解密份额,输出解密结果M.

定义7. IBTD方案的IND-sID-CPA(Indist-inguishability of ciphertexts under a selective-identity chosen-plaintext attack)安全性.其是根据攻击者A和挑战者C之间的游戏定义的.

初始化.攻击者A输出准备要攻击的身份id*和一个腐化的解密服务器集合S∈{1,2,…,t-1}.

设置.挑战者C运算Setup(λ),将获取的公开参数给攻击者,自己保留系统主私钥.

第1阶段询问:

① 私钥询问,攻击者A询问身份id(idid*)所对于的私钥Sid,挑战者C运行KeyGen算法并将结果Sid返回给A.

② 私钥份额询问,当被询问用户id的第i个解密份额时,C运行ShareKeyGen(id,Sid,N,t)算法获取私钥份额TSKid,i(1≤iN),和相应的门限验证密钥TVKid,i,如果(idid*)或者(id=id*,iS),那么挑战者返回相应份额给攻击者,否则输出“⊥”.

挑战阶段.攻击者A输出2个等长的消息M0,M1(M0M1),挑战者随机选择一个b∈{0,1},并计算挑战密文C*=Encrypt(id,Mb),将其发送给A.

第2阶段询问.与第1阶段相同.

猜测.攻击者A给出一个对b值的猜测b′∈{0,1},如果b′=b那么攻击者获胜.

攻击者A在上述游戏中的优势为

定义8. 解密一致性.其游戏中定义的初始化、设置和询问步骤与定义7中的相同,攻击者输出2组解密份额S={θ1,θ2,…,θt} 和如果3个条件成立,攻击者获胜:

SS′在身份id*TVKid*下都是合法份额;

SS′中解密份额来自t个不同解密服务器;

Combine(TVKid*,id*,S,C)≠Combine(TVKid*,id*,S′,C);

攻击者A在上述解密一致性游戏中的优势定义为

定义9. 如果一个IBTD方案是IND-sID-CPA安全的,那么对于任意的都是可以忽略的.

3方案描述

1) 系统设置Setup(λ)

输入安全参数λ,设置nq=ploy(n),m=O(nlogq).

① 根据TrapGen算法,PKG生成随机均匀分布的矩阵A0和陷门

② 选择2个均匀分布的矩阵A1B,选择一个均匀分布的向量u

③ 选择身份编码函数H:

④ 定义映射函数φ:{0,1}m+1×{0,1}*q,其输入为密文C和密钥KA,其输出为之间的随机值.

⑤ 选择一个素数p使得离散对数问题在以g为生成元的循环群p上是困难的.

公开系统主要参数pp=(A0,A1,B,u,H,φ,g),保留主密钥

2) 私钥提取Extract(msk,pp,id)

输入用户id和系统主密钥利用身份编码函数计算H(id)∈id对应公钥为Fid=(A0|A1+H(id)B).使用左基采样算法计算Fid对应的陷门Tid满足Fid·Tid=0,且Tid服从噪声分布

返回私钥Tid给用户id.

3) 私钥分割算法DisKey(id,Tid,N,t)

给定解密服务器数量N、门限值t和公共参数pp,标记u=(u1,u2,…,un)∈

① 随机选择n个多项式li(x)←q[x] (1≤in) 满足最高次数等于t-1且li(0)=ui.对于1≤iN,第i个解密服务器的特征向量为uid,i=(l1(i),l2(i),…,ln(i)).

② 对于1≤iN,利用陷门Tid,采用SamplePre(Fid,Tid,uid,i,2σ)算法抽取出eid,i满足Fid·eid,i=uid,i,那么第i个服务器拥有的用户id部分私钥份额为TSKid,i=eid,i,并将其表示为向量eid,i=(eid,i,1,eid,i,2,…,eid,i,2m),验证份额为TVKid,i=(geid,i,1,geid,i,2,…,geid,i,2m).

所有解密服务器对于用户id的门限验证密钥为TVKid=(TVKid,1,TVKid,2,…,TVKid,N),其可以公开.

③ 对于任意一个解密服务器iN,在除去i的所有N-1个服务器中,选择t个服务器组成一个群,使用A表示其群号,并选择一个随机整数KA分发给此群中的所有解密服务器,那么每一个服务器将获得个随机整数.

i个解密服务器的私钥份额为个随机整数),将其通过保密信道发送给第i个解密服务器.

4) 加密算法Enc(id,M)

① 计算id的公钥Fid=(A0|A1+H(id)B);

② 随机选择均匀分布的s

③ 选择均匀分布的矩阵R其系数随机取自{-1,1};随机选取噪声分布xψs和噪声计算

④ 待加密消息M∈{0,1},计算密文y|z)∈c2=uTs+x+Mq/2q,输出密文C=(c1,c2)∈q.

5) 部分解密算法SubDec(TSKid,i,C=(c1,c2))

利用私钥份额TSKid,i,计算出密文C所对应的解密份额,过程如下.

① 遍历TSKid,i得到个整数);

② 计算

③ 对于个整数中的每一个,标记为计算并对所有的计算结果求和

④ 第i个解密服务器的部分解密份额为Mi=di+xi.第i个解密服务器解密份额为

6) 份额验证算法ShareVery(TVKid,i,θi,C)

利用验证密钥TVKid,i,验证解密份额θi是否为密文C的合法解密份额.

① 第1部分密文c1=(c1,1,c1,2,…,c1,2m),TVKid,i=(geid,i,1,geid,i,2,…,geid,i,2m),遍历θi得到

② 验证如果等式验证失败,返回“⊥”,否则通过验证.

7) 组合算法Combine(TVKid,C,θ1,θ2,…,θt)

t个解密服务器,构成集合S,他们的解密份额分别为θ1,θ2,…,θt,利用这些份额可以恢复出密文C所对于的明文信息,过程如下.

① 对于每一个解密份额θi(1≤it),如果ShareVery(TVKid,i,θi,C)验证失败,输出 “⊥”,并退出.

② 遍历θi(iS) 得到采用拉格朗日插值公式,以解密服务器的编号作为x值,以解密份额Mi作为y的值.计算拉格朗日系数为

计算解密结果如果M′∈(q/4,3q/4],那么M′=1,否则M′=0.

输出消息M′.

4方案分析

4.1正确性

定理3. 对于任意的实数s>0,T>0和xn,有

定理4. 选择合适的参数,在新的IBTD方案中,解密份额能够通过验证,且解密算法能够正确还原出消息.

证明.

1) 验证算法的正确性.

2) 解密结果的正确性.

来自服务器i的部分解密份额为Mi=di+xi.根据解密份额合成算法, 在获取t个这样的份额后,根据拉格朗日运算的同态性质,计算

q/2=

q/2.

要解密正确,只需要

q/4.

noise可以分为3部分,第1部分是x, 其满足xψs,即服从参数为s的高斯分布.第2部分是其中(eid,i)T(y|z),表示2个长度为2m向量的内积,而2组向量中的每一个分量分别服从参数为2σ和参数为s的高斯分布.利用定理3,可求出其上界.

eid,i=(e1,e2),那么因此可以看成是拉格朗日函数h(x)的所对应的秘密,其采用解密服务器编号为x坐标,(eid,i)T(y|z)为y坐标,容易证明h(0)的值不超过t(σm3/2).

对于第3部分,这里是拉格朗日函数f(x)的结果,其采用解密服务器编号为x坐标,xiy坐标,可以证明f(0)的值不超过其值在之间,因此,第3部分的上限为

要解密正确,只需要noise的3部分之和不超过

q/4,实际上第一个部分非常小,通常可忽略,因此只需要q/4.通过设置适当参数,方案能够正确解密.

4.2安全性证明

先介绍安全性证明过程中需要使用的引理2和定理5.

引理2. 假设mn>(n+1)logq+ω(logn),其中q是一个素数,矩阵A是一个m×m方阵,其值随机取自{-1,1},那么(A,AR)的分布在统计上与分布(A,B)不可区分.

定理5. 在二维平面上给定t个点(x1,y1),(x2,y2),…,(xt,yt),其中xi的值各不相同,那么存在且唯一存在最高次数为t-1的多项式f,对于所有的点(xi,yi)(1≤it),满足f(xi)=yi.

定理6. 安全性.如果LWE问题是困难的,那么上述基于格的IBTD方案可以满足IND-sID-CPA安全性.

证明. 证明过程分2步:证明密文满足语义安全和证明解密一致性.

语义安全性证明.先构造一系列游戏,第一个游戏是真实的IND-sID-CPA攻击,而最后一个游戏是攻击者无法获胜的;然后基于一些格上的困难性假设,证明相邻游戏之间在多项式时间内不可区分.

Game0.攻击者A和挑战者C之间真实的IND-sID-CPA游戏,设攻击者A输出准备要攻击的身份id*和一个已经腐化的解密服务器集合S∈{1,2,…,t-1}.挑战者运算Setup算法,将获取的公开参数给攻击者A,自己保留系统主私钥msk.且如下回答攻击者的询问.

1) 私钥询问,攻击者A询问身份id(idid*)所对应的私钥Tid,挑战者运行KeyGen算法并将结果Tid返回给挑战者.

2) 私钥份额询问,当被询问用户id的第i个解密份额时,挑战者运行ShareKeyGen(id,Tid,N,t)算法获取门限份额密钥TSKid,i(1≤iN),和相应的门限验证密钥TVKid,i(1≤iN),如果(idid*)或者(id=id*,iS),那么挑战者返回相应的份额给攻击者,否则输出“⊥”.

Game1. 在Game0中,挑战者公开的系统参数A1取自均匀分布,Game1中环多项式A1不再是随机选取,而是通过A1=A0R*-H(id*)B计算得到,R*为加密阶段选取的随机向量,其余参数的选取与Game0相同.

Game0到Game1:对多项式时间内的攻击者A而言,Game0和Game1概率不可区分,使用引理2可以证明.

Game2. 对Game1中参数进行如下修改,A0q上随机均匀选取,不含陷门.利用陷门函数产生含有陷门TBB那么,用户id对应的身份矩阵为Fid=(A0|A0R*+(H(id)-H(id*))B).挑战者拥有的系统主密钥为TB.其在挑战阶段如此回答询问.

1) 私钥询问,攻击者询问身份id(idid*)所对应的私钥Tid,挑战者运行右采样基算法TidSampleBasisRight(A0,B,R*,TB,2σ)(具体算法参见文献[16],将结果Tid返回给挑战者.

2) 私钥份额询问,当被询问用户id的第i个解密份额时,如果idid*,挑战者首先通过私钥询问获取Tid,之后运行ShareKeyGen(id,Tid,N,t)算法获取门限份额密钥TSKid,i(1≤iN),和相应的门限验证密钥TVKid,i(1≤iN),那么挑战者返回相应的份额给攻击者.如果id=id*,iS,挑战者随机选择长度为2m的向量返回给挑战者.其余情况输出“⊥”.

Game1到Game2:从攻击者A角度来看,私钥份额生成过程是不可见的,A获得的私钥eid,i在统计上仍然服从分布D2m,2σ,且满足Fid·eid,i=uid,i.所以攻击者A在Game1中得到的优势与Game2中的优势相当.

Game3. 挑战密文为随机选取且互相独立的向量C=(c1,c2)∈U(q),其余设置与Game2中相同.

Game2到Game3:假设攻击者A有不可忽略的优势来区分Game2和Game3,那么可以如下构造仿真者S来解决判定性LWE问题.

假设存在一个LWE采样预言机O,其随机从O$或Os中选取一些采样作为输出,仿真者S通过与攻击者A进行交互后判断这些采样取自Os或O$.

实例化:C向预言机O询问并接收m+1个LWE采样,标记为{(w1,v1),(w2,v2),…,(wm+1,vm+1)}.

攻击目标:设攻击者A输出准备要攻击的身份id*和一个已经腐化的解密服务器的集合S∈{1,2,…,t-1}.

S构造如下系统参数:

1)A0=(w1,w2,…,wm)T

2)u=(wm+1);

3) 其余系统参数设置与Game2中相同.

第1阶段询问.与Game2中定义的询问相同.

挑战.当攻击者A给仿真者S发送加密消息M∈{0,1}时,仿真者S如下构造挑战密文:

1) 设

2)c2=(vm+1)+Mq/2

3) 仿真者S从{0,1}中随机选取β,如果β=0,密文C*=(c1,c2)∈q构造方法如上,否则随机选取均匀分布的矩阵C*U(q),将C*发送给攻击者A.

第2阶段询问.和第1阶段询问一样,带有一些限制.

猜测.询问过后,攻击者A给出一个猜想β′∈{0,1},这里β′=1意味着攻击者A正在与Game2交互,仿真者S回答LWE挑战的猜测δ′=β′,这里δ′=1意味着上述实例(wi,vi)(1≤im+1)服从LWE分布,否则δ′=0表示实例服从随机均匀分布.

如果实例化过程中预言机O输出的分布来自Os,那么密文C*的分布与Game2中分布相同.原因如下:第一,Fid*=(A0|A0R*);第二,令那么密文第1部分第2部分q/2=uTs+x+Mq/2,这2部分都与Game2中挑战密文的分布相同.

如果实例化过程中预言机O输出的分布来自O$,那么根据引理也是服从均匀分布的,所以整个密文在统计上仍服从随机均匀分布,而在Game3中,密文C=(c1,c2)∈q取于随机均匀分布.

以上完成了对仿真者S的描述,可以看出如果A能够以不可忽略的优势区分Game2和Game3,那么仿真者S能够以绝对的优势解决判定性LWE问题.

通过以上4个等价游戏,将方案的安全性归约为判定性LWE困难假设.根据定理1,方案达到了语义安全.

解密一致性证明.利用反证法证明方案的解密一致性.假设攻击者A找到2组解密份额S={θ1,θ2,…,θk}和他们在身份id*TVKid*下都是合法的份额,且来自t个不同解密服务器,那就意味着在拉格朗日插值计算过程中,他们的序号即x坐标是相同的,但是y坐标是不同的,最终重构出2个不同的多项式(常数项一定是不同的).

这就与定理5产生了矛盾.

因此,上述方案是满足解密一致性的,因此方案满足IND-sID-CPA安全.

证毕.

4.3效率比较

目前,基于格上困难问题构造的门限解密方案主要有文献[13,15],这2个方案都是基于LWE困难问题构造的,且都满足非交互性,但是从构造方法、安全性和效率方面有所差异.将这些类似方案进行比较,具体如表1所示.可公开验证性是指解密份额是否满足可公开验证性;密钥份额是指每个解密服务器获得的密钥份额,其长度单位为logq位,密文长度是指加密1位明文后生成的密文长度,单位为logq位;计算量中的乘法运算指的是q上2个整数相乘,采用Mul表示;指数运算是指离散对数群上生成元的指数计算,采用Exp表示.Hash表示一次Hash运算,Sign表示一次签名运算.

Table1TheComparisontoRelatedWorks
表1相关工作比较

Schemes Security ModelSecurity LevelPublicly VerifiablePartition Object and Its DistributionLength of Key Share Length of CiphertextEncryption CalculationsDecryption CalculationsShare Verification CalculationsRef[13]Random OracleIND-sID-CPAYesUsers private key/Gaussian distributionnm+1(n+1)n×Mul+1×Signn×Mul+CtN-1×Hash+1×Exp(n+1)×1×Exp+(n+1)×MulRef[15]Random OracleIND-sID-CCANoUsers private key and noise/Gaussian distributionm+nn+1(m+1)n×Muln×Mul0Our Scheme StandardIND-sID-CPAYesPublic vector/Uniform distribution2m2m+1(2m+1)n×Mul2m×Mul+CtN-1×Hash+1×Exp(2m+1)×Exp+(2m+1)×Mul

5

本文利用格上陷门产生函数、左右采样基、Shamir秘密分享等技术构造了一种IND-sID-CPA安全的IBTD方案,并基于离散对数困难问题来实现可公开验证性.同现存格上基于身份的门限加密方案相比,本文是对满足均匀分布的向量进行分割,通过私钥份额和解密份额之间的同态性来保证方案的正确性,同时方案的证明过程在标准模型下完成.

参考文献

[1]Shamir A. How to share a secret[J]. Communications of the ACM, 2011, 22(22): 612-613

[2]Blakley G R. Safeguarding cryptographic keys[C] //Proc of Int Workshop on Managing Requirements Knowledge (AFIPS). Piscataway, NJ: IEEE, 1979: 313-317

[3]Boneh D, Franklin M. Identity-based encryption from the Weil pairing[C] //Proc of the Annual Int Cryptology Conf. Berlin: Springer, 2001: 213-229

[4]Boneh D, Boyen X, Halevi S. Chosen ciphertext secure public key threshold encryption without random oracles[C] //Proc of the Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2006: 226-243

[5]Baek J, Zheng Yuliang. Identity-based threshold decryption[C] //Proc of the Int Workshop on Public Key Cryptography. Berlin: Springer, 2004: 262-276

[6]Chai Zhenchuan, Cao Zhenfu, Lu Rongxing. ID-based threshold decryption without random oracles and its application in key escrow[C] //Proc of the Int Conf on Information Security. New York: ACM, 2004: 119-124

[7] Libert B, Quisquater J J. Efficient revocation and threshold pairing based cryptosystems[C] //Proc of the 22nd Annual Symp on Principles of Distributed Computing. New York: ACM, 2003: 163-171

[8]Zhang Pingyuan, Jiang Han, Cai Jie, et al. Recent advances in lattice-based cryptography[J]. Journal of Computer Research and Development, 2017, 54(10): 2121-2129 (in Chinese)(张平原, 蒋瀚, 蔡杰, 等. 格密码技术近期研究进展[J]. 计算机研究与发展, 2017, 54(10): 2121-2129)

[9]Bendlin R, Damgård I. Threshold decryption and zero-knowledge proofs for lattice-based cryptosystems[C] //Proc of Theory of Cryptography Conf. Berlin: Springer, 2010: 201-218

[10]Regev O. On lattices, learning with errors, random linear codes, and cryptography[C] //Proc of the 37th Annual ACM Symp on Theory of Computing. New York: ACM, 2005: 84-93

[11]Xie Xiang, Xue Rui, Zhang Rui. Efficient threshold encryption from lossy trapdoor functions[C] //Proc of the 4th Int Workshop on Post-Quantum Cryptography. Berlin: Springer, 2011: 163-178

[12]Singh K, Rangan C P, Banerjee A K. Lattice based efficient threshold public key encryption scheme[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications, 2013, 4(4): 93-107

[13]Singh K, Rangan C P, Banerjee A K. Lattice-based identity-based resplittable threshold public key encryption scheme[J]. International Journal of Computer Mathematics, 2016, 93(2): 289-307

[14]Agrawal S, Boyen X, Vaikuntanathan V, et al. Fuzzy identity based encryption from lattices[EB/OL]. [2018-06-10]. http://eprint.iacr.org/2011/414.pdf

[15]Kuchta V, Markowitch O. Identity-based threshold encryp-tion on lattices with application to searchable encryption[C] //Proc of the 6th Int Conf on Applications and Techniques in Information Security. Berlin: Springer, 2016: 117-129

[16]Agrawal S, Boneh D, Boyen X. Efficient lattice (H) IBE in the standard model[C] //Proc of the Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 553-572

Identity-BasedThresholdDecryptionSchemefromLatticesundertheStandardModel

Wu Liqiang1, Yang Xiaoyuan1,2, and Zhang Minqing1

1(KeyLaboratoryofNetworkandInformationSecurity(EngineeringUniversityofChineseArmedPoliceForce),Xian710086)2(KeyLaboratoryofComputerNetworkandInformationSecurity(XiDianUniversity),MinistryofEducation,Xian710071)

AbstractThe identity-based threshold decryption (IBTD) system combines the secret sharing method with the identity-based encryption mechanism. In a (t,N) IBTD system,Ndecryption servers share the private key corresponding to a user’s identity. When to decrypt, at leasttservers are required to participate in and calculate their corresponding decryption shares. However, less thantor fewer servers are unable to obtain any information about the plaintext. At present, the existing IBTD schemes from lattices are constructed under the random model, and the main method is to divide the private key statistically close to a Gauss distribution directly. This paper constructs a non-interactive IBTD scheme. A public vector is split using the Lagrange secret partition method, and each decryption server obtains its respective characteristic vector. Each private key share is obtained by sampling the pre-image of the characteristic vectors through the private trapdoor function for each decryption server. The user’s complete private key is effectively hidden and the security of the scheme is improved. The difficulty of the discrete logarithm problem is used to realize the verifiability of decryption share. The correctness of the decryption share is guaranteed by the homomorphism of the operations between the common vector and the private key shares. The IND-sID-CPA security for the proposed scheme is proved based on the decisional learning with errors (LWE) hardness assumption under the standard model.

Keywordsidentity-based threshold decryption; lattice; standard model; publicly verfication; non-interactivity

This work was supported by the National Nature Science Foundation of China (U1636114, 61572521, 61772550) and the Foundation Funding Research Project of the Engineering University of Chinese Armed Police Force (WJY201523).

基金项目国家自然科学基金项目(U1636114,61572521,61772550);武警工程大学基础研究项目(WJY201523)

修回日期:2018-08-15

收稿日期2018-06-11;

中图法分类号TP391

(latticewj@163.com)

WuLiqiang, Born in 1986. MSc, lecturer. His main research interests include cryptosystems based on lattices and provable security theory.

YangXiaoyuan, born in 1959. PhD, professor and PhD supervisor. His main research interests include cryptography and network security.

ZhangMinqing, born in 1967. PhD, professor. Her main research interests include network security and information hiding.