Group Key Establishment in a Quantum-Future Scenario
Volume 31, Issue 4 (2020), pp. 751–768
Pub. online: 15 September 2020
Type: Research Article
Open Access
Open Access
Received
1 February 2020
1 February 2020
Accepted
1 August 2020
1 August 2020
Published
15 September 2020
15 September 2020
Abstract
In cryptography, key establishment protocols are often the starting point paving the way towards secure execution of different tasks. Namely, the parties seeking to achieve some cryptographic task, often start by establishing a common high-entropy secret that will eventually be used to secure their communication. In this paper, we put forward a security model for group key establishment ($\mathsf{GAKE}$) with an adversary that may execute efficient quantum algorithms, yet only once the execution of the protocol has concluded. This captures a situation in which keys are to be established in the present, while security guarantees must still be provided in the future when quantum resources may be accessible to a potential adversary.
Further, we propose a protocol design that can be proven secure in this model. Our proposal uses password authentication and builds upon efficient and reasonably well understood primitives: a message authentication code and a post-quantum key encapsulation mechanism. The hybrid structure dodges potential efficiency downsides, like large signatures, of some “true” post-quantum authentication techniques, making our protocol a potentially interesting fit for current applications with long-term security needs.
References
Abdalla, M., Bohli, J., Vasco, M.I.G., Steinwandt, R. (2007). (Password) Authenticated key establishment: from 2-party to group. In: Vadhan, S.P. (Ed.), Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007, Proceedings, Lecture Notes in Computer Science, Vol. 4392. Springer, Amsterdam, The Netherlands, pp. 499–514.
Apon, D., Dachman-Soled, D., Gong, H., Katz, J. (2019). Constant-round group key exchange from the ring-LWE assumption. In: Ding, J., Steinwandt, R. (Eds.), Post-Quantum Cryptography – 10th International Conference PQCrypto 2019, Chongqing, China, May 8–10, 2019, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 11505. Springer, pp. 189–205.
Azarderakhsh, R., Campagna, M., Costello, C., Feo, L., Hess, B., Jalali, A., Jao, D., Koziel, B., LaMacchia, B., Longa, P. et al. (2017). SIKE – Supersingular Isogeny Key Encapsulation. https://sike.org/.
Benhamouda, F., Blazy, O., Ducas, L., Quach, W. (2018). Hash proof systems over lattices revisited. In: Abdalla, M., Dahab, R. (Eds.), Public-Key Cryptography – PKC 2018 – 21st IACR International Conference on Practice and Theory of Public-Key Cryptography. Rio de Janeiro, Brazil, March 25–29, 2018, Proceedings, Part II, Lecture Notes in Computer Science, Vol. 10770. Springer, pp. 644–674.
Bernstein, D., Chou, T., Lange, T., von Maurich I, Misoczki, R., Niederhagen, R., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Wang, W. (2017a). Classic McEliece. https://classic.mceliece.org/.
Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C. (2017b). Reducing attack surface at low cost. In: Adams, C., Camenisch, J., (Eds.), Selected Areas in Cryptography – SAC 2017 – 24th International Conference, Ottawa, ON, Canada, August 16–18, 2017, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 10719. Springer, pp. 235–260.
Bindel, N., Herath, U., McKague, M., Stebila, D. (2017). Transitioning to a quantum-resistant public key infrastructure. In: Lange, T., Takagi, T. (Eds.), Post-Quantum Cryptography – 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26–28, 2017, Proceedings, Lecture Notes in Computer Science, Vol. 10346. Springer, pp. 384–405.
Boneh, D., Glass, D., Krashen, D., Lauter, K.E., Sharif, S., Silverberg, A., Tibouchi, M., Zhandry, M. (2018). Multiparty non-interactive key exchange and more from isogenies on elliptic curves. CoRR. abs/1807.03038.
Bos, J.W., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D. (2016). Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (Eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24–28, 2016. ACM, pp. 1006–1018.
Bos, J.W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehlé, D. (2018). CRYSTALS – kyber: A CCA-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018, London, United Kingdom, April, 24–26, 2018. IEEE, pp. 353–367.
Bresson, E., Chevassut, O., Pointcheval, D., Quisquater, J. (2001). Provably authenticated group Diffie-Hellman key exchange. In: Reiter, M.K., Samarati, P. (Eds.), CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6–8, 2001. ACM, pp. 255–264.
Ding, J., Gao, X., Takagi, T., Wang, Y. (2019a). One sample ring-LWE with rounding and its application to key exchange. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (Eds.), Applied Cryptography and Network Security – 17th International Conference, ACNS 2019, Bogota, Colombia, June 5–7, 2019, Proceedings, Lecture Notes in Computer Science, Vol. 11464. Springer, pp. 323–343.
Ding, J., Schmitt, K., Zhang, Z. (2019b). A key exchange based on the short integer solution problem and the learning with errors problem. In: Carlet, C., Guilley, S., Nitaj, A., Souidi, E.M. (Eds.), Codes, Cryptology and Information Security – Third International Conference, C2S 2019, Rabat, Morocco, April 22–24, 2019, Proceedings – In Honor of Said El Hajji, Lecture Notes in Computer Science, Vol. 11445. Springer, pp. 105–117.
Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D. (2012). Message authentication. In: Pointcheval, D., Johansson, T. (Eds.), Advances in Cryptology – EUROCRYPT 2012 – 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15–19, 2012, Proceedings, Lecture Notes in Computer Science, Vol. 7237. Springer, pp. 355–374.
Katz, J., Vaikuntanathan, V. (2009). Smooth projective hashing and password-based authenticated key exchange from lattices. In: Matsui, M. (Ed.), Advances in Cryptology – ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009, Proceedings, Lecture Notes in Computer Science, Vol. 5912. Springer, pp. 636–652.
National Institute of Standards and Technology (2019). Post-Quantum Cryptography; Round 2 Submissions. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.
Biographies
González Vasco María Isabel
M.I. González Vasco is associate professor at MACIMTE, Universidad Rey Juan Carlos, where she works since 2003. She received her diploma and PhD degree in mathematics from the Universidad de Oviedo (1999 and 2003). Her research interests include provable security for cryptographic constructions, with special focus on public key cryptographic designs for encryption and group key exchange. She is currently a member of the Board of Directors (Junta de Gobierno) of the Royal Spanish Mathematical Society.
Pérez del Pozo Ángel L.
A.L. Pérez del Pozo is assistant professor (profesor ayudante doctor) at the Universidad Rey Juan Carlos, Spain. He holds a PhD in Mathematics from Universidad Complutense de Madrid (Spain). His main research focus is cryptographic designs for key exchange in non-standard scenarios, secret sharing schemes, and applications of multi-party computation.
Steinwandt Rainer
R. Steinwandt serves as Chair of Florida Atlantic University’s Department of Mathematical Sciences. Before joining FAU, he was with the University of Karlsruhe in Germany, where he completed his MS and PhD degrees in computer science, researching topics in computer algebra. Today, his research focus is in cryptology, including quantum cryptanalysis and quantum-safe cryptography. He currently serves as director of FAU’s Center for Cryptology and Information Security. His research has been funded through the Air Force Research Laboratory, the German Federal Office for Information Security, the National Science Foundation, and the NATO Science for Peace and Security program.
