计算机应用   2016, Vol. 36 Issue (10): 2733-2737  DOI: 10.11772/j.issn.1001-9081.2016.10.2733
0

引用本文 

项文, 杨晓元, 吴立强. 理想格上可撤销的模糊身份加密方案[J]. 计算机应用, 2016, 36(10): 2733-2737.DOI: 10.11772/j.issn.1001-9081.2016.10.2733.
XIANG Wen, YANG Xiaoyuan, WU Liqiang. Revocable fuzzy identity based encryption scheme over ideal lattice[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(10): 2733-2737. DOI: 10.11772/j.issn.1001-9081.2016.10.2733.

基金项目

国家自然科学基金资助项目(61272492,61572521);陕西省自然科学基础研究计划项目(2015JM6353)

通信作者

项文(1990—),男,湖北襄阳人,硕士研究生,主要研究方向:格公钥密码学,E-mail:xiangwen0917@163.com

作者简介

杨晓元(1959—),男,湖南湘潭人,教授,博士生导师,CCF会员,主要研究方向:密码学、信息安全;
吴立强(1986—),陕西蓝田人,讲师,硕士,CCF会员,主要研究方向:格公钥密码学、可证明安全理论

文章历史

收稿日期:2016-03-28
修回日期:2016-06-17
理想格上可撤销的模糊身份加密方案
项文, 杨晓元, 吴立强    
武警工程大学 网络与信息安全武警部队重点实验室, 西安 710086
摘要: 针对目前基于身份加密(IBE)方案不能同时满足用户撤销和模糊身份提取功能,基于理想格上的差错学习问题(LWE),借助二叉树结构和门限秘密共享算法,提出了一个可撤销的模糊身份加密方案(RFIBE)。该方案首先利用理想格上的陷门生成函数和门限秘密共享算法生成用户的私钥,其次利用二叉树结构完成方案的撤销功能。最后,在标准模型下证明所提方案的安全性达到了选择身份和选择明文攻击下的不可区分性(IND-sID-CPA)安全。与基于标准格的IBE方案相比,所提方案同时具备可撤销功能和高效模糊身份提取功能,实用性更强。
关键词: 用户撤销    模糊身份加密    差错学习    门限秘密共享算法    
Revocable fuzzy identity based encryption scheme over ideal lattice
XIANG Wen, YANG Xiaoyuan, WU Liqiang     
Key Laboratory for Network and Information Security of Chinese Armed Police Force, Engineering University of Chinese Armed Police Force, Xi'an Shaanxi 710086, China, Xi'an Shaanxi 710086, China
Abstract: The present Identity Based Encryption (IBE) scheme cannot meet user revocation and fuzzy identity extraction at the same time, a Revocable Fuzzy IBE (RFIBE) scheme based on hardness of Learning With Errors (LWE) problem over ideal lattice was proposed to resolve the above problems by using revocable binary trees and threshold secret sharing algorithm. Firstly, the trapdoor generating function over ideal lattice and threshold secret sharing algorithm were used to generate user' private key. Then an RFIBE scheme was put forward by using revocable binary trees. Finally, the scheme was proved to be INDistinguishabity against selective IDentity and Chosen Plaintext Attack (IND-sID-CPA) secure. Compared with previous IBE scheme, RFIBE has stronger practicability with the function of revocation and efficient fuzzy identity extraction.
Key words: user revocation    Fuzzy Identity Based Encryption (FIBE)    Learning With Error (LWE)    threshold secret sharing algorithm    
0 引言

基于身份的加密(Identity Based Encryption,IBE)[1]体制的提出极大地简化了密钥的管理。该密码体制是利用用户的身份信息作为公钥,由可信中心产生私钥,用户接收到加密完的消息用自己的私钥进行解密。但是直到2001年,Boneh等[2]基于双线性对假设提出了第一个实用的基于身份的加密方案。随后,众多基于双线性对和格的身份类密码方案[3-6]被提出。

在日常生活中,用户的密钥由于各种原因会出现丢失或者用户变成非法用户,这就需要定期更新用户的密钥或者系统,显然,后者的代价要高得多。因此,可撤销身份的密码方案有着重要意义。最近,Libert等[7]提出了一个可撤销的身份类加密(Revocable IBE,RIBE)方案,方案中可信中心执行非撤销用户的对数级别的工作量,这有效地减轻了可信中心的负担,并且第1次获得非交互的密钥撤销。2012年,Chen等[8]基于格问题提出了第一个可撤销的基于身份的加密方案,该方案仅达到了选择性安全。2015年,张彦华等[9]结合Chen方案[8]和Agrawal方案[4]上提出了适应性安全的可撤销的基于身份加密方案。同年,Cheng等[10]基于标准格上子集差分提出了适应性安全的可撤销身份加密方案。

模糊身份加密(Fuzzy IBE,FIBE)[11]的提出解决了某些用户的身份信息不能被完全正确提取的问题,如生物特征的识别等。在FIBE系统中,用户的身份信息通过一个属性集合来表示,加密公钥也为一个属性集合,当且仅当这两个集合足够“相近”时,解密才能正常执行。这类密码体制能够容忍部分错误公钥信息,其容忍程度由衡量集合近似度的方法决定。文献[11]利用双线性对上的判定性Diffie-Hellman(Decisional Diffie-Hellman,DDH)问题构造了一个选择身份安全的模糊身份加密方案。2012年,Agrawal等[12]借助格工具实现了新的模糊身份加密方案,方案不仅可以抵抗量子计算机的攻击,而且拥有格的快速计算特性。最近,吴立强等[13]基于理想格问题提出了一个高效的模糊身份加密方案,方案中解决了Agrawal方案[12]中的公钥长度大、密文扩展率高的缺点。

本文基于以上用户撤销模型和模糊身份加密模型,提出了一个基于理想格困难问题的方案——RFIBE(Revocable FIBE)。方案在标准模型下证明是非适应性选择身份和选择明文攻击下的语义不可区分性(INDistinguishabity against selective IDentity and Chosen Plaintext Attack,IND-sID-CPA)安全的,并且方案运算效率上也存在优势,方案的可撤销性质,解决了密钥的撤销与更新问题,减轻了服务器存储和管理上的负担;模糊身份提取功能解决了某些用户的身份信息不能被完全正确提取的问题场景,实用性更强。

1 基础知识 1.1 格

几何学上的格又称为点格,是n维空间中规则排列的离散的无限点集。其定义如下:

定义1[14] 格是由Rn中的m个线性无关向量b1,b2,…,bm整数线性组合构成的集合,记为:

$L({{b}_{1}},{{b}_{2}},\cdots ,{{b}_{m}})=\left\{ v\in {{R}^{n}}|v=\sum\limits_{i=1}^{m}{{{t}_{i}}{{b}_{i}}},{{t}_{i}}\in Z \right\}$

向量组[b1,b2,…,bm]称为格L的一组基,m称为格L的维数,n是格L的阶。如果m=n,则称格L是满秩格(full rank)。设B=[b1,b2,…,bm],格的基用矩阵的形式表示为L(B)={Bt|t∈Zm}。

定义2 对于一个素数q,整数m、n,矩阵A∈Zqn×m,m维q-ary格定义为:

Λq(A)={e∈Zm}

s.t. ATe=0(mod q)

Λqu(A)={e∈Zm}

s.t. ATe=u(mod q)

定义3 设ρs(x)是中心为0、标准差为s的n维高斯分布,即ρs(x)=exp(-π‖x‖2/s2),那么对于格L,记ρs(L)=$,当ρs(L)有界时,格L上的高斯分布定义为∃y∈L,DL,s(y)=ρs(y)/ ρs(L)。

1.2 环上错误学习问题困难性假设

设α∈R+∈(0,1),q≥2,T=R/Z为[0,1)上加法运算模1的实数群,Ψα是T上正态分布,其均值为0,标准差为α,对于任意的x∈Ψα,Ψαq表示Zq上值为round(xq) mod q的离散分布。设f(x)=xn+1∈Z[x],安全参数n=2k(k∈Z)(保证f(x)不可逆),离散错误分布为χ=Ψaq。设秘密s∈Rqn均匀分布,随机均匀选取的a∈Rqn和噪声e∈R(e系数服从χ分布),计算(a,〈a,s〉+e)∈Rqn×Rq,并将其分布记为As,Ψαq(也称RLWE(Learning With Errors over Rings)分布),计算性RLWE问题就是通过来自As,Ψαq的样本以很大概率正确解出s∈Rqn。判定性RLWE问题[14]描述如下:

存在一个敌手A和RLWE预言机O,O包含两个采样算法O(随机均匀选取(a,b)∈U(Rqn×Rq))和Os(设定秘密s∈Rqn和选择均匀分布的a,计算(a,b= 〈a,s〉+e)∈As,Ψαq),敌手A向预言机O询问,O随机利用O或者Os产生一些实例(a,b)∈U(Rqn×Rq)返回给敌手A,如果A能够准确分辨出实例来自O或Os的优势Adv(A)=|Pr[AOs=1]-Pr[AO=1]|是不可忽略的,那么就说A能够解决判定性RLWE问题。

当且仅当参数q为素数且f(x)=xn+1∈Z[x]能够在Zq上分解为n个不同线性因子时,判定性RLWE是困难的(参见文献[15])。

1.3 相关算法

算法1[16] 设n为2的幂数,q≥5是素数,输入一个环多项式向量g1′∈Rq×,其系数在Zq上是均匀分布,存在概率多项式时间(Probabilistic Polynomial Time)算法Trap(n,q),输出环多项式向量g2′=(g1′⊗u1,g1′⊗u2,…,g1′⊗um1)∈Rqm1,其中:ui∈Rqm1×n(1≤i≤m1),ui的系数取自离散高斯分布DZm1×n,ui是格g2′的陷门。

算法2 ExtractLeft(a,g,Ta,u,σ)。

输入 环多项式u,a∈Rqm,g∈Rqm和陷门Ta,σ≥‖Ta‖ω($\sqrt{\operatorname{l}bm}$ m)。

输出 多项式向量e~DZ2m,满足e⊗(a;g)=u。

1) 随机选取统计服从分布DZm×n的e1Rm,计算u1=e1⊗g。

