Towards isogeny-based password-authenticated key establishment. (English) Zbl 1464.94065
Summary: Password authenticated key establishment (PAKE) is a cryptographic primitive that allows two parties who share a low-entropy secret (a password) to securely establish cryptographic keys in the absence of public key infrastructure. We propose the first quantum-resistant password-authenticated key exchange scheme based on supersingular elliptic curve isogenies. The scheme is built upon supersingular isogeny Diffie-Hellman [D. Jao and L. De Feo, Lect. Notes Comput. Sci. 7071, 19–34 (2011; Zbl 1290.94094)], and uses the password to generate permutations which obscure the auxiliary points. We include elements of a security proof, and discuss roadblocks to obtaining a proof in the BPR model [M. Bellare et al., Lect. Notes Comput. Sci. 1807, 139–155 (2000; Zbl 1082.94533)]. We also include some performance results.
MSC:
| 94A62 | Authentication, digital signatures and secret sharing |
| 94A60 | Cryptography |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
| 68P25 | Data encryption (aspects in computer science) |
Keywords:
isogenies; password authenticated key establishment; key establishment; post-quantum cryptography; isogeny-based cryptography; authenticationSoftware:
NAXOSReferences:
| [1] | Mihir Bellare, David Pointcheval and Phillip Rogaway, Authenticated Key Exchange Secure against Dictionary Attacks, in: Advances in Cryptology— EUROCRYPT 2000 (Bart Preneel, ed.), pp. 139-155, Springer Berlin Heidelberg, Berlin, Heidelberg, 2000. · Zbl 1082.94533 |
| [2] | Mihir Bellare and Phillip Rogaway, Entity Authentication and Key Distribution, in: Advances in Cryptology — CRYPTO ’93 (Douglas R. Stinson, ed.), pp. 232-249, Springer Berlin Heidelberg, Berlin, Heidelberg, 1994. · Zbl 0870.94019 |
| [3] | Steven M. Bellovin and Michael Merritt, Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks, in: IEEE Symposium On Research In Security And Privacy, pp. 72-84, 1992. |
| [4] | Reinier Bröker, Denis Charles and Kristin Lauter, Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography, in: Proceedings of the 2nd International Conference on Pairing-Based Cryptography, pp. 100-112, 2008. · Zbl 1186.94428 |
| [5] | Ran Canetti and Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, in: EURO-CRYPT (Birgit Pfitzmann, ed.), Lecture Notes in Computer Science 2045, pp. 453-474, Springer, 2001. · Zbl 0981.94032 |
| [6] | Ran Canetti and Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, in: Advances in Cryptology—EUROCRYPT 2001 (Birgit Pfitzmann, ed.), pp. 453-474, Springer, Berlin, Heidelberg, 2001. · Zbl 0981.94032 |
| [7] | Denis Xavier Charles, Kristin E. Lauter and Eyal Z. Goren, Cryptographic Hash Functions from Expander Graphs, Journal of Cryptology 22 (2009), 93-113. · Zbl 1166.94006 |
| [8] | Anamaria Costache, Brooke Feigon, Kristin Lauter, Maike Massierer and Anna Puskas, Ramanujan graphs in cryptography, Research Directions in Number Theory: Women in Numbers IV, AWM Springer Series (to appear), 2019, https://eprint.iacr.org/2018/593 · Zbl 1457.94115 |
| [9] | Craig Costello, Patrick Longa and Michael Naehrig, Eflcient Algorithms for Supersingular Isogeny Difle-Hellman, in: Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I (Matthew Robshaw and Jonathan Katz, eds.), pp. 572-601, Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. · Zbl 1384.94046 |
| [10] | Jean-Marc Couveignes, Hard Homogeneous Spaces, 2006, http://eprint.iacr.org/2006/291/ |
| [11] | Luca De Feo, David Jao and Jérôme Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), 209-247. · Zbl 1372.94419 |
| [12] | Jintai Ding, Saed Alsayigh, Jean Lancrenon, Saraswathy RV and Michael Snook, Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World, in: Topics in Cryptology - CT-RSA 2017 (Helena Handschuh, ed.), pp. 183-204, Springer, Cham, 2017. · Zbl 1383.94052 |
| [13] | Steven D. Galbraith, Christophe Petit, Barak Shani and Yan Bo Ti, On the Security of Supersingular Isogeny Cryptosystems, in: Advances in Cryptology - ASIACRYPT 2016 (Jung Hee Cheon and Tsuyoshi Takagi, eds.), pp. 63-91, Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. · Zbl 1404.94073 |
| [14] | David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Geovandro Pereira, Joost Renes, Vladimir Soukharev and David Ubanik, Supersingular Isogeny Key Encapsulation, NIST Post-Quantum Cryptography Standardization Process, Report, 2019. |
| [15] | David Jao and Luca De Feo, Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies, in: PQCrypto (Bo-Yin Yang, ed.), Lecture Notes in Computer Science 7071, pp. 19-34, Springer, 2011. · Zbl 1290.94094 |
| [16] | David Jao and Vladimir Soukharev, A subexponential algorithm for evaluating large degree isogenies, Algorithmic number theory, Lecture Notes in Comput. Sci. 6197, Springer, Berlin, 2010, pp. 219-233. · Zbl 1260.11086 |
| [17] | Brian LaMacchia, Kristin Lauter and Anton Mityagin, Stronger Security of Authenticated Key Exchange, in: Provable Security: First International Conference (Willy Susilo, Joseph K. Liu and Yi Mu, eds.), pp. 1-16, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. · Zbl 1138.94381 |
| [18] | Jason LeGrow, Post-Quantum Security of Authenticated Key Establishment Protocols,Master’s thesis, University ofWaterloo, 2016. |
| [19] | Vadim Lyubashevsky, Chris Peikert and Oded Regev, On Ideal Lattices and Learning with Errors over Rings, in: Advances in Cryptology - EUROCRYPT 2010 (Henri Gilbert, ed.), pp. 1-23, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. · Zbl 1279.94099 |
| [20] | Alfred J. Menezes, Tatsuaki Okamoto and Scott A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory 39 (1993), 1639-1646. · Zbl 0801.94011 |
| [21] | Christophe Petit, Faster Algorithms for Isogeny Problems Using Torsion Point Images, in: Advances in Cryptology - ASI-ACRYPT 2017 (Tsuyoshi Takagi and Thomas Peyrin, eds.), pp. 330-353, Springer International Publishing, Cham, 2017. · Zbl 1409.94898 |
| [22] | S. Pohlig and M. Hellman, An Improved Algorithm for Computing Logarithms over and Its Cryptographic Significance (Corresp.), IEEE Trans. Inf. Theor. 24 (2006), 106-110. · Zbl 0375.68023 |
| [23] | Alexander Rostovtsev and Anton Stolbunov, Public-key cryptosystem based on isogenies, 2006, http://eprint.iacr.org/2006/145/ |
| [24] | Joseph H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics 106, Springer, New York, 1986. · Zbl 0585.14026 |
| [25] | Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics 106, Springer-Verlag, New York, 1992. · Zbl 0585.14026 |
| [26] | Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238-A241. · Zbl 0225.14014 |
| [27] | Jiang Zhang and Yu Yu, Two-Round PAKE from Approximate SPH and Instantiations from Lattices, in: Advances in Cryptology—ASIACRYPT 2017 (Tsuyoshi Takagi and Thomas Peyrin, eds.), pp. 37-67, Springer, Cham, 2017. · Zbl 1417.94088 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
