logo

SCIENTIA SINICA Informationis, Volume 51 , Issue 8 : 1375(2021) https://doi.org/10.1360/SSI-2020-0177

Achieving password-hashing scheme over lattices

More info
  • ReceivedJun 16, 2020
  • AcceptedAug 19, 2020
  • PublishedAug 9, 2021

Abstract


Funded by

国家自然科学基金(61802006,61802214)

山东省国家自然科学基金(ZR2019BF009)

青岛市应用基础研究计划青年专项基金(19-6-2-6-cg)


References

[1] Pointcheval D, Zimmer S. Multi-factor authenticated key exchange. In: Proceedings of the 6th International Conference Applied Cryptography and Network Security, New York, 2008. 277--295. Google Scholar

[2] Gardham D, Manulis M, Dragan C C. Biometric-authenticated searchable encryption. IACR Cryptol ePrint Arch, 2020, 2020: 17. Google Scholar

[3] Dupont P, Hesse J, Pointcheval D, et al. Fuzzy password-authenticated key exchange. In: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, 2018. 393--424. Google Scholar

[4] Bonneau J, Herley C, van Oorschot P C, et al. Passwords and the evolution of imperfect authentication. Commun ACM 2015, 58: 78--87. Google Scholar

[5] Wang P, Wang D, Huang X. Advances in password security (in Chinese). Journal of Computer Research and Development, 2016, 53: 2173. Google Scholar

[6] Weir M, Aggarwal S, de Medeiros B, et al. Password cracking using probabilistic context-free grammars. In: Proceedings of the 30th IEEE Symposium on Security and Privacy. Oakland: IEEE Computer Society, 2009. 391--405. Google Scholar

[7] Hitaj B, Gasti P, Ateniese G, et al. Passgan: a deep learning approach for password guessing. In: Proceedings of the 17th International Conference on Applied Cryptography and Network Security, Bogota, 2019. 217--237. Google Scholar

[8] Juels A, Rivest R L. Honeywords: making password-cracking detectable. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, 2013. 145--160. Google Scholar

[9] Wang D, Cheng H, Wang P, et al. A security analysis of honeywords. In: Proceedings of the Network and Distributed System Security Symposium, 2018. 1--16. Google Scholar

[10] Wu J. A non-technical history of password storage. Technical Report, 2017. https://analogist.net/post/password-storage/. Google Scholar

[11] Grassi P A, Newton E M, Perlner R A, et al. uppercaseNIST 800-63B digital identity guidelines: Authentication and lifecycle management. Technical Report, National Institute of Standards and Technology, McLean, 2017. https://doi.org/10.6028/NIST.SP.800-63b. Google Scholar

[12] Li Z, Wang D. Two-round PAKE protocol over lattices without NIZK In: Proceedings of the 14th International Conference on Information Security and Cryptology, Fuzhou, 2018. 138--159. Google Scholar

[13] Hu X, Zhang J, Zhang Z. Universally composable anonymous password authenticated key exchange. Sci China Inf Sci, 2017, 60: 52107 CrossRef Google Scholar

[14] Li Z, Wang J, Choi C, et al. Multi-factor password-authenticated key exchange via pythia prf service. Computers, Materials & Continua, 2020, 63(2):663--674. Google Scholar

[15] Benhamouda F, Blazy O, Chevalier C, et al. New techniques for sphfs and efficient one-round pake protocols. In: Proceedings of Annual Cryptology Conference, 2013. 449--475. Google Scholar

[16] Bellovin S M, Merritt M. Encrypted key exchange: password-based protocols secure against dictionary attacks. In: Proceedings of the 1992 IEEE Symposium on Security and Privacy, 1992. 72--84. Google Scholar

[17] Katz J, Ostrovsky R, Yung M. Efficient password-authenticated key exchange using human-memorable passwords. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, 2001. 475--494. Google Scholar

