可證明安全的后量子兩方口令認證密鑰協商協議

作者簡介：倪亮（1975－），男，遼寧葫蘆島人，副教授，博士，主要研究方向為網絡安全和密碼學（niliang402@zut.edu.cn）；張亞偉（1997－），男，河南蘭考人，碩士研究生，主要研究方向為網絡安全與密碼學；王念平（1973－），男，教授，博士，主要研究方向為信息安全和密碼學；周恒昇（1997－），男，碩士研究生，主要研究方向為網絡安全與密碼學；劉笑顏（1998－），女，碩士研究生，主要研究方向為網絡安全與密碼學；谷兵珂（1996－），男，碩士研究生，主要研究方向為網絡安全與密碼學.

摘 要：口令認證密鑰協商可以在客戶機和服務器之間建立安全的遠程通信，且可以將一個低熵口令放大為一個高熵的會話密鑰。然而，隨著量子計算技術的快速發展，基于大數分解和離散對數等經典數學難題的PAKA協議面臨著嚴峻的安全挑戰。因此，為了構建一個高效安全的后量子PAKA協議，依據改進的Bellare-Pointcheval-Rogaway（BPR）模型，提出了一個基于格的匿名兩方PAKA協議，并且使用給出嚴格的形式化安全證明。性能分析結果表明，該方案與相關的PAKA協議相比，在安全性和執行效率等方面有一定優勢，更適用于資源受限的物聯網（Internet of Things，IoT）智能移動設備。

關鍵詞：口令認證密鑰協商；基于格的密碼；環上帶誤差學習；可證明安全；抗離線字典攻擊

中圖分類號：TP309 文獻標志碼：A

文章編號：1001－3695（2023）04－040－1208－06

doi：10.19734/j.issn.1001-3695.2022.07.0377

Abstract：Password authentication key agreement can not only establish secure remote communication between client and server，but also amplify a low-entropy password into a high-entropy session key.However，with the rapid development of quantum computing technology，PAKA protocol based on classical mathematical problems such as large number decomposition and discrete logarithm is facing serious security challenges.Thus，in order to construct an efficient and secure post-quantum PAKA protocol，this paper proposed a post-quantum lattice-based anonymous two-party PAKA protocol based on the improved BPR model and gave a strict formal security proof.The performance analysis results show that compared with the related PAKA protocol，the proposed protocol has some advantages in security and execution efficiency.So it is more suitable for resource-constrained Internet of Things smart mobile devices.

Key words：password authenticated key agreement（PAKA）；lattice-based cryptography；ring learning with error；provable security；resistance to offline dictionary attacks

0 引言

口令便于人類記憶且避免了使用公鑰基礎設施（public key infrastructure，PKI），也無須使用硬件存儲。因此，口令成為了一種普遍的認證方法[1，2]。

口令認證密鑰協商協議（password authenticated key agreement，PAKA）是認證密鑰協商協議的一個重要研究分支，它支持通信雙方（如服務器和持有智能設備的用戶）在不安全的公開網絡上使用簡單的低熵口令協商出高熵會話密鑰，與其他認證方式相比效率較高。但是隨著量子計算機的快速發展，基于傳統數學難題的加密算法無法保障安全，越來越多的學者和學術團體開始研究抗量子算法，基于格的算法憑借其簡單、高效和并行性成為后量子密碼算法的研究熱點。但是早期的基于格的方案著重于密鑰協商而不是互相認證，如文獻［3］。直到2017年，Ding等人[4]提出了一個基于理想格的PAKA協議，不過該方案的通信開銷太大，實際執行難度較大。Gao等人[5]對Ding方案[4]進行了優化，并且給出了一種適合于數論變換（number theoretic transforms，NTT）算法的參數集，但該參數集沒有考慮通信負擔。此外Feng等人[6]引入了一種用于移動設備的匿名密鑰協商協議。在隨機預言模型（random oracle model，ROM）中給出了安全性證明，Rana等人[7]提出了一個基于環上帶誤差學習問題（ring lear-ning with error，RLWE）的PAKA協議，并與其他方案進行了比較。在文獻［6，7］提出的兩方PAKA協議的啟發下，本文對文獻［7］基于隨機預言模型PAKA協議的改進后，構造了一個基于RLWE的2輪匿名PAKA協議，并且在改進的Bellare-Pointcheval-Rogaway（BPR）模型[8]中進行了嚴格的安全證明，本文改進如下：a）使用累積分布函數齊普夫法則模型（cumulative distribution function Zipf’s law，CDF-Zipf）[9]模擬敵手的在線攻擊能力；b）為了簡化證明，本文提出帶誤差配對問題（pairing with error，PWE）。將安全證明降低為可抗在線字典攻擊的證明，并證明所提方案滿足前向安全性，且與相關方案相比執行效率較高，更適用于資源受限的物聯網設備。

1 預備知識

在介紹預備知識之前，先介紹相關的符號說明，如表1所示。

性能對比結果表明，所提PAKA協議在公鑰尺寸相同的情況下，安全性能更高，與文獻［5～7］相比，所提協議通過減少環上的運算次數，降低了通信輪數和計算開銷。

4 結束語

本文基于RLWE問題的難解性，提出了一種格上匿名兩方PAKA協議，所提協議可抗目前已知的量子計算攻擊和服務器泄露以及離線字典攻擊。在認證階段服務器和用戶之間僅需要交互一次信息，無須使用簽名、驗簽、同態加密等開銷較大的密碼源語，且在改進的BPR模型下進行了嚴格的安全性證明。與相關方案相比，其提高了執行效率。下一步考慮使用LWE困難問題設計更為安全高效的后量子匿名口令認證協議。

