Research on password-authenticated key exchange protocol over lattices

Yuanbo GUO; Anqi YIN

doi:10.11959/j.issn.1000-436x.2022190

您当前的位置：

首页 >

文章列表页 >

Research on password-authenticated key exchange protocol over lattices

Comprehensive Reviews | 更新时间：2024-06-05

- Research on password-authenticated key exchange protocol over lattices
- Journal on Communications Vol. 43, Issue 12, Pages: 172-187(2022)
- 作者机构：
  
  信息工程大学密码工程学院，河南郑州 450001
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61501515)
- DOI：10.11959/j.issn.1000-436x.2022190
  CLC： TP393
- Online First：2022-12，
  
  Published：25 December 2022
- 稿件说明：
移动端阅览
Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices[J]. Journal on Communications, 2022, 43(12): 172-187.
DOI：

Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices[J]. Journal on Communications, 2022, 43(12): 172-187. DOI： 10.11959/j.issn.1000-436x.2022190.

摘要

量子计算技术的快速发展使基于传统困难问题的口令认证密钥交换（PAKE）协议在后量子时代面临严重的安全威胁。基于格的密码体制因高效性、高安全性，以及支持全同态加密和多线性映射等更强的密码服务功能，被美国NIST认证为后量子时代最具潜力的密码体制。首先系统地梳理格上PAKE协议的研究进展，主要包括格上集中式的两方、三方PAKE协议和分布式PAKE协议，然后分别对相关典型方案进行了对比分析，最后展望了格上PAKE协议的未来发展趋势。

Abstract

With the rapid development of quantum computing technology

password-authenticated key exchange (PAKE) protocol based on conventional difficult problems will face serious security threats in the post-quantum era.Lattice-based cryptosystem has been certified by NIST as the most promising cryptosystem in the post-quantum era due to its high efficiency

high security and support for stronger cryptographic service functions (such as fully homomorphic encryption and multi-linear mapping).Firstly

the research progress of lattice-based PAKE protocol was systematically sort out

mainly including the centralized two-party

three-party PAKE protocol and the distributed PAKE protocol over lattices.Then

the relevant typical schemes were compared and analyzed

respectively.Finally

the future research directions PAKE protocol over lattices were prospected.

关键词

Keywords

references

汪定 . 口令安全关键问题研究 [D ] . 北京:北京大学 , 2017 .

WANG D . Research on key issues in password security [D ] . Beijing:Peking University , 2017 .

张效林 , 谷大武 , 张驰 . 移动平台典型应用的身份认证问题研究 [J ] . 网络与信息安全学报 , 2020 , 6 ( 6 ): 137 - 151 .

ZHANG X L , GU D W , ZHANG C . Issues of identity verification of typical applications over mobile terminal platform [J ] . Chinese Journal of Network and Information Security , 2020 , 6 ( 6 ): 137 - 151 .

汪定 , 邹云开 , 陶义 , 等 . 基于循环神经网络和生成式对抗网络的口令猜测模型研究 [J ] . 计算机学报 , 2021 , 44 ( 8 ): 1519 - 1534 .

WANG D , ZOU Y K , TAO Y , et al . Password guessing based on recurrent neural networks and generative adversarial networks [J ] . Chinese Journal of Computers , 2021 , 44 ( 8 ): 1519 - 1534 .

郭宓文 . 密码,让百姓生活更安全 [N ] . 人民日报 , 2021 .

GUO B W . Password,let people live more secure [N ] . The People’s Daily , 2021 .

MIT Technology Review 2022年“全球十大突破性技术”解读 [J ] . 中国科学基金 , 2022 ( 3 ): 432 - 446 .

Interpretation of 2022 MIT technology review’s top 10 breakthrough technologies [J ] . Bulletin of National Natural Science Foundation of China , 2022 ( 3 ): 432 - 446 .

SHIN J S , JO M , HWANG J Y , et al . A verifier-based password-authenticated key exchange using tamper-proof hardware [J ] . The Computer Journal , 2021 , 64 ( 8 ): 1293 - 1302 .

WU T D , . The secure remote password protocol [C ] // Proceedings of Internet Society 1997 Symposium on Network and Distributed System Security . Piscataway:IEEE Press , 1997 : 97 - 111 .

MACKENZIE P . The PAK suite:protocols for password-authenticated key exchange [R ] . DIMACS Technical Report 2002-46 , 2002 .

BOYKO V , MACKENZIE P , PATEL S . Provably secure password-authenticated key exchange using diffie-Hellman [C ] // Advances in Cryptology — EUROCRYPT 2000 . Berlin:Springer , 2000 : 156 - 171 .