2) 运行原像采样算法,计算t=SamplePre(Rotf(a),Ta,u-u′,σ)∈Zmn;

3) 计算e2=Mapv-M(t)∈Rm,e2~DZm×n;

4) 输出e=(e1;e2)∈R2m

1.4 模糊身份加密定义

一个FIBE方案由以下四个算法组成:

Fuzzy.Setup(λ,l)→(PP,MSK):算法输入安全参数λ和用户身份的最大长度l。算法输出公共参数PP和主私钥MSK。

Fuzzy.Extract(MSK,PP,ID,k)→SKID:算法输入主私钥MSK,公共参数PP和用户身份ID,门限值k≤l;输出用户的解密私钥SKID

Fuzzy.Enc(PP,ID′,m)→CTID′:算法输入待加密消息m,用户的身份ID′相关的公钥,公共参数PP;输出密文消息CTID′

Fuzzy.Dec(PP,CTID′,SKID)→m:算法输入密文CTID′,解密密钥SKID,公共参数PP。如果|ID∩ID′|≥k,输出明文m;否则终止。

本节定义选择性安全的模糊身份基加密方案,方案的非适应性选择挑战ID和选择明文攻击下的语义不可区分性(IND-sID-CPA)可以通过敌手A与挑战者C之间的游戏来定义。