參考文獻：

［1］Islam M Z，Ali R，Haider A，et al.A reinforcement learning-based personalized adaptability knowledge extraction strategy for adaptive lear-ning systems［J］.IEEE Access，2021，9（1）：155123-155137.

［2］Zhang Yuan，Xu Chunxiang，Li Hongwei，et al.Efficient password-based threshold single-sign-on authentication for mobile users against perpetual leakage［J］.IEEE Trans on Mobile Computing，2021，20（6）：2297-2312.

［3］Ding Jintai，Xie Xiang，Lin Xiaodong.A simple provably secure key exchange scheme based on the learning with errors problem［EB/OL］.（2012）［2022-07-03］.https：//ia.cr/2012/688.

［4］Ding Jintai，Alsayigh S，Lancrenon J，et al.Provably secure password authenticated key exchange based on RLWE for the post-quantum world［C］//Proc of Cryptographers’ Track at RSA Conference.Cham：Springer，2017：183-204.

［5］Gao Xinwei，Ding Jintai，Li Lin，et al.Efficient implementation of password-based authenticated key exchange from RLWE and post-quantum TLS［EB/OL］.（2017-12-18）［2022-07-03］.https：//ia.cr/2017/1192.

［6］Feng Qi，He Debiao，Zeadally S，et al.Ideal lattice-based anonymous authentication protocol for mobile devices［J］.IEEE Systems Journal，2019，13（3）：2775-2785.

［7］Rana S，Mishra D.Lattice-based key exchange protocol under ring-LWE problem for IoT-enabled smart devices［J］.Sādhan，2021，46（84）：83-94.

［8］Bellare M ，Pointcheval D，Rogaway P.Authenticated key exchange secure against dictionary attacks［C］//Proc of EUROCRYPT.Berlin：Springer，2000：139-155.

［9］Wang Ding，Cheng Haibo，Wang Ping，et al.Zipf’s law in passwords［J］.IEEE Trans on Information Forensics and Security，2017，12（11）：2776-2791.

［10］Ajtai M.Generating hard instances of lattice problems［C］//Proc of the 28th Annual ACM Symposium on Theory of Computing.New York：ACM Press，1996：99-108

［11］Micciancio D.Generalized compact knapsacks cyclic lattices and efficient one-way functions［J］.Computational Complexity，2007，16（4）：365-411.

［12］舒琴，王圣寶，胡斌，等.格上兩方口令認證密鑰交換協議研究綜述［J］.杭州師范大學學報：自然科學版，2021，20（5）：463-470.（Shu Qin，Wang Shengbao，Hu Bin，et al.A survey of two party password authentication key exchange protocol on lattice［J］.Journal of Hangzhou Normal University：Natural Science Edition，2021，20（5）：463-470.）

［13］Ren Peixin，Gu Xiaozhuo.Practical post-quantum password-authenticated key exchange based-on module-lattice［C］//Proc of International Conference on Information Security and Cryptology.Cham：Springer，2022：137-156.

［14］李子臣，謝婷，張卷美.基于RLWE問題的后量子口令認證密鑰交換協議［J］.電子學報，2021，49（2）：260-267.（Li Zichen，Xie Ting，Zhang Juanmei.Post-quantum password authenticated key exchange protocol based on RLWE problem［J］.Acta Electronic Sinica，2021，49（2）：260-267.）

［15］Dharminder D，Chandran K P.LWESM：learning with error based secure communication in mobile devices using fuzzy extractor［J］.Journal of Ambient Intelligence and Humanized Computing，2020，11（1）：4089-4100.

［16］羅璇，曹天杰.改進的抵抗離線字典攻擊的口令更新協議［J］.計算機工程與應用，2009，45（25）：118-120.（Luo Xuan，Cao Tianjie.Improved password update protocol against offline dictionary attack［J］.Computer Engineering and Applications，2009，45（25）：118-120.）

［17］Aguilar-Melchor C ，Barrier J ，Guelton S ，et al.NFLLIB：NTT-based fast lattice library［C］//Proc of Cryptographers’ Track at the RSA Confe-rence.Cham：Springer，2016：341-356.

［18］Dabra V，Bala A，Kumari S.LBA-PAKA：lattice-based anonymous password authenticated key exchange for mobile devices［J］.IEEE Systems Journal，2021，15（1）：5067-5077.

［19］Yao Hailong，Wang Caifen，Fu Xingbing，et al.A privacy-preserving RLWE-based remote biometric authentication scheme for single and multi-server environments［J］.IEEE Access，2019，7：109597-109611.

［20］廉歡歡，侯慧瑩，趙運磊.后量子基于驗證元的三方口令認證密鑰交換協議［J］.通信學報，2022，43（4）：95-106.（Lian Huanhuan，Hou Huiying，Zhao Yunlei.Postquantum three-party password authentication key exchange protocol based on verification element［J］.Journal on Communications，2022，43（4）：95-106.）

［21］尹安琪，郭淵博，汪定，等.可證明安全的抗量子兩服務器口令認證密鑰交換協議［J］.通信學報，2022，43（3）：14-29.（Yin Anqi，Guo Yuanbo，Wang Ding，et al.Demonstrably secure quantum-proof two-server password authentication key exchange protocol［J］.Journal on Communications，2022，43（3）：14-29.）