基于BLISS签名的不经意电子信封_杜育松.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):6172密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]基于 BLISS 签名的不经意电子信封*杜育松1,2,庄少华1,伍春晖31.中山大学 计算机学院,广州 5100062.广东省信息安全技术重点实验室,广州 5100063.广东金融学院 互联网金融与信息工程学院,广州 510521通信作者:伍春晖,E-mail:摘要:目前已有的基于签名的不经意电子信封(oblivious signature-based envelope,OSBE)使用的是Schnorr 或 RSA 等传统数字签名,其安全性来源于离散对数或大整数分解等经典数论困难问题,无法抵御量子计算机的攻击.本文提出一种基于 BLISS 数字签名的不经意电子信封(BLISS-OSBE),可以在量子计算机攻击的环境下保证 OSBE 的安全特性.消息发送者使用对称密码加密消息,然后与消息接收者交互,产生用于加密对称密钥的公钥,使用基于环上的 LWE 问题的公钥加密方案加密对称密钥,拥有有效BLISS 签名的接收者可以解密 LWE 密文得到对称密钥,从而解密消息,并且不泄露自己的身份.方案可以抵御量子计算机的攻击,不涉及大整数、模指数或椭圆曲线点加倍点运算,具有良好的实现性能.关键词:不经意签名电子信封;格密码;环上带错学习;小整数解中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000579中文引用格式:杜育松,庄少华,伍春晖.基于 BLISS 签名的不经意电子信封J.密码学报,2023,10(1):6172.DOI:10.13868/ki.jcr.000579英文引用格式:DU Y S,ZHUANG S H,WU C H.An oblivious envelope based on bimodal lattice signatureschemeJ.Journal of Cryptologic Research,2023,10(1):6172.DOI:10.13868/ki.jcr.000579An Oblivious Envelope Based on Bimodal Lattice Signature SchemeDU Yu-Song1,2,ZHUANG Shao-Hua1,WU Chun-Hui31.School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China2.Guangdong Key Laboratory of Information Security Technology,Guangzhou 510006,China3.School of Internet Finance and Information Engineering,Guangdong University of Finance,Guangzhou510521,ChinaCorresponding author:WU Chun-Hui,E-mail:Abstract:The existing oblivious signature-based envelope(OSBE)schemes use traditional digitalsignatures,such as Schnorr signature or RSA signature,their security comes from classical number-theoretic problems such as solving discrete logarithm or factoring large integers,and they cannot resistattacks from quantum computers.This paper proposes an oblivious envelope based on BLISS signature*基金项目:广东省基础与应用基础研究重大项目(2019B030302008);国家自然科学基金(61972431,61902081);广东省基础与应用基础研究(2022A1515011512);广州市基础与应用基础研究(202102080322)Foundation:Guangdong Major Project of Basic and Applied Research(2019B030302008);National NaturalScience Foundations of China(61972431,61902081);Guangdong Basic and Applied Basic Research Foundation(2022A1515011512);Basic and Applied Basic Research Foundation of Guangzhou Municipality(202102080322)收稿日期:2021-12-20定稿日期:2022-03-3162Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023(BLISS-OSBE),which can ensure the security of OSBE against attacks from quantum computers.Thesender encrypts a message with a symmetric key,then interacts with the receiver to generate a publickey for encrypting the symmetric key,and encrypts the symmetric key with a public key cryptosystembased on the ring-LWE.The receiver who possesses the valid BLISS signature can decrypt LWEencryption and obtain the symmetric key,thus can decrypt the message without revealing his identity.The proposed OSBE scheme can resist the attacks from quantum computers,and it does not involvelarger integer modular exponentiation,or elliptic curve point addition and doubling operations.Theexperimental results show that the proposed scheme has good performance.Key words:oblivious signature-based envelope;lattice-based cryptography;ring-LWE;SIS1引言考虑这样的安全需求,用户 B 为服务接收方,用户 A 为服务发送方,用户 B 接收来自 A 的消息,但出于隐私考虑,用户 B 不希望用户 A 知道用户 B 接收的是哪条消息.比如:网上交易数字产品,消费者不愿意暴露商品购买记录(如某些药品);在线付费浏览或下载,用户不希望暴露其选择过的某些敏感的频道或内容.业务需求中存在大量用户隐私需求的场景,在确保业务功能正常运行的前提下尽可能保护用户隐私是现代密码学的主要目标之一.不经意传输协议(oblivious transfer,OT)由 Rabin 首次提出1,用于描述一个两方计算场景,即发送者 S 发送一个消息给接收者 R,要求 R 以 1/2 的概率得到这个消息,而S 却不知道消息是否被 R 接收.大多数不经意传输协议都没有考虑对协议进行接入控制的问题,即任何与消息发送者通信的用户在执行完协议之后都可以得到他想要的消息,为攻击者窃取消息创造了条件.所以说,对接收者授权并保护授权信息尤为重要.Li 等人提出了基于签名的不经意电子信封方案(oblivious signature-based envelope,OSBE)2.OSBE 能够让用户 A 和用户 B 在以下的情形下进行通信:(1)作为接收者的用户 B 只有在持有相关证书的前提下才能获得消息;(2)发送消息的用户 A 不能判断用户 B 是否持有对应的证书;(3)没有其他用户或实体能够获取用户 A 的消息和用户 B 的证书信息.OSBE 中发送者的访问控制策略在密文中已经强制执行,只有满足发送者设定的属性特征的接收者才可打开密文,使发送者在不确定接收者权限的情形下发送加密消息,而只有经过授权的接收者才能恢复他想要得到的消息.Li 等人构造了基于 RSA 的和基于身份加密的 OSBE 方案2,其中基于 RSA 的方案是两轮的,具有前向安全性等附加的性质.虽然基于身份加密的方案是一轮的,但基于身份的加密系统对密钥分发中心(授权者)需要更强的信任,密钥分发中心可以解密所有的信息.Nasserian 等人在 ElGamal 签名家族的签名方案如 Schnorr、Nyberg-Rueppel 和 DSA 签名上构造了两轮 OSBE 方案3.Blazy 等人4考虑了当授权者不诚实时的语义安全性.当授权者采用窃听攻击的方式时,仍然不能得到传输的消息.他们采用光滑投射哈希函数给出了两轮 OSBE 的通用构造和一个具体构造.Chen 等人5在 Blazy 等人的基础上给出了一轮 OSBE 的通用构造和具体构造,采用了光滑投射哈希函数和基于身份的光滑投射哈希函数.OSBE 可以应用在电子商务、内容保护等领域以保护参与者的隐私,也可用于构造秘密握手协议.申艳光等人6根据不经意传输理论,采用基于 Schnorr 签名的 OSBE,在 2013 年提出了基于 Schnorr 签名的隐私保护网上订购方案.隐私保护的电子交易方案能够使用户在正确付费后,得到且仅能够得到自己订购的商品,从而有效地保护用户的隐私信息不被泄露.杨波等人7采用基于 ElGamal 签名的 OSBE,在2014 年又给出了一个基于 ElGamal 签名的隐私保护网上交易方案.此外,Nasserian 等还在文献 3 中提出 OSBE 与秘密握手8概念的相似性,并使用 RSA-OSBE、NR-OSBE 和 Schnorr-OSBE 构造单轮的秘密握手协议,使用两个 OSBE 交互实现两方的秘密握手.目前已有的 OSBE 使用的签名都是传统公钥密码体制下的签名方案.然而,随着量子计算技术的发展,传统公钥密码受到了极大挑战,基于经典数论问题的公钥密码系统在量子环境下不再安全.作为后量子密码的一个研究分支,格公钥密码相较于其他后量子密码体制具有显著优势,在密码学发展进程中占据重要地位.Lyubashevsky 等人9在 2012 年提出了一个基于格上困难问题的格签名体制,其安全性基于小整数解 SIS 问题的困难性.Ducas 等人10在 2013 年提出了一个基于双峰离散高斯分布的格签名方案杜育松 等:基于 BLISS 签名的不经意电子信封63(bimodal lattice signature scheme,BLISS),这是对 Lyubashevsky 等人9提出的签名方案的改进.它结合拒绝采样方法,通过双峰离散高斯分布的采样,隐藏签名中私钥信息,从而减少了拒绝采样中的拒绝次数,提高了签名产生的效率.格签名方案的逐渐成熟也使得构造基于格签名的 OSBE 成为可能.本文提出了一种基于 BLISS 签名的不经意电子信封(BLISS-OSBE).BLISS-OSBE 在量子计算攻击情况下,仍具有 OSBE 的不经意性和语义安全性,并且可具有前向安全性,能在授权者不诚实(采用窃听攻击)的情况下,保持消息的机密性,达到了 Blazy 等人4提出的对于授权者的语义安全性.在该方案中,消息发送者使用对称密码体制加密要发送的消息,然后与消息接收者交互,产生用于加密对称密钥的公钥,使用基于环上 LWE 问题的公钥加密方案加密对称密钥,并将密文发送给接收者.拥有有效 BLISS 签名的接收者可以解密 LWE 加密,得到对称密钥,从而解密消息,并且不泄露自己的身份;而没有有效 BLISS签名的接收者无法解密 LWE 加密,从而无法解密消息,但不会泄露自己没有有效 BLISS 签名的事实.因此,消息发送者能在不确定接收者权限的情形下不经意地发送加密消息,而只有经过授权的接收者才可以恢复消息,未被授权的接收者无法恢复消息.2预备知识2.1符号说明设 Zx 是全体整系数多项式构成的多项式环,f(x)=xn+1 Zx 为有理数域上的一个不可约多项式,其中安全参数 n 为 2 的幂.令 R=Zx/(xn+1)表示 Zx 中的多项式模去 f(x)=xn+1后形成的整数多项式环.那么环 R 上的元素可以表示为次数小于 n 的多项式.对整数 q 2,环 Rq=R/qR=Zqx/(xn+1)就表示一个同时模 f(x)和 q 的整数多项式环.Rq上的元素可以表示为次数小于 n,系数取自 0,1,q 1 的多项式.2.2基于签名的不经意电子信封 OSBE基于签名的不经意电子信封 OSBE 以签名方案的参数作为输入参数,它包括一个发送者 S 与两个接收者 R1和 R2.其中,接收者 R1拥有证书权威中心(certificate authority,CA)对公开消息 的签名,而接收者 R2不拥有该签名.在每轮协议执行期间,发送者 S 与接收者 R1和 R2当中的一个进行信息交互.使用 OSBE 无须预先对用户进行认证,OSBE 中的信任关系直接来源于对证书权威中心 CA 公钥的信任.一个完整的 OSBE 方案包括以下三个阶段:(1)系统建立.给定一个签名方案,系统建立算法生成待签名消息、待传输消息 P 以及签名方案所需的公私密钥对.算法使用该私钥生成对输入消息 的签名 Sig.待签名消息、公共参数和公钥对所有实体公开,而消息 P 作为待传输明文只对发送者 S 公开,签名 Sig 只对接收者 R1公开.由于系统建立算法产生签名,我们认为系统建立阶段充当了证书权威机构(CA)的角色.(2)信息交互.在信息交互阶段,接收者 R1和 R2中的任意一个被选择作为 R,但发送者 S 不知道R 是哪一个,即 S 无法分辨 R1和 R2.发送者 S 和接收者 R 执行一个交互式协议.(3)打开信封.在信息交互之后,如果 R=R1,也就是在信息交互阶段选择 R1,则 R 就可以打开消息 P,这是因为 R 知道签名 Sig;否则,若 R=R2,则 R 不能打开消息 P.一个 OSBE 方案必须满足以下三个性质:(1)正确性.如果在打开信封阶段,接收者 R1能以占据优势的概率解密密文,输出消息 P,即 R1不能输出 P 的概率可以忽略,那么这个 OSBE 方案就具有正确性.(2)不经意性.执行完交互式协议后,如果发送者 S 不知道接收者 R 是 R1还是 R2,那么这个 OSBE具有不经意性.更确切地说,接收者 R1和 R2被随机地选择作为 R 与 S 进行信息交互,发送者S 正确猜测出另一个实体的概率最好情况下为 prob,则 prob 大于 1/2 的部分可忽略.(3)对接收者的语义安全性.如果执行协议之后接收者 R2不能获取消息 P,那么这个 OSBE 具有对接收者的语义安全性.64Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.20232.3格的相关定义和困难假设定义 1(格的定义)设 B=b1,b2,bm 是 n 维空间中 m 个线性无关的向量,格 L(B)是由向量组 b1,b2,bm的所有整系数线性组合构成,即格 =L(B)=mi=1cibi,ci Z,并称向量组b1,b2,bm为格 的一组基.定义 2(整数上的离散高斯分布)令实数 0,整数上以 为参数的离散高斯分布定义为:D(x)=(x)(Z)=(x)xZ(x)x Z,其中(x)=exp(x222)是以实数 为参数的高斯函数.格上密码方案的安全性依赖于格上困难问题的难解程度,基于格的加密、签名方案的安全性通常可规约到格上困难问题的难解性,从复杂性理论方面讲,这些问题都已被证明是 NP 困难的.Ajtai11于 1999年首次提出了格上的小整数解(SIS)问题.Regev12于 2005 年首次提出容错学习(LWE)问题.之后,Lyubashevsky 等人13研究了一个限制在理想格上的 LWE 问题,即环上带差错学习问题,也被称为环上的 LWE 问题(RLWE),其原理就是利用理想格的特殊代数结构来降低使用 LWE 问题时带来的空间和时间开销.与环上的 LWE 问题类似,Lyubashevsky 和 Micciancio 首先研究了环上的小整数解问题14,即环上的 SIS 问题(RSIS).选择特定的参数,这些问题都被证明可以归约到格上的困难问题,并且具有更符合密码设计的表述形式,因此被广泛应用于各种加密和数字签名方案的设计中.定义 3(RSISKq,l,m,问题)K 为一个 Rlmq上的分布,选取一个服从分布 K 的矩阵 A Rlmq,选择适当的界定参数,RSISKq,l,m,问题是:寻找一个非零向量 v Rmq,满足 Av=0 mod q 且|v|2.定义 4(RLWEq,问题)给定一个秘密 s R 和 R 上某种特定的差错分布,令 RLWEq,表示(a,b=a s+e)RqRq的分布,其中 a 从 Rq中均匀随机选取,差错 e 采样自差错分布,即 e .RLWEq,问题可以表述为两种形式,即 search-RLWEq,问题和 decision-RLWEq,问题:(1)search-RLWEq,:给定分布 RLWEq,中任意多个相互独立的采样(a,b=a s+e),能够以极大的概率恢复 s.(2)decision-RLWEq,:能够以不可忽略的优势区分从 RLWEq,中输出的任意多个采样和从 RqRq上均匀分布输出的相同数目采样.2.4统计上不可区分如果一个函数 f(x),对任意的多项式 p(k),都存在一个 k0使得对所有的 x k0,有 f(x)2,随机生成两个多项式 f 和 g,在每个多项式中有 d1=1n个系数取自 1,有 d2=2n 个系数取自 2,其他系数均为 0,若多项式 f 不可逆,则重新生成 f和 g.签名者的私钥为 S=(s1,s2)t=(f,2g+1)t,通过如下计算得到:aq=(2g+1)/f mod q,定义公钥A=(a1,a2)=(2aq,q 2)R122q.可以容易地验证:AS=2aq f 2(2g+1)=0 mod q,AS=q (2g+1)=q 1=1 mod 2,可知 AS=q mod 2q,这是 BLISS 签名方案中的关键性质,最后签名者获得(A,S)作为一个合法的密钥对.定义 使得 (q 2)=1 mod 2q,有 A=(a1,1).BLISS 签名的安全性可以归约到 RSISKq,1,2,问题的困难性(见文献 10 中的定理 4.4).A 和 S 分别为签名者的公私钥,签名者对输入消息 产生签名 Sig=(z1,z2,c)的过程如下:(1)从整数离散高斯分布中采样获得 y=(y1,y2)t R21,其中 y1,y2 DZn,.(2)计算 c=H(udmod p,),其中 u=Ay=a1 y1+y2mod 2q.(3)计算 z=(z1,z2)t R21,其中 z1=y1+(1)bs1c,z2=y2+(1)bs2c,b 为一个均匀随机比特.(4)以概率 1/M exp(Sc222)cosh(2)继续下一步,否则重新开始(1).(5)计算 zT2=(ud u z2d)mod p.(6)输出签名 Sig0=(z1,zT2,c).这里的第(4)步是一种拒绝采样操作.它概率地输出签名,使得签名的分布与私钥的分布相互独立,从而可以有效防止私钥泄露.具体来说,即输出签名是 z=(1)bSc+y,其中 S 为签名者的私钥,y=(y1,y2)t D2Zn,因此 z 服从的分布为12D,Sc(x)+12D,Sc(x).为了消除签名 z 对私钥 S 的依赖,使用拒绝采样,使得 z 服从的分布为 DZn,从而防止签名泄露私钥 S 的信息.第(5)步中 zT2的作用是压缩签名的规模.对任意整数 x,定义 xd为 x 的高阶比特,即 x 可表示为 x=xd+x mod 2d.在验证签名时,已知被签名的消息、公钥 A=(2aq,q 2)R122q、签名 Sig0=(z1,zT2,c),在签名范数不超过特定大小情况下,当且仅当 c=H(a1 z1+q cd+zT2mod p,)时接受签名.3.2从 BLISS 签名到 BLISS-OSBE以文献 3 中的基于 Schnorr 签名设计的 OSBE 方案为例.消息接收者 R1或 R2与消息发送者 S交互.交互过程中,持有合法签名的 R1使用签名信息进行计算,而没有合法签名的 R2可以使用均匀随机数进行计算,然后将计算结果发给消息发送者 S.R1和 R2发来的计算结果对于消息发送者 S 是无法区分的.消息发送者 S 在此基础上产生一个用于加密消息的共享密钥,然后使用 Diffie-Hellman 密钥协商方法,将产生共享密钥的部分信息发送出去,最后使用该共享密钥加密要发送的消息,把消息密文发送给接66Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023收者 R1或 R2.持有合法签名的 R1利用签名信息,使用 Diffie-Hellman 密钥协商方法,可以计算出共享密钥,解密消息,而没有合法签名的 R2则无法计算出共享密钥.由于 OSBE 的特性,R1或 R2不会向 S暴露自己的身份信息,无论是消息的接收者还是发送者,都不会有密钥确认的信息流.BLISS-OSBE 可以仿照 Schnorr-OSBE 来设计.认证方 CA 直接将 BLISS 签名中的(z1,z2,c)发送给被授权者 R1(不考虑压缩 z2).类似地,在交互过程中,持有合法签名的 R1使用(z1,z2,c)可以计算出Ay=(a1 y1+y2)mod 2q,这是因为:(Az+q(c)=a1 z1+z2+q (c)=Ay+(1)bASc+q (c)=Ay mod 2q,而没有合法签名的 R2使用符合离散高斯分布的随机数(y1,y2)进行计算:(a1 y1+y2)mod 2q=Aymod 2q,其中 y1,y2 DZn,.计算结果 Ay mod 2q 和 Aymod 2q 对于消息发送者 S 是无法区分的.消息发送者 S 在此基础上产生一个用于加密消息的共享密钥 Ks,但无法再类似地使用 Diffie-Hellman 密钥协商方法,将产生共享密钥的部分信息发送给 R1或 R2.我们这里考虑使用基于环上 LWE问题的公钥加密方案,来直接加密共享密钥 Ks.我们注意到,消息发送者 S 在获得 mod 2q 的基础上可以计算:q H(Ayd,)+Ay=(q c+Ay)=Az=(a1 z1+z2)mod 2q,而拥有合法签名(z1,z2,c)的 R1则可以直接计算出 Az=(a1 z1+z2)mod 2q.这里,z1和 z2是通过拒绝采样方法获得的两个服从离散高斯分布 DZn,的多项式,而 a1可以看成是 R2q上均匀选取的多项式.因此,如果 q 足够大,(a1,a1z1+z2)mod 2q 可以对应于基于环 R2q上 LWE 问题的公钥加密方案的公钥,而 z1对应于私钥,z2对应于产生私钥时所用的差错(噪声)多项式.于是,我们让消息发送者 S 直接生成共享密钥 Ks,使用 Ks加密要发送的消息 P,得到密文 C=KsP.基于环 R2q上 LWE 问题的公钥加密方案,使用公钥(a1,a1z1+z2)mod 2q 加密共享密钥 Ks,得到lweKs=(c1,c2),再把 Cc1c2发送给 R1或 R2.最终,在打开信封阶段,只有被授权拥有合法签名Sig=(z1,z2,c)的 R1知道可用于解密的私钥 z1,R1解密(c1,c2)获得共享密钥 Ks,进而使用共享密钥Ks解密密文 C=KsP,获得消息 P.不持有合法签名的 R2无法打开信封.3.3BLISS-OSBE 方案(1)系统建立.输入安全参数 t 后,该算法将产生 BLISS 密钥:(q,A,S),其中 S=(s1,s2)t=(f,2g+1)t为 BLISS 签名的私钥.选择一个合适的哈希函数 H,一个安全的对称加密体制Ks(如 AES,其中 Ks为发送方 S 产生的对称密钥),一个基于环 R2q上 LWE 问题的公钥加密方案(算法)lwe,两个消息 和 P.认证方 CA 计算对公开消息 的 BLISS 签名 Sig=(z1,z2,c),发送者 S 拥有、消息明文 P 和(q,A),接收者 R1拥有、签名 Sig 和(q,A),接收者 R2拥有 和(q,A).(2)信息交互.选择 R1和 R2中的任意一个作为接收者 R,但 S 不知道 R 是哪一个,S 与 R 执行一个交互式的协议.过程如下:(a)(a1)R1 S:X=(Az+q(c)mod 2q=(a1 y1+y2)mod 2q=Ay mod 2q,或(a2)R2 S:X=(a1 y1+y2)mod 2q=Aymod 2q,其中 y1,y2 DZn,.(b)S 接收 X,计算(pk1,pk2),其中pk1=a1mod 2q,pk2=(q H(Xd,)+X)mod 2q.特别地,如果收到的是 X=Ay mod 2q,则pk2=(q H(Ayd,)+Ay)=(q c+Ay)=(a1 z1+z2)mod 2q.杜育松 等:基于 BLISS 签名的不经意电子信封67如果收到的是 X=Aymod 2q,则pk2=(q H(Ayd,)+Ay)=(q c+Ay)mod 2q,其中 c=H(Ayd,).(c)S 产生共享的对称密钥 Ks,加密明文 P 得到 C=KsP,使用基于环 R2q上 LWE 问题的公钥加密算法 lwe和公钥(pk1,pk2),加密共享密钥 Ks,得到 lweKs=(c1,c2).(d)S R1或 R2:C c1c2.(3)打开信封.接收者 R1或 R2收到 Cc1c2后,由于 R1拥有私钥 z1,R1能够解密得到对称密钥Ks,进而解密密文 C=KsP 打开信封获得消息 P;而接收者 R2不拥有可用于解密的私钥,无法解密获得对称密钥 Ks,不能够打开消息 P.图1是整个 BLISS-OSBE 方案的交互示意图.发送者 S接收者 R1接收者 R2系统建立待签名消息 待传输消息 P公开参数(q,A)对称加密体制 Ks对应解密 dKs环 R2q上的 LWE 加密 lwe对应解密 dlwe待签名消息 公开参数(q,A)对消息 的 BLISS 签名Sig=(z1,z2,c)待签名消息 公开参数(q,A)信息交互S 接收 X计算X=(Az+q(c)=A y mod 2q计算X=A y mod 2q其中 y=(y1,y2)ty1,y2 DZn,发送 Xoo发送 Xoo计算(pk1,pk2)pk1=a1mod 2qpk2=(q H(Xd,)+X)mod 2qS 产生对称密钥 KsC=KsP(c1,c2)=lweKs发送 Cc1c2/发送 Cc1c2/打开信封拥有私钥 z1Ks=dlwe(c1,c2),z1P=dKsC,Ks打开信封获得消息 P不拥有私钥 z1无法获得 Ks无法打开信封图 1 BLISS-OSBE 交互示意图Figure 1 Interaction diagram of BLISS-OSBE4BLISS-OSBE 方案的安全性分析本节将说明 BLISS-OSBE 方案满足正确性、不经意性和对于接收者的语义安全性.68Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.20234.1正确性BLISS-OSBE 具有正确性,即在信息交互的最后,拥有签名的 R1应能以很大的概率解密消息 P.在本方案中若发送者 S 能计算出正确的隐含签名信息的 lwe加密算法的公钥,则接收者 R1在拥有、签名 Sig=(z1,z2,c)和(q,A)的情况下,能解密出发送者 S 使用 lwe算法加密的对称密钥 Ks,进而打开信封.这是因为在信息交互阶段,R1 S:X=Ay mod 2q.S 获得 X 并计算:pk2=(q H(Xd,)+X)mod 2q,而(q H(Xd,)+X)mod 2q 满足:X+q H(Xd,)mod 2q=(a1 y1+y2+q H(a1 y1+y2d,)mod 2q,=(a1 y1+y2+q c)mod 2q,=(a1 z1+z2)mod 2q.于是,发送者 S 可以计算得到 pk2=(Az)=(a1 z1+z2),其中签名的一部分 z1作为私钥被接收者R1持有.在打开信封阶段,拥有私钥 z1的 R1能以很大的概率解开密文,进而成功打开信封,解密消息P.4.2不经意性拥有签名的接收者 R1和不拥有签名的接收者 R2在信息交互阶段发送的信息 X 分别来自以下两个分布族:D(y)=(a1 y1+y2)mod 2q=Ay mod 2q,其中 y1,y2 DZn,D(y)=(a1 y1+y2)mod 2q=Aymod 2q,其中 y1,y2 DZn,.这两个分布族分布在相同的值域,并且在每一轮信息交换中,都是从离散高斯分布中均匀随机采样得出 y=(y1,y2)t和 y=(y1,y2)t,可知 y 和 y具有相同的分布,从而分布族 D1(y)和 D2(y)不可区分.因此发送方 S 不能确定接收者 R 是 R1还是 R2,BLISS-OSBE 具有不经意性.4.3针对接收者的语义安全性本节将说明在 BLISS-OSBE 中,未被授权的接收者 R2不能打开消息 P.定理 1 在 RSISKq,l,m,和 RLWE2q,困难问题成立的条件下,BLISS-OSBE 中不持有对消息 的签名 Sig=(z1,z2,c)的接收者不能获得对称密钥.证明:BLISS-OSBE 方案使用的是基于 RLWE2q,的语义安全的公钥加密方案 lwe,一个多项式时间的攻击者 Adversary 参与游戏:(1)Adversary 被告知消息 和公共参数(q,A),其中 A=(2aq,q 2)R122q;(2)Adversary 选择一个多项式 X=(a1 y1+y2)mod 2q,这里 Adversary 可能知道 y=(y1,y2)t的信息,也可能不知道;(3)Adversary被告知一个多项式元组(c1,c2)R122q,(c1,c2)为基于RLWE2q,加密方案lwe加密对称密钥Ks所产生的密文,采用的公钥为pk=(pk1,pk2)=(a1mod 2q,q H(Xd,)+X mod 2q);(4)Adversary 输出多项式 K.当且仅当 K=Ks时,Adversary 才赢得游戏.该游戏过程是在 lwe公钥加密中解密出 Ks.文献 10 中指出在 RSISKq,l,m,困难性问题成立的条件下,BLISS 签名是存在性不可伪造的,即攻击者在已知签名公共参数(q,A)和待签名消息 的情形下,无法伪造一个有效的签名.特别地,BLISS-OSBE 中未被授权的接收者 R2没有合法签名,在与发送者 S 的交互过程中,接收者 R2使用服从离散高斯分布的随机向量(y1,y2)进行计算,但由于 BLISS 签名的不可伪造性,R2无法伪造出相应的签名 z=(z1,z2),同时满足范数大小要求和下列等式:a1 z1+z2mod 2q=q c+Ay,杜育松 等:基于 BLISS 签名的不经意电子信封69其中 c=H(Ayd,).考虑接收者 R2能够伪造一个无效签名 z=(z1,z2),满足上述等式,但不满足范数大小要求,则 z1和 z2不服从离散高斯分布 DZn,那么在 lwe解密阶段,差错(噪声)就会掩盖加密的消息,无法正确恢复对称密钥 Ks.因此假设多项式时间的攻击者 Adversary 赢得了游戏,那么基于 RLWE2q,X的公钥加密方案 lwe能够在多项式时间内被破译,这与 RLWE2q,x困难问题的难解性相予盾.因此在 RSISKq,l,m,和 RLWE2q,X困难性问题成立的条件下,BLISS-OSBE 中不持有对消息 的签名 Sig=(z1,z2,c)的接收者 R2不能获得对称密钥 Ks,从而在打开信封阶段无法打开消息 P,说明BLISS-OSBE 方案具有针对接收者的语义安全性.4.4前向安全性前向安全性由 Gnther15首次提出,是指长期密钥的泄露不会造成之前通信时使用的会话密钥的泄露,从而不会影响先前会话的安全性.在 OSBE 方案中,前向安全性体现在交互结束后,签名的泄露不会导致先前传输的消息 P 的泄露,即一个拥有有效签名的攻击者无法打开先前的消息 P.此外,对于授权者CA 来说,只要他不去恶意冒充 R1,即使他拥有有效签名也同样无法打开消息发送者 S 给 R1先前发送的消息 P.对于 BLISS-OSBE 方案,我们在发送者 S 和接收者 R1信息交互阶段增加交互的内容,即可实现其前向安全性,而这一改变不会影响 BLISS-OSBE 的安全性质.在信息交互阶段,接收者 R1选取随机向量 y1,y2 DZn,得到 y=(y1,y2)t,计算:Ay=a1 y1+y2.然后 R1将 X 连同 Ay一起发送给 S.于是,S 得到基于 RLWE2q,的加密方案的两套公钥(pk1,pk2)和(pk1,pk2),加密算法分别记为 lwe1和 lwe2.其中 pk1=a1mod 2q,pk2=Az=(a1 z1+z2)mod 2q,而 pk2=(a1 y1+y2)mod 2q.首先,发送者 S 随机选择产生 ks和 kr,以此来产生加密消息 P 的对称密钥K=H(ks kr).加密明文 P 得到 C=KP,其中 H 是公开的 Hash 函数.接着,使用基于 RLWE2q,的公钥加密算法 lwe1和对应公钥(pk1,pk2),加密 ks,得到 lwe1ks=(c1,c2);使用公钥加密算法 lwe2和对应公钥(pk1,pk2),加密 kr,得到 lwe2kr=(c1,c2).最后,S 将加密结果发送给 R:C(c1,c2)(c1,c2).在打开信封阶段,只有同时拥有签名 Sig=(z1,z2,c)和随机向量 y=(y1,y2)t的接收者 R1才能打开消息 P.认证方 CA 或拥有签名的攻击者不知道用于解密(c1,c2)的私钥 y1,无法解密获得 kr,因而无法得到共享密钥 K,最终在打开信封阶段无法打开消息 P.5参数选择与实验结果由于是基于 BLISS 签名的 OSBE 方案,因此考虑直接继承文献 10 中 BLISS 签名方案的参数设置.但是,需要注意到,本文的 OSBE 方案使用了以(a1,a1z1+z2)mod 2q 为公钥,z1为私钥的基于环R2q上 LWE 问题的公钥加密.作为签名的一部分,z1是一个服从离散高斯分布 DZn,的多项式.为了确保该 LWE 加密的安全性和解密的正确性,必须使得模数 2q 相对 足够大.需要说明的是,RLWEq,问题曾一度被认为只有模数 q 是素数的情况下才能被归约到格上的困难问题.直到 2017 年,Peikert 等人16证明了实际上对于任意的模数 q,RLWEq,问题都能被归约到格上的困难问题上.这使我们使用基于模数 2q 的 RLWE 问题(即 RLWE2q,问题),