1) 攻击目标:敌手A公布要攻击的ID*

2) 初始化:挑战者C运行Fuzzy.Setup算法,将公共参数PP发送给敌手,保留主密钥MSK。

3) 询问1:对于任意的,敌手A选择一系列IDi(ID*≠IDi,i=1,2,…,k)交给挑战者C,C运行Extract算法返回IDi所对应的私钥。敌手对私钥进行询问。

4) 挑战:敌手A选择两个等长的明文M0和M1,发送给挑战者C,C随机选取β∈{0,1},并计算C*=FuzzyEnc(ID*,Mβ),返回密文C*给A。

5) 询问2:A再选择一系列的IDi(ID*≠IDi,i=1,2,…,k)进行私钥询问。

6) 猜测:敌手A给出对β的猜测β′∈{0,1}。如果β′= β,则敌手A获胜。

敌手A在上述游戏中的优势定义为:

AdvAIND-sID-CPA=|Pr(β= β′)-12|。

如果一个攻击者A在多项式时间内赢得上述的攻击游戏的优势AdvAIND-sID-CPA是可以忽略的,则称被攻击的FIBE方案是IND-sID-CPA安全的。

1.5 可撤销身份加密形式化定义及安全模型

一个可撤销身份加密方案由以下七个多项式时间内的算法组成:系统建立(Setup)、用户私钥生成(PriKeyGen)、更新密钥生成(UpdKeyGen)、解密密钥生成(DecKeyGen)、加密(Enc)、解密(Dec)、身份撤销(KeyRev)。