[18] Li Z, Wang D. Achieving One-Round Password-based Authenticated Key Exchange over Lattices. IEEE Trans Serv Comput, 2019, : 1-1 CrossRef Google Scholar

[19] Jarecki S, Krawczyk H, Xu J. OPAQUE: an asymmetric PAKE protocol secure against pre-computation attacks. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018. 456--486. Google Scholar

[20] Benhamouda F, Pointcheval D. Verifier-based password-authenticated key exchange: New models and constructions. Cryptology ePrint Archive, Report 2013/833. https://eprint.iacr.org/2013/833. Google Scholar

[21] Kiefer F, Manulis M. Zero-knowledge password policy checks and verifier-based PAKE In: Proceedings of European Symposium on Research in Computer Security, 2014. 295--312. Google Scholar

[22] Kiefer F, Manulis M. Blind password registration for verifier-based PAKE In: Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, 2016. 39--48. Google Scholar

[23] Pointcheval D, Wang G. VTBPEKE: verifier-based two-basis password exponential key exchange. In: Proceedings of ACM on Asia Conference on Computer & Communications Security, 2017. 301--312. Google Scholar

[24] Nguyen K, Tan B H M, Wang H. Zero-knowledge password policy check from lattices. In: Proceedings of International Conference on Information Security, 2017. 92--113. Google Scholar

[25] Bellovin S M, Merritt M. Augmented encrypted key exchange: a password-based protocol secure against dictionary attacks and password file compromise. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, 1993. 244--250. Google Scholar

[26] Gentry C, MacKenzie P D, Ramzan Z. A method for making password-based key exchange resilient to server compromise. In: Proceedings of the 26th Annual International Conference on Advances in Cryptology, 2006. 142--159. Google Scholar

[27] Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans Inform Theor, 1985, 31: 469-472 CrossRef Google Scholar

[28] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques, 1999. 223--238. Google Scholar

[29] Boneh D, Goh E, Nissim K. Evaluating 2-DNF formulas on ciphertexts. In: Proceedings of Theory of Cryptography Conference, 2005. 325--341. Google Scholar

[30] Fujisaki E, Okamoto T. Statistical zero knowledge protocols to prove modular polynomial relations. In: Proceedings of the 17th Annual International Cryptology Conference, Santa Barbara, 1997. 16--30. Google Scholar

[31] Damgård I, Fujisaki E. A statistically-hiding integer commitment scheme based on groups with hidden order. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2002. 125--142. Google Scholar

[32] Damgård I, Nielsen J B. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, 2002. 581--596. Google Scholar

[33] Boyen X, Waters B. Compact group signatures without random oracles. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2006. 427--444. Google Scholar

[34] Groth J. Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Proceedings of the 12th International Conference on Theory and Application of Cryptology and Information Security, 2006. 444--459. Google Scholar

[35] Groth J, Sahai A. Efficient non-interactive proof systems for bilinear groups. In: Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2008. 415--432. Google Scholar

[36] Bauman E, Lu Y, Lin Z. Half a century of practice: who is still storing plaintext passwords? In: Proceedings of the 11th International Conference on Information Security Practice and Experience, 2015. 253--267. Google Scholar

