可证明安全的抗量子高效口令认证密钥交换协议  

Provably Secure Quantum Resistance Efficient Password-Authenticated Key Exchange Protocol

作　　者：尹安琪 汪定 郭渊博 陈琳 唐迪 YIN An-Qi;WANG Ding;GUO Yuan-Bo;CHEN Lin;TANG Di(College of Electronic Technology,Information Engineering University,Zhengzhou 450001;College of Cyber Science,Nankai University,Tianjin 300350;Tianjin Key Laboratory of Network and Data Security Technology(Nankai University),Tianjin 300350)

机构地区：[1]信息工程大学电子技术学院,郑州450001 [2]南开大学网络空间安全学院,天津300350 [3]天津市网络与数据安全技术重点实验室(南开大学),天津300350

出　　处：《计算机学报》2022年第11期2321-2336,共16页Chinese Journal of Computers

基　　金：国家自然科学基金(62172240);京津冀基础研究合作专项(21JCZXJC00100)资助.

摘　　要：基于格的口令认证密钥交换(Password-Authenticated Key Exchange,PAKE)协议在后量子时代具有广泛的应用前景.降低通信轮次可以有效提高执行效率,也是格上PAKE协议的重要优化方向.现有基于格的低轮次PAKE协议的构建方法主要有两种:一种是基于非交互式零知识(Non-Interactive Zero-Knowledge,NIZK)证明,但在标准模型下如何在格上实现NIZK证明仍然是公开问题;另一种虽然宣称基于不可区分适应性选择密文攻击(Indistinguishability under Adaptive Chosen-Ciphertext Attack,IND-CCA2)的安全模型,但实际上只采用了不可区分性选择密文攻击(Indistinguishability under Chosen-Ciphertext Attack,IND-CCA1)安全的公钥加密(Public Key Encryption,PKE)方案,该类PAKE协议在现实应用时需要利用签名/验签等技术才能保证安全性.这两种方法都会增加计算和通信开销.为此,本文利用带误差学习(Learning with Errors,LWE)问题的加法同态属性,提出了一种格上IND-CCA2安全的非适应性平滑投影哈希函数(Smooth Projective Hash Function,SPHF),该函数支持一轮PAKE协议的构造;并确定了所基于的PKE方案中相关参数的大小,从而消除了LWE问题的不完全加法同态属性对SPHF正确性的影响.尽所知,这是格上第一个直接基于IND-CCA2安全模型的非适应性SPHF,且该SPHF具有相对独立的研究价值,可应用于证据加密、零知识证明和不经意传输等领域.基于此,本文构建了一种格上可证明安全的高效PAKE协议.该协议可以抵御量子攻击;只需要一轮通信,因而具有最优的通信轮次;是基于标准模型,所以避免了使用随机预言机的潜在安全威胁,特别是使用随机预言机可能导致格上PAKE协议遭受离线口令猜测攻击和量子攻击;在实际应用时,该协议也不需要利用NIZK证明和签名/验签等技术来保证安全性,这有效提高了执行效率.本文还利用人人网474万口令数据验证了基于CDF-Zipf定律的PAKE协�Password-Authenticated Key Exchange(PAKE) protocol has a wide application prospect in the coming post-quantum era.Scaling down the number of communication rounds is capable of effectively improving the execution efficiency,and this is a rather important direction for optimizing PAKE protocols over lattices.Up to now,there are mainly two technical routes in the existing literature guiding the construction of low-round PAKE schemes over lattices.One is based on Non-Interactive Zero-Knowledge(NIZK) proofs,but how to implement NIZK proofs in the standard model over lattices is still an open question for these derivative schemes;the other one is nominally designed as Indistinguishability under Adaptive Chosen-Ciphertext Attack(INDCCA2) secure based protocol,nevertheless it applies only an Indistinguishability under ChosenCiphertext Attack(IND-CCA1) secure based Public Key Encryption(PKE) scheme in implementation,which relies on the introduction of signature/verification algorithms or other techniques to ensure its security in implementation.Moreover,these two methods will introduce extra computation and communication costs.Therefore,taking advantage of the additive homomorphic property of the Learning with Errors(LWE) problem,this paper proposes an INDCCA2 secure word-independent Smooth Projective Hash Function(SPHF) over lattices,which also supports the construction of one-round PAKE protocols.And this paper identifies the exact values of parameters of the PKE scheme that the proposed SPHF predicates on,ultimately eliminate the influence of the incomplete additive homomorphic property of the LWE problem on the correctness of the SPHF.As far as we know,so mentioned function is the first IND-CCA2 secure word-independent SPHF over lattices.Besides,the proposed SPHF possesses independent research value and great application potential in multiple practice fields such as witness encryption,zero-knowledge proof,oblivious transmission and so on.On this basis,this paper innovatively designs an efficient provably secure PAKE p

关 键 词：抗量子 非适应性平滑投影哈希函数 高效 加法同态 口令认证密钥交换协议 可证明安全 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]