Setup(1λ,N):输入安全参数和系统参数,输出系统的主密钥MSK,公开参数PP,用户撤销列表RL和状态表ST,MSK系统自己保存,PP公开。

PriKeyGen(PP,MSk,ID,ST):输入用户的身份标识ID,系统的主密钥MSK和状态ST,输出用户的私人密钥SKID和更新状态ST。

UpdKeyGen(PP,MSK,t,RL,ST):输入公共参数PP,系统主私钥MSK,密钥更新时间t,状态ST。系统输出更新密钥KUt

DecKeyGen(SKID,KUt):输入用户的私人密钥SKID和当前的更新密钥KUt。如果用户ID未被撤销,输出用户的解密密钥DKID,t,否则输出⊥。

Enc(PP,ID,t,m):输入公共参数PP,主私钥MSK,用户身份标识ID和待加密消息m,输出密文CTID,t

Dec(PP,DKID,t,CTID,t):接收者输入公共参数PP,用户的解密密钥DKID,t和密文CTID,t,输出明文消息m。

KeyRev(ID,t,RL ST):输入用户的ID,撤销时间t,撤销列表RL和状态ST,返回更新后的撤销列表RL。

2 理想格上的RFIBE方案 2.1 方案描述

参数设置如下:噪声上界为qσlmα·ω($\sqrt{lbm}$ m)+O(σm3/2),n=2k,2n|q-1,m=6n1+δ,s=ml·(ω$\sqrt{lbn}$),q=max(2Q,2m $\sqrt{n}$·ω($\sqrt{lbn}$ )),其中Q是敌手进行用户密钥询问的次数,α=[l2m2ωlb n],nδ>lb q=O( lb n)。

1) 系统建立。

输入安全参数λ和身份最大长度l,调用陷门生成函数Trap(n,q)返回giRqn(0≤i≤l)和系统陷门Tgi,选取2l+1个均匀随机分布的环多项式向量ai、bi和d∈Rqm,其中:i∈[l],表示分别取整数i=1,2,…,l;随机选取环多项式u∈Rq,输出公共参数PP=({gi,ai,bi,}i∈[l],g0,d,u),主密钥MK=Tgi

2) 用户私钥生成。

①输入公共参数PP,主密钥MK,用户身份属性集ID=(id1,id2,…,idl)∈Rql,门限值k <l,撤销列表RL和状态ST;从BT上选取一个空的叶子节点v,将用户ID存储在该节点,∀θ∈Path(v),将uθ,1、uθ,2置空,随机选取uθ,1Rq,uθ,2=u-uθ,1,并存储在节点θ。

②分别对uθ,1=(u1,u2,…,un)∈Rq的每个分量使用Shamir秘密共享算法,计算生成l个份额。对于i∈[l],选择系数均匀分布的k-1次多项式使得pi(0)=ui

③对于j∈J,J⊂[l],且J≥k,构造第j个份额向量vj=(vj,1,vj,2,…,vj,n)=(p1(j),p2(j),…,pn(j))∈Rn,根据Shamir秘密共享方案系数的相关性,选取系数Lj,满足${{u}_{\theta ,1}}=\sum\limits_{j=1}^{J}{{{L}_{j}}{{v}_{j}}}$

④对于i∈[l],选取身份idi,构造 fidi=ai+h(idi)bi,其中h为系数取自{0,1}多项式到任意多项式的映射。运行算法ExtractLeft(gi,fidi,Tgi,uθ,1,i,σ)得到环多项式向量eθ,1,iRq2m,满足Fidi⊗eθ,1,i=uθ,1,i,其中Fidi=(gi; fidi),输出SKID={(θ,eθ,1,i)}θ∈Path(v),i∈[l]和ST。

3) 密钥更新。

输入公共参数PP,主密钥MK,密钥更新时间t=(t1,t2,…,tl)∈{-1,1}l,撤销列表RL和状态ST,令ft=d+$\sum\nolimits_{i=1}^{l}{{{t}_{i}}{{b}_{i}}}$。∀θ∈KUNodes(BT,RT,t),将uθ,1、uθ,2置空,随机选取uθ,1Rq,uθ,2=u-uθ,1,并存储在节点θ,运行算法ExtractLeft(g0,ft,Tg0,uθ,2,σ)得到环多项式向量eθ,2Rq2m,满足Ft⊗eθ,2=uθ,2,其中Ft=(g0; ft),输出KUt={(θ,eθ,2)}θ∈KUNodes(BT,RL,t)和ST。