[37] Jaeger D, Pelchen C, Graupner H, et al. Analysis of publicly leaked credentials and the long story of password (re-) use. In: Proceedings of the 11th International Conference on Passwords (PASSWORDS'16), 2016. Google Scholar

[38] Kaliski B. Pkcs #5: Password-based cryptography specification version 2.0. Request for Comments: 2898. https://tools.ietf.org/html/rfc2898. Google Scholar

[39] Aumasson J P. Password Hashing Competition and Our Recommendation for Hashing Passwords: Argon2. Technical Report, 2019. http://www.password-hashing.net/. Google Scholar

[40] Hatzivasilis G. Password-Hashing Status. Cryptography, 2017, 1: 10 CrossRef Google Scholar

[41] Leurent G, Nguyen P Q. How risky is the random-oracle model? In: Proceedings of Annual International Cryptology Conference, 2009. 445--464. Google Scholar

[42] Nist. Recommendation for password-based key derivation. Special Publication 800-132. 2010. http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-13~2.pdf. Google Scholar

[43] Wang D, Wang P, He D, et al. Birthday, name and bifacial-security: Understanding passwords of chinese web users. In: Proceedings of the 28th USENIX Conference on Security Symposium, 2019. 1537--1555. Google Scholar

[44] Wang D, Cheng H, Wang P. Zipf's Law in Passwords. IEEE TransInformForensic Secur, 2017, 12: 2776-2791 CrossRef Google Scholar

[45] Bonneau J. The science of guessing: analyzing an anonymized corpus of 70 million passwords. In: Proceedings of IEEE Symposium on Security and Privacy, 2012. 538--552. Google Scholar

[46] Wang D, Gu Q, Huang X, et al. Understanding human-chosen pins: characteristics, distribution and security. In: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, 2017. 372--385. Google Scholar

[47] Shannon C E. A mathematical theory of communication. Mobile Computing and Communications Review, 2001, 5(1):3--55. Google Scholar

[48] Li Z, Wang J, Zhang W. Revisiting post-quantum hash proof systems over lattices for Internet of Thing authentications. J Ambient Intell Human Comput, 2020, 11: 3337-3347 CrossRef Google Scholar

[49] Percival C. A future-adaptable password scheme. The OpenBSD Project, 2009. https://www.tarsnap.com/scrypt/scrypt.pdf. Google Scholar

[50] Biryukov A, Dinu D, Khovratovich D. Argon2: the memory-hard function for password hashing and other applications. https://www.cryptolux.org/images/0/0d/Argon2.pdf~. Google Scholar

[51] Cabarcas D, Demirel D, Göpfert F, et al. An unconditionally hiding and long-term binding post-quantum commitment scheme. IACR Cryptology ePrint Archive, Report 2013/833. Google Scholar

[52] Baum C, Damgård I, Lyubashevsky V, et al. More efficient commitments from structured lattice assumptions. In: Proceedings of International Conference on Security and Cryptography for Networks 2018. 368--385. Google Scholar

[53] Kawachi A, Tanaka K, Xagawa K. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In: Proceedings of International Conference on the Theory & Application of Cryptology & Information Security: Advances in Cryptology, 2008. 372--389. Google Scholar

  • Table 1   Comparison with commitment-based password hashing schemes
    Character Cabarcas et al. [51] Baum et al. [52] Kawachi et al. [53]
    Assumption RLWE RLWE RLWE
    Commitment key ${\boldsymbol~A}=({\boldsymbol~A}_1,~{\boldsymbol~A}_2)\in\mathbb{Z}_q^{m\times~(n+k)}$ ${\boldsymbol~A}:=[ ~~~~~~~~~~~~~~~~~~~~~~~~~~~{\tiny~\begin{array}{c} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{\boldsymbol~A}_1~\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{\boldsymbol~A}_2~\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~\end{array}} ~~~~~~~~~~~~~~~~~~~~~~~~~~]\in~\mathbb{R}_q^{(n+\ell)\times~k}$ ${\boldsymbol~P}=({\boldsymbol~A},~{\boldsymbol~B})\in\mathbb{Z}_q^{n\times~(\ell+m)}$
    Plaintext space ${\boldsymbol~m}\in\mathbb{Z}_q^n$ ${\boldsymbol~m}\in\mathbb{R}_q^{(n+\ell)\times~1}$ ${\boldsymbol~m}\in\{0,1\}^{m}$
    Commitment value ${\boldsymbol~A}_1\cdot~{\boldsymbol~m}+~{\boldsymbol~A}_2\cdot~{\boldsymbol~s}~+{\boldsymbol~e}~\in\mathbb{Z}_q^m$ $[ ~~~~~~~~~~~{\tiny~\begin{array}{c} ~~~~~~~~~~~~~~~{\boldsymbol~A}_1~\\ ~~~~~~~~~~~~~~~{\boldsymbol~A}_2~\\ ~~~~~~~~~~~~\end{array}} ~~~~~~~~]~\cdot~{\boldsymbol~r}~+ ~~~~~~~~[ ~~~~~~~~~~~~{\tiny\begin{array}{c} ~~~~~~~~~~~~~~~\mathbf{0}^n~\\ ~~~~~~~~~~~~~~~{\boldsymbol~m}~\\ ~~~~~~~~~~~~\end{array}} ~~~~~~~~]~\in\mathbb{R}_q^{(n+\ell)\times~1}$ ${\boldsymbol~A}\cdot~{\boldsymbol~m}~+{\boldsymbol~B}\cdot~{\boldsymbol~r}~\in\mathbb{Z}_q^{n\times~1}$
    Pre-salt value $\overline{s}:={\boldsymbol~s}\in\mathbb{Z}_q^k$ $\overline{s}:={\boldsymbol~s}\in\mathbb{Z}_q^k$ $\overline{s}:={\boldsymbol~s}~\in\mathbb{Z}_q^k$
    Salt value $s:={\boldsymbol~B}\cdot~{\boldsymbol~e}_0\in\mathbb{Z}_q^m$ $s:={\boldsymbol~e}={\boldsymbol~s}\cdot~{\boldsymbol~B}~\in\mathbb{Z}_q^k$ $s:={\boldsymbol~r}\in\mathbb{Z}_q^m$
    PreHash ${\boldsymbol~A}\cdot ~~~~~~~[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~\mathsf{pwd}~\\ ~~~~~~{\boldsymbol~s}\\ ~~~~~~\end{array}} ~~~~~~]~\in~\mathbb{Z}_q^m$ $[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~{\boldsymbol~A}_1~\\ ~~~~~~{\boldsymbol~A}_2~\\ ~~~~~~\end{array}} ~~~~~~]~\cdot~{\boldsymbol~s}+ ~~~~~~~~~~~~[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~\mathbf{0}^n~\\ ~~~~~~\mathsf{pwd}\\ ~~~~~~\end{array}} ~~~~~~]\in\mathbb{Z}_q^m$ ${\boldsymbol~A}[ ~~~~~{\tiny~\begin{array}{c} ~~~~~~{\boldsymbol~s}~\\ ~~~~~~\mathsf{pwd}~\\ ~~~~~~\end{array}} ~~~~~~]\in\mathbb{Z}_q^n$
    PHash ${\boldsymbol~A}\cdot ~~~~~~~[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~\mathsf{pwd}~\\ ~~~~~~{\boldsymbol~s}~\\ ~~~~~~\end{array}} ~~~~~~]~+~2{\boldsymbol~e}~\in~\mathbb{Z}_q^m$ $~[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~{\boldsymbol~A}_1~\\ ~~~~~~{\boldsymbol~A}_2~\\ ~~~~~~\end{array}} ~~~~~~]~\cdot~{\boldsymbol~e}~+ ~~~~~~~~~~~~[ ~~~~~~{\tiny\begin{array}{c} ~~~~~~\mathbf{0}^n~\\ ~~~~~~\mathsf{pwd}\\ ~~~~~~\end{array}} ~~~~~~]\in~\mathbb{Z}_q^m~$ ${\boldsymbol~A}~[ ~~~~~{\tiny~\begin{array}{c} ~~~~~~{\boldsymbol~s}~\\ ~~~~~~{\boldsymbol~m}~\\ ~~~~~~\end{array}} ~~~~~~]~+~{\boldsymbol~B}{\boldsymbol~r}\in~\mathbb{Z}_q^n$
qqqq

Contact and support