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

作者：尹安琪; 汪定^*; 郭渊博; 陈琳; 唐迪

来源：计算机学报, 2022, 45(11): 2321-2336.

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

基于格的口令认证密钥交换(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协议安全模型可以更加准确地评估PAKE协议所提供的安全强度;最后基于该安全性模型,本文在标准模型下对所提出的PAKE协议进行了严格的安全性证明.实验结果表明,与其它相关协议相比,本文协议具有最优的整体执行效率和最低的通信开销.

• 单位
  南开大学; 信息工程大学