4) 解密密钥生成。

输入用户私钥SKID={(v,ev,1,i)}v∈V,i∈[l],更新密钥KUt={(j,ej,2)}j∈J,其中V和J是节点集;若存在(v,j)使得v=j,则输出DKID,t=({ev,1,i}i∈[l],ej,2);否则DKID,t→⊥。由于v=j,简记为DKID,t=({e1,i}i∈[l],e2)。

5) 加密。

输入公共参数PP,用户身份ID′=(id′1,id′2,…,id′l)∈Rql,密钥更新时间t和消息m(系数满足{0,1}的n阶多项式)。

①定义D=(l!)2

②随机选取均匀分布的环多项式s∈Rq

③随机选取系数服从分布DZm×n,δ的环多项式向量ex;随机产生2m个随机均匀n阶环多项式向量r1,r2,…,r2m(系数取自{-1,1})。计算ey,1=(ex⊗r1,ex⊗r2,…,ex⊗rm),ey,2=(ex⊗rm+1,ex⊗rm+2,…,ex⊗r2m),选择噪声${{e}_{z}}\xleftarrow{R}{{\chi }_{\{\alpha ,q\}}}$

④令Fidi=[gi; fidi]∈Rq2m,Ft=[g0; ft]∈Rq2m,计算

${{c}_{0}}=u\cdot s+D{{e}_{z}}+m\left\lfloor q/2 \right\rfloor $
${{c}_{1,i}}={{F}_{id{{'}_{i}}}}\cdot s+D\left( {{e}_{x}};{{e}_{y,1}} \right)$
${{c}_{t}}={{F}_{t}}\cdot s+D\left( {{e}_{x}};{{e}_{y,2}} \right)$

ct=Ft·s+D(ex;ey,2)

输出密文CTID′,t=(c0,{c1,i}i∈[l],ct)。

6) 解密。

输入公共参数PP,解密密钥DKID,t和密文CTID′,t

①设J⊂[l]表示身份属性向量中ID和ID′中的元素匹配集合,如果|J| <k,输出⊥;否则计算Lagrange系数Lj,满足

$\sum\limits_{j=1}^{J}{{{L}_{j}}{{v}_{j}}}=\sum\limits_{j=1}^{J}{{{L}_{j}}({{F}_{i{{d}_{j}}}}\otimes {{e}_{1,j}})}={{u}_{\theta ,1}}$

②计算$\omega ={{c}_{0}}-\sum\limits_{j=1}^{J}{{{L}_{j}}({{c}_{1,j}}\otimes {{e}_{1,j}})}-{{e}_{2}}\otimes {{c}_{t}}$,若ω的系数更接近于$\left\lfloor q/2 \right\rfloor $,输出1;否则输出0。

7) 用户撤销。

输入用户的身份ID,密钥更新时间t,撤销列表RT和状态表ST。运行算法KUNodes(BT,RT,t)将需要撤销的用户ID添加到对应的叶子节点v,将密钥更新时间t添加到撤销列表RL,并输出新的撤销列表RL。

2.2 正确性分析

方案的正确性计算,输入密文CTID′,t=(c0,{c1,i}i∈[l],ct)和解密密钥DKID,t=({e1,i}i∈[l],e2),计算如下:

$\begin{align} & \omega ={{c}_{0}}-\sum\limits_{j=1}^{J}{{{L}_{j}}({{c}_{1,j}}\otimes {{e}_{1,j}})}-{{e}_{2}}\otimes {{c}_{t}} \\ & \text{ }=u\cdot s+D{{e}_{z}}+m\left\lfloor q/2 \right\rfloor -\sum\limits_{j=1}^{J}{{{L}_{j}}({{F}_{i{{d}_{j}}}}\otimes {{e}_{1,j}})}\cdot s- \\ & \text{ } \sum\limits_{j=1}^{J}{{{L}_{j}}D(\left( {{e}_{x}};{{e}_{y,1}} \right)\otimes {{e}_{1,j}})}-{{e}_{2}}\otimes {{F}_{t}}\cdot s-{{e}_{2}}\otimes D\left( {{e}_{x}};{{e}_{y,2}} \right) \\ & =m\left\lfloor q/2 \right\rfloor +\underbrace{\left\{ u\cdot s-\sum\limits_{j=1}^{J}{{{L}_{j}}({{F}_{i{{d}_{j}}}}\otimes {{e}_{1,j}})\cdot s-{{e}_{2}}\otimes {{F}_{t}}\cdot s} \right\}}_{=u-{{u}_{\theta ,1}}-{{u}_{\theta ,2}}=0}\text{+} \\ & \text{ } \underbrace{\left\{ D{{e}_{z}}-\sum\limits_{j=1}^{J}{{{L}_{j}}D\left( {{e}_{x}};{{e}_{y,1}} \right)\otimes {{e}_{1,j}}-{{e}_{2}}\otimes D\left( {{e}_{x}};{{e}_{y,2}} \right)} \right\}}_{\approx 0} \\ \end{align}$

所以,要正确解密必须满足差错量 $ D\left\{ {{e}_{z}}-\sum\limits_{j=1}^{J}{{{L}_{j}}\left( {{e}_{x}};{{e}_{y,1}} \right)\otimes {{e}_{1,j}}-{{e}_{2}}\otimes \left( {{e}_{x}};{{e}_{y,2}} \right)} \right\}$中的每一个系数绝对值不能超过q/4。

定理1[12] 设D=(l!)2,给定k≤l个数值I1,I2,…,Ik∈[1,2,…,l],定义拉格朗日系数为$D{{L}_{j}}=\prod\limits_{i\ne j}{\frac{-{{I}_{i}}}{{{I}_{j}}-{{I}_{i}}}}$,所以有对于1≤j≤k,DLj是一个整数,满足|DLj|≤D2≤(l!)4

由于私钥量({e1,i}i∈[l],e2)和噪声量ex的系数是服从分布DZ2m×n,σ和DZm×n,δ的,且有ey,1=(ex⊗r1,ex⊗r2,…,ex⊗rm)和ey,2=(ex⊗rm+1,ex⊗rm+2,…,ex⊗r2m),所以对于任意的|1≤i≤m,都有$\parallel {{e}_{y,i}}\parallel \le \sqrt{mn}\parallel {{e}_{x,i}}\parallel $。根据文献[13]定理5,存在一个c≥1,满足‖ex,i‖≤cδn/2π,根据环多项式的运算法则,噪声多项式的每一个系数相当于$\sqrt{D{{L}_{j}}m(mn)}\le Dm\sqrt{n}$个系数服从分布DZm,σ的x∈Rm和服从分布DZm,δ的y∈Rm内积,因此解密失败的概率为:

$\begin{align} & Pr[Dm\sqrt{n}|<x,y >| \ge q/4] \\ & =Pr[|<x,y>| \ge q/(4Dm\sqrt{n})] \\ & =Pr[|<x,y>| \ge T\sigma ||y||] \\ & <2\exp (-\pi {{T}_{1}}^{2}) \\ \end{align}$

由于${{T}_{1}}=\frac{q}{4Dm\sqrt{n}\sigma \parallel \hat{y}\parallel }\ge \frac{\sqrt{2\pi }q}{4Dm\sqrt{n}\sigma \chi \sigma c\sqrt{n}}=t\ge 15$, 所以,对于选取合适的参数,解密失败的概率2exp(-πT 12)是可忽略不计的,因此方案的解密正确的概率接近1。

2.3 安全性分析

方案的安全性分析可以从两个方面进行证明:一是可撤销性质的安全性;二是模糊身份加密的安全性。

对于方案中的可撤销性质的证明,文献[8]已经证明基于标准格的可撤销身份加密方案的安全性达到了IND-sID-CPA安全。目前研究表明,当标准格移植理想格上时,安全性并没有降低[15],求解RLWE等价于解决理想格中最短向量问题(Shortest Vector Problem,SVP)问题的最难实例。本文方案是基于理想格上的困难问题,方案在构造过程中,对于身份构造满足选择性安全,因此本文方案满足IND-sID-CPA安全。

对于本文的模糊身份加密方案,方案的安全性证明如下:

定理2 假设存在一个多项式时间的敌手A,攻击选择性安全的模糊身份加密方案优势ε>0,那么就存在一个多项式时间内的算法B解决判定性RLWE问题的优势ε/(l+1)。

证明 在RLWE困难问题实例定义中提供的随机采样预言机O既不是完全随机的预言机,也不是带噪声的伪随机预言机。模拟者B利用与敌手A交互区分两个加密信息,交互如下:

实例化 从预言机O进行(lm+1)个RLWE采样,采样如下:

$\begin{align} & ({{w}_{1}},{{v}_{1}})\in R_{q}^{{}}\times R_{q}^{{}} \\ & \left\{ (w_{1}^{1},v_{1}^{1})(w_{1}^{2},v_{1}^{2})\cdots (w_{1}^{\text{m}},v_{1}^{\text{m}}) \right\}\in {{(R_{q}^{{}}\times R_{q}^{{}})}^{m}} \\ & \text{ } \cdots \text{ } \cdots \\ & \left\{ (w_{l}^{1},v_{l}^{1})(w_{l}^{2},v_{l}^{2})\cdots (w_{l}^{\text{m}},v_{l}^{\text{m}}) \right\}\in {{(R_{q}^{{}}\times R_{q}^{{}})}^{m}} \\ \end{align}$

攻击目标 攻击者A向B公布他要攻击的目标身份ID′。

系统建立 B构造如下的系统参数PP。

1) 随机从RLWE预言机采样中{(wl1),(wl2),…,(wlm)}i∈[l]选取l个多项式向量gi=(wi1,wi2,…,wim)i∈[l]

2) 从RLWE预言机随机选取多项式u,u=w1

将公共参数返回给敌手A。

询问 对身份ID*的每一个私钥生成进行作如下适应性询问:

1) 设ID∩ID*=I⊂[l],[I]=t <k,拥有与集合I相关的多项式向量的陷门,假设ID*和ID的前t比特是相同的。

2) 假设u的份额构造vj=u+a1i+a2i2+…+ak-1ik-1,其中a1,a2,…,ak-1是多项式。

3) 对于i∈[t],idi*=idi,随机运行高斯采样算法SampleGaussian生成ei,记vi= fidi⊗ei

4) 由于t≤k-1,有k-1个n次多项式a1,a2,…,ak-1,随机选取k-1-t个份额v1,v2,…,vk-1,由于a1,a2,…,ak-1的值是确定的,所以所有的份额v1,v2,…,vk-1也就确定了。

5) 对于j=t+1,…,l,vj= fidj⊗ej,运行算法SamplePre( fidj,Tgj,vj,σ),生成私钥ej

6) 返回(e1,e2,…,el)。

在交互中,真实的公共参数和密钥的分布与模拟中的参数分布在统计上是不可区分的。

挑战 敌手A输出消息,B构造如下密文进行回复:

1) 设ci′=(vi1,vi2,…,vim)。

2) 计算ci=(ci′; ci′⊗r1,ci′⊗r2,…,ci′⊗rm)。