KATZ J , OSTROVSKY R , YUNG M . Efficient passwordauthenticated key exchange using human-memorable passwords [C ] // Lecture Notes in Computer Science . Berlin:Springer , 2001 : 475 - 494 .

GENNARO R , LINDELL Y . A framework for password-based authenticated key exchange1 [J ] . ACM Transactions on Information and System Security (TISSEC) , 2006 , 9 ( 2 ): 181 - 234 .

JIANG S , GONG G . Password based key exchange with mutual authentication [C ] // International Workshop on Selected Areas in Cryptography . Berlin:Springer , 2004 : 267 - 279 .

GROCE A , KATZ J . A new framework for efficient password-based authenticated key exchange [C ] // Proceedings of the 17th ACM Conference on Computer and Communications Security . New York:ACM Press , 2010 : 516 - 525 .

SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring [C ] // Proceedings 35th Annual Symposium on Foundations of Computer Science . Piscataway:IEEE Press , 1994 : 124 - 134 .

ROSS O H M . A review of quantum-inspired metaheuristics:going from classical computers to real quantum computers [J ] . IEEE Access , 2019 , 8 : 814 - 838 .

牟雁飞 . 基于格的数字签名和认证协议研究 [D ] . 上海:复旦大学 , 2014 .

MOU Y F . Research in lattice-based digital signature and identification protocols [D ] . Shanghai:Fudan University , 2014 .

张彦华 . 基于格的若干密码方案的设计与分析 [D ] . 西安:西安电子科技大学 , 2017 .

ZHANG Y H . Design and analysis of several lattice-based cryptographic schemes [D ] . Xi’an:Xidian University , 2017 .

MERKLE R C , . Protocols for public key cryptosystems [C ] // Proceedings of 1980 IEEE Symposium on Security and Privacy . Piscataway:IEEE Press , 1980 :122.

宋永成 , 黄欣沂 , 伍玮 , 等 . 基于编码的数字签名综述 [J ] . 网络与信息安全学报 , 2021 , 7 ( 4 ): 1 - 17 .

SONG Y C , HUANG X Y , WU W , et al . Survey of code-based digital signatures [J ] . Chinese Journal of Network and Information Security , 2021 , 7 ( 4 ): 1 - 17 .

PATARIN J , . Hidden fields equations (HFE) and isomorphisms of polynomials (IP):two new families of asymmetric algorithms [C ] // Advances in Cryptology — EUROCRYPT ’96 . Berlin:Springer , 1996 : 33 - 48 .

NEJATOLLAHI H , DUTT N , RAY S , et al . Post-quantum lattice-based cryptography implementations [J ] . ACM Computing Surveys , 2019 , 51 ( 6 ): 1 - 41 .

ASIF R . Post-quantum cryptosystems for Internet-of-things:a survey on lattice-based algorithms [J ] . IoT , 2021 , 2 ( 1 ): 71 - 91 .

SEYHAN K , NGUYEN T N , AKLEYLEK S , et al . Lattice-based cryptosystems for the security of resource-constrained IoT devices in post-quantum world:a survey [J ] . Cluster Computing , 2022 , 25 ( 3 ): 1729 - 1748 .

ALAYA B , LAOUAMER L , MSILINI N . Homomorphic encryption systems statement:trends and challenges [J ] . Computer Science Review , 2020 ,36:100235.

ALAGIC G , ALPERIN-SHERIFF J ,, APON D , et al . Status report on the second round of the NIST post-quantum cryptography standardization process [R ] . NIST , 2020 .

BELLARE M , POINTCHEVAL D , ROGAWAY P . Authenticated key exchange secure against dictionary attacks [C ] // International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2000 : 139 - 155 .

BRESSON E , CHEVASSUT O , POINTCHEVAL D . Security proofs for an efficient password-based key exchange [C ] // Proceedings of the 10th ACM Conference on Computer and Communications Security . New York:ACM Press , 2003 : 241 - 250 .