3) c0=v0+mq/2」。

猜测 多次适应性询问结束之后,敌手A输出猜想比特b′∈{0,1},模拟者输出敌手A的猜测作为对RLWE预言机的求解。敌手成功的优势为:

$\begin{align} & Adv_{\varepsilon ,\mathcal{A}}^{ID-CPA}(k)=|\Pr [b=b']-1/2| \\ & \le Adv_{\mathcal{B}}^{\text{RLWE}}=\varepsilon /(l+1) \\ \end{align}$

其中:AdvBRLWE为攻击判定性RLWE成功的优势,由于不存在PPT算法有效求解判定性RLWE问题,因此本文方案中的模糊身份加密过程是非适应性挑战身份和选择明文攻击不可区分性安全的。

综上所述,将新方案的安全性紧凑地归约为判定性RLWE困难性假设,证明了方案满足IND-sID-CPA安全。

2.4 性能分析

本文提出了一个基于理想格困难问题的具有可撤销性质的模糊身份加密方案。由于基于格的IBE方案只涉及群上的加法和乘法,具有较高的加解密运算速度。本文方案采用了环上多项式进行运算,利用快速傅里叶变换可以进一步提高加解密速度,也容易采用并行系统实现加解密操作。同时,由于密文每次操作都是向量运算,平均密文长度明显缩短。由于本文方案调用原像采样函数次数少,可以在不增加额外计算量的前提下降低密文扩展率。而安全性方面,根据文献[17],当n≥256及适当的参数选取时,RLWE困难问题已经满足大部分的加密需求。即使面对量子计算机,格密码也具有相当的优势。

3 结语

本文基于理想格中的RLWE困难问题,结合撤销二叉树结构和Shamir门限秘密共享方案,提出了一个可撤销的模糊身份加密方案,并在标准模型下证明是IND-sID-CPA安全的。相对于现有的基于标准格的IBE方案,本文方案利用了理想格可进行快速傅里叶变换计算的特性,具有更高的加解密速度和更低的密文扩展率。本文方案的可撤销功能,解决了密钥的撤销与更新问题,减轻了服务器存储和管理上的负担。模糊身份提取功能解决了某些用户的身份信息不能被完全正确提取的问题场景,在现实生活中具有广阔的应用前景。

参考文献
[1] SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Proceedings of CRYPTO 1984 on Advances in Cryptology. Berlin: Springer, 1985: 47-53. (0)
[2] BONEH D, FRANKLIN M. Identity-based encryption from the Weil pairing[C]//Proceedings of CRYPTO 2001 on Advances in Cryptology. Berlin: Springer, 2001: 213-229. (0)
[3] BOLDYREVA A, GOYAL V, KUMAR V. Identity-based encryption with efficient revocation[C]//Proceedings of the 15th ACM Conference on Computer and Communications Security. New York: ACM, 2008: 417-426. (0)
[4] AGRAWAL S, BONEH D, BOYEN X. Efficient lattice (H)IBE in the standard model[C]//EUROCRYPT 2010: Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 553-572. (0)
[5] SINGH K, PANDURANGAN C, BANERJEE A K. Adaptively secure efficient lattice (H)IBE in standard model with short public parameters[C]//SPACE 2012: Proceedings of the Second International Conference on Security, Privacy, and Applied Cryptography Engineering, LNCS 7644. Berlin: Springer, 2012: 153-172. (0)
[6] SINGH K, PANDURANGAN C, BANERJEE A. Lattice based forward-secure identity based encryption scheme with shorter ciphertext[J]. Journal of Internet Services and Information Security, 2013, 3 (1/2) : 5-19. (0)
[7] LIBERT B, VERGNAUD D. Adaptive-ID secure revocable identity-based encryption[C]//CT-RSA 2009: Proceedings of the 2009 Cryptographers' Track at the RSA Conference. Berlin: Springer, 2009, 5473: 1-15. (0)
[8] CHEN J, LIM H W, LING S, et.al. Revocable identity-based encryption from lattices[C]//ACISP 2012: Proceedings of the 17th Australasian Conference on Information Security and Privacy, LNCS 7372. Berlin: Springer, 2012: 390-403. (0)
[9] 张彦华, 胡予濮, 江明明, 等. 格上可撤销的基于身份的适应性安全的加密方案[J]. 电子与信息学报, 2015, 37 (2) : 423-428. ( ZHANG Y H, HU Y P, JIANG M M, et al. A lattice-based revocable adaptive-ID secure encryption scheme[J]. Journal of Electronics & Information Technology, 2015, 37 (2) : 423-428. ) (0)
[10] CHENG S, ZHANG J. Adaptive-ID secure revocable identity-based encryption from lattices via subset difference method[C]//ISPEC 2015: Proceedings of the 11th International Conference on Information Security Practice and Experience, LNCS 9065. Berlin: Springer, 2015:283-297. (0)
[11] SAHAI A, WATERS B. Fuzzy identity based encryption[C]//EUROCRYPT 2005: Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, LNCS 3494. Berlin: Springer, 2005:457-473. (0)
[12] AGRAWAL S, BOYEN X, VAIKUNTANATHAN V, et al. Functional encryption for threshold functions (or, fuzzy IBE) from lattices[C]//PKC 2012: Proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography, LNCS 7293. Berlin: Springer, 2012:280-297. (0)
[13] 吴立强, 杨晓元, 韩益亮. 基于理想格的高效模糊身份加密方案[J]. 计算机学报, 2015, 38 (2) : 775-782. ( WU L Q, YANG X Y, HAN Y L. An efficient FIBE scheme based on ideal lattices[J]. Chinese Journal of Computers, 2015, 38 (2) : 775-782. ) (0)
[14] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//STOC 2005: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. New York: ACM, 2005: 84-93. (0)
[15] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[C]//EUROCRYPT 2010: Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 6110. Berlin: Springer, 2010: 1-23. (0)
[16] MICCIANCIO D. Generalized compact knapsack, cyclic lattices, and efficient oneway functions[J]. Computational Complexity, 2007, 16 (4) : 365-411. doi: 10.1007/s00037-007-0234-9 (0)
[17] RÜCKERT M, SCHNEIDER M. Estimating the security of lattice-based cryptosystems[EB/OL]. [2015-10-10]. https://eprint.iacr.org/2010/137.pdfhttps://eprint.iacr.org/2010/137.pdf. (0)