MACKENZIE P , PATEL S , SWAMINATHAN R . Passwordauthenticated key exchange based on RSA [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Berlin:Springer , 2000 : 599 - 613 .

ABDALLA M , BENHAMOUDA F , POINTCHEVAL D . Disjunctions for hash proof systems:New constructions and applications [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2015 : 69 - 100 .

ABDALLA M , CHEVALIER C , POINTCHEVAL D . Smooth projective hashing for conditionally extractable commitments [C ] // Advances in Cryptology - CRYPTO 2009 . Berlin:Springer , 2009 : 671 - 689 .

BENHAMOUDA F , BLAZY O , CHEVALIER C , et al . New techniques for SPHFs and efficient one-round PAKE protocols [C ] // Advances in Cryptology – CRYPTO 2013,Berlin:Springer , 2013 : 449 - 475 .

CANETTI R , HALEVI S , KATZ J , et al . Universally composable password-based key exchange [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2005 : 404 - 421 .

KATZ J , VAIKUNTANATHAN V . Round-optimal password-based authenticated key exchange [C ] // Theory of Cryptography . Berlin:Springer , 2011 : 293 - 310 .

MITTELBACH A , FISCHLIN M . The theory of hash functions and random oracles [M ] . Cham : Springer International Publishing , 2021 .

BONEH D , DAGDELEN Ö , FISCHLIN M , et al . Random oracles in a quantum world [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Berlin:Springer , 2011 : 41 - 69 .

CHIESA A , MANOHAR P , SPOONER N . Succinct arguments in the quantum random oracle model [C ] // Theory of Cryptography Conference . Berlin:Springer , 2019 : 1 - 29 .

KATZ J , VAIKUNTANATHAN V . Smooth projective hashing and password-based authenticated key exchange from lattices [C ] // Advances in Cryptology - ASIACRYPT 2009 . Berlin:Springer , 2009 : 636 - 652 .

WANG D , WANG P . On the implications of Zipf’s law in passwords [C ] // European Symposium on Research in Computer Security . Berlin:Springer , 2016 : 111 - 131 .

YANG K Y , HU X X , ZHANG Q H , et al . VAEPass:a lightweight passwords guessing model based on variational auto-encoder [J ] . Computers ＆ Security , 2022 ,114:102587.

FUN T S , AHMEDY F , FOO Z M , et al . Enhanced password-based authentication mechanism in cloud computing with extended honey encryption (XHE):a case study on diabetes dataset [C ] // Advances in Computer,Communication and Computational Sciences . Berlin:Springer , 2021 : 65 - 74 .

PEIKERT C . A decade of lattice cryptography [J ] . Foundations and Trends® in Theoretical Computer Science , 2016 , 10 ( 4 ): 283 - 424 .

BANERJEE A , PEIKERT C , ROSEN A . Pseudorandom functions and lattices [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2012 : 719 - 737 .

GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions [C ] // Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing . New York:ACM Press , 2008 : 197 - 206 .

LI Z , WANG D . Two-round PAKE protocol over lattices without NIZK [C ] // International Conference on Information Security and Cryptology . Berlin:Springer , 2018 : 138 - 159 .

REGEV O . On lattices,learning with errors,random linear codes,and cryptography [J ] . Journal of the ACM , 2009 , 56 ( 6 ): 1 - 40 .

叶茂 . 基于格的口令认证密钥交换协议和相关加密算法研究 [D ] . 郑州:信息工程大学 , 2013 .

YE M . Research on password-based authenticated key exchange protocols and associated encryption algorithms from lattices [D ] . Zhengzhou:Information Engineering University , 2013 .

CRAMER R , SHOUP V . Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption [C ] // International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2002 : 45 - 64 .

BENHAMOUDA F , BLAZY O , DUCAS L , et al . Hash proof systems over lattices revisited [C ] // IACR International Workshop on Public Key Cryptography . Berlin:Springer , 2018 : 644 - 674 .

BELLARE M , ROGAWAY P . Entity authentication and key distribution [C ] // Annual International Cryptology Conference . Berlin:Springer , 1993 : 232 - 249 .

BELLARE M , ROGAWAY P . Provably secure session key distribution:the three party case [C ] // Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing . New York:ACM Press , 1995 : 57 - 66 .

BLAKE-WILSON S , JOHNSON D , MENEZES A . Key agreement protocols and their security analysis [C ] // Crytography and Coding . Berlin:Springer , 1997 : 30 - 45 .

MACKENZIE P . Secure network authentication with password identification [R ] . IEEE P1363 Working Group , 1999 .

GUO Y M , ZHANG Z F , GUO Y J . Anonymous authenticated key agreement and group proof protocol for wearable computing [J ] . IEEE Transactions on Mobile Computing , 2022 , 21 ( 8 ): 2718 - 2731 .

LI Z P , WANG D , MORAIS E . Quantum-safe round-optimal password authentication for mobile devices [J ] . IEEE Transactions on Dependable and Secure Computing , 2022 , 19 ( 3 ): 1885 - 1899 .

DING Y , FAN L . Efficient password-based authenticated key exchange from lattices [C ] // Proceedings of 2011 Seventh International Conference on Computational Intelligence and Security . Piscataway:IEEE Press , 2011 : 934 - 938 .

BLAZY O , CHEVALIER C , DUCAS L , et al . Exact smooth projective hash function based on LWE [J ] . Cryptology ePrint Archive , 2013 :173107.

ZHANG J , YU Y . Two-round PAKE from approximate SPH and instantiations from lattices [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Berlin:Springer , 2017 : 37 - 67 .

ABDALLA M , BENHAMOUDA F , POINTCHEVAL D . Public-key encryption indistinguishable under plaintext-checkable attacks [J ] . IET Information Security , 2016 , 10 ( 6 ): 288 - 303 .

MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2012 : 700 - 718 .

尹安琪 , 曲彤洲 , 郭渊博 , 等 . 格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议 [J ] . 电子学报 , 2022 , 50 ( 5 ): 1140 - 1149 .

YIN A Q , QU T Z , GUO Y B , et al . Provably secure two-round PAKE based on ciphertext standard language over lattices [J ] . Acta Electronica Sinica , 2022 , 50 ( 5 ): 1140 - 1149 .

LI Z P , WANG D . Achieving one-round password-based authenticated key exchange over lattices [J ] . IEEE Transactions on Services Computing , 2022 , 15 ( 1 ): 308 - 321 .

LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2010 : 1 - 23 .

叶茂 , 胡学先 , 刘文芬 . 基于理想格的近似平滑投射 Hash 函数 [J ] . 信息工程大学学报 , 2013 , 14 ( 1 ): 13 - 21 .

YE M , HU X X , LIU W F . Approximate smooth projective hash functions from ideal lattices [J ] . Journal of Information Engineering University , 2013 , 14 ( 1 ): 13 - 21 .

ATANI R E , ATANI S E , KARBASI A H . A new ring-based SPHF and PAKE protocol on ideal lattices [J ] . The ISC International Journal of Information Security , 2019 , 11 ( 1 ): 75 - 86 .

KATZ J , OSTROVSKY R , YUNG M . Efficient and secure authenticated key exchange using weak passwords [J ] . Journal of the ACM , 2009 , 57 ( 1 ): 1 - 39 .

DING J , ALSAYIGH S , LANCRENON J , et al . Provably secure password authenticated key exchange based on RLWE for the post-quantum world [C ] // Topics in Cryptology – CT-RSA 2017 . Berlin:Springer , 2017 : 183 - 204 .

GAO X , DING J , LIU J , et al . Post-quantum secure remote password protocol from RLWE problem [C ] // International Conference on Information Security and Cryptology . Berlin:Springer , 2017 : 99 - 116 .

舒琴 , 王圣宝 , 路凡义 , 等 . 基于理想格的通用可组合两方口令认证密钥交换协议 [J ] . 电子与信息学报 , 2021 , 43 ( 6 ): 1756 - 1763 .

SHU Q , WANG S B , LU F Y , et al . Universally composable two-party password-based authenticated key exchange from ideal lattices [J ] . Journal of Electronics ＆ Information Technology , 2021 , 43 ( 6 ): 1756 - 1763 .

FENG Q , HE D B , ZEADALLY S , et al . Ideal lattice-based anonymous authentication protocol for mobile devices [J ] . IEEE Systems Journal , 2019 , 13 ( 3 ): 2775 - 2785 .

DABRA V , BALA A J , KUMARI S . LBA-PAKE:lattice-based anonymous password authenticated key exchange for mobile devices [J ] . IEEE Systems Journal , 2021 , 15 ( 4 ): 5067 - 5077 .

DING J , SARASWATHY R , ALSAYIGH S , et al . How to validate the secret of a ring learning with errors (RLWE) key [J ] . Cryptology ePrint Archive , 2018 :2018/081.

DING R Y , CHENG C , QIN Y . Further analysis and improvements of a lattice-based anonymous PAKE scheme [J ] . IEEE Systems Journal , 2022 , 16 ( 3 ): 5035 - 5043 .

GAO X W , DING J T , LI L , et al . Practical randomized RLWE-based key exchange against signal leakage attack [J ] . IEEE Transactions on Computers , 2018 , 67 ( 11 ): 1584 - 1593 .

WANG Q X , WANG D , CHENG C , et al . Quantum2FA:efficient quantum-resistant two-factor authentication scheme for mobile devices [J ] . IEEE Transactions on Dependable and Secure Computing , 2021 ,doi:10.1109/TDSC.2021.3129512.

ABDALLA M , FOUQUE P A , POINTCHEVAL D . Password-based authenticated key exchange in the three-party setting [C ] // Public Key Cryptography - PKC 2005 . Berlin:Springer , 2005 : 65 - 84 .

ALKIM E , DUCAS L , PöPPELMANN T , , et al . NewHope without reconciliation [J ] . Cryptology ePrint Archive , 2016 :2016/1157.

KEITH M , SHAO B , STEINBART P J . The usability of passphrases for authentication:an empirical field study [J ] . International Journal of Human-Computer Studies , 2007 , 65 ( 1 ): 17 - 28 .

叶茂 , 胡学先 , 刘文芬 . 基于格的三方口令认证密钥交换协议 [J ] . 电子与信息学报 , 2013 , 35 ( 6 ): 1376 - 1381 .

YE M , HU X X , LIU W F . Password authenticated key exchange protocol in the three party setting based on lattices [J ] . Journal of Electronics ＆ Information Technology , 2013 , 35 ( 6 ): 1376 - 1381 .

XU D , HE D , CHOO K-K R , et al . Provably secure three-party password authenticated key exchange protocol based on ring learning with error [J ] . Cryptology ePrint Archive , 2017 :173311.

于金霞 , 廉欢欢 , 汤永利 , 等 . 格上基于口令的三方认证密钥交换协议 [J ] . 通信学报 , 2018 , 39 ( 11 ): 87 - 97 .

YU J X , LIAN H H , TANG Y L , et al . Password-based three-party authenticated key exchange protocol from lattices [J ] . Journal on Communications , 2018 , 39 ( 11 ): 87 - 97 .

YIN A Q , GUO Y B , SONG Y M , et al . Two-round password-based authenticated key exchange from lattices [J ] . Wireless Communications and Mobile Computing,2020 , 2020 :8893628.

ROY P S , DUTTA S , SUSILO W , et al . Password protected secret sharing from lattices [C ] // International Conference on Applied Cryptography and Network Security . Berlin:Springer , 2021 : 442 - 459 .

尹安琪 , 郭渊博 , 汪定 , 等 . 可证明安全的抗量子两服务器口令认证密钥交换协议 [J ] . 通信学报 , 2022 , 43 ( 3 ): 14 - 29 .

YIN A Q , GUO Y B , WANG D , et al . Provably secure quantum resistance two-server password-authenticated key exchange protocol [J ] . Journal on Communications , 2022 , 43 ( 3 ): 14 - 29 .

GONG L , LOMAS M A , NEEDHAM R M , et al . Protecting poorly chosen secrets from guessing attacks [J ] . IEEE Journal on Selected Areas in Communications , 1993 , 11 ( 5 ): 648 - 656 .

HALEVI S , KRAWCZYK H . Public-key cryptography and password protocols [J ] . ACM Transactions on Information and System Security , 1999 , 2 ( 3 ): 230 - 268 .

YI X , HAO F , BERTINO E . ID-based two-server password-authenticated key exchange [C ] // European Symposium on Research in Computer Security . Berlin:Springer , 2014 : 257 - 276 .

YI X , RAO F Y , TARI Z , et al . ID2S password-authenticated key exchange protocols [J ] . IEEE Transactions on Computers , 2016 , 65 ( 12 ): 3687 - 3701 .

RAIMONDO D M , GENNARO R . Provably secure threshold password-authenticated key exchange [C ] // International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2003 : 507 - 523 .

KATZ J , MACKENZIE P , TABAN G , et al . Two-server password-only authenticated key exchange [C ] // International Conference on Applied Cryptography and Network Security . Berlin:Springer , 2005 : 1 - 16 .

Views

1292

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Provably secure quantum resistance two-server password-authenticated key exchange protocol

Lattice-based verifiable timed signature and application

Lattice-based lightweight post quantum access authentication scheme for satellite network

CDBS: blind signature scheme based on CRYSTALS-Dilithium algorithm

Post-quantum verifier-based three-party password authenticated key exchange protocol

Related Author

Yuanbo GUO

Ding WANG

Tongzhou QU

Lin CHEN

Anqi YIN

XIN Hongcai

TAN Shuncong

WANG Ke

Related Institution

College of Cyber Science, Nankai University

Tianjin Key Laboratory of Network and Data Security Technology, Nankai University

Department of Cryptology Science and Technology, Beijing Electronic Science and Technology Institute

School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications

AI问答

⁰