Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Authenticated logarithmic-order supersingular isogeny group key exchange

  • Regular Contribution
  • Published:
International Journal of Information Security Aims and scope Submit manuscript

Abstract

We present the first constant-round, tree-based, group key exchange protocol based on SIDH with logarithmic-order communication and memory complexity, where the only previous isogeny-based group key exchange, SIBD, has linear-order communication and memory complexity. We call our protocol the supersingular isogeny tree-based group key exchange (SIT). We show that our protocol satisfies post-quantum security through a reduction to the supersingular decisional Diffie–Hellman (SSDDH) problem in the security model of Manulis, Suzuki, and Ustaoglu. We also construct a peer-to-peer (sequential) version of SIT. Finally, we present a compiler that turns SIT into an authenticated group key exchange while maintaining the same complexity and security as SIT, resulting in the authenticated SIT group key exchange (A-SIT).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. There has been some doubt as to the veracity of the security proof for SIBD given by Furukawa, Kunihiro, and Takashima [9]. Takashima [21] defines a new hard problem and supplies a corresponding proof.

  2. https://sike.org/.

  3. Original TikZ code courtesy of De Feo via GitHub [6].

  4. The result in [8] holds in the authenticated-links adversarial model of Canetti and Krawczyk [5].

  5. The authors claim that their scheme may also easily be constructed for odd n; however, their indexing method does not allow for odd n.

  6. Although the original BDII scheme has no such concept, we introduce a ‘score’ for each party, needed in order to alternate SIDH bases so as to avoid the attack outlined in Note 1.

  7. \(\mathcal {D}\) needs at most \((2n-4)t_{isog}\) additional time to generate all the isogenies for the transcript, where \(t_{isog}\) is the amount of time needed to do a single SIDH isogeny computation.

  8. There exist other types of compilers for two-party AKEs (see for example [15, 18]) that may possibly be extended into compilers for AGKEs as well, but such work is outside the scope of this paper.

  9. This s may not be the same for each party in the protocol instance. See Sect. 2.1.

  10. \(\mathcal {P}_i|sID|0|r_i|\sigma \) can just be sent to all parties to eliminate the need to store a list of descendants, which in the case of \(\mathcal {P}_0\) and \(\mathcal {P}_1\) has size O(n).

  11. At most this requires one re-signing of a message when a party has to send the SIT protocol x value to a child (with which it has already exchanged more than one previous message) and its other descendants (with which it has sent at most one previous message).

  12. In doing so, we assume that broadcasting/multicasting a message does not depend on the number of receivers but that receiving l messages means that the receiver incurs a cost of l, even if all messages are received in a single round. The reason for this is that it takes into account that receiving messages requires being online and also storing said messages while broadcasting/multicasting is usually a one-time operation.

References

  1. Azarderakhsh R, Jalali A, Jao D, Soukharev V: Practical supersingular isogeny group key agreement. IACR Cryptol. ePrint Arch. (2019)

  2. Boyd C, Gellert K: A modern view on forward security. Cryptology ePrint Archive, Report 2019/1362 (2019). https://eprint.iacr.org/2019/1362

  3. Burmester, M., Desmedt, Y.: A secure and efficient conference key distribution system. In: De Santis, A. (ed.) Advances in Cryptology - EUROCRYPT94, pp. 275–286. Springer, Berlin (1995)

    Chapter  Google Scholar 

  4. Burmester M, Desmedt Y: Efficient and secure conference-key distribution. In: Proceedings of the International Workshop on Security Protocols, Springer, London (1997). http://dl.acm.org/citation.cfm?id=647214.720375

  5. Canetti R, Krawczyk H: Analysis of key-exchange protocols and their use for building secure channels. In: Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, EUROCRYPT ’01. Springer, London (2001). http://dl.acm.org/citation.cfm?id=647086.715688

  6. De Feo L, Jao D: defeo/sidh-paper. https://github.com/defeo/sidh-paper/blob/master/eprint.tex

  7. Desmedt, Y., Lange, T., Burmester, M.: Scalable authenticated tree based group key exchange for ad-hoc groups. In: Dietrich, S., Dhamija, R. (eds.) Financial Cryptography and Data Security, pp. 104–118. Springer, Berlin (2007)

    Chapter  Google Scholar 

  8. Feo, L.D., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014). https://doi.org/10.1515/jmc-2012-0015

    Article  MathSciNet  MATH  Google Scholar 

  9. Furukawa S, Kunihiro N, Takashima K: Multi-party key exchange protocols from supersingular isogenies. 2018 International Symposium on Information Theory and Its Applications (ISITA) 208–212 (2018)

  10. Galbraith SD: Authenticated key exchange for SIDH. IACR Cryptology ePrint Archive 2018, 266 (2018).http://eprint.iacr.org/2018/266

  11. Galbraith SD, Petit C, Shani B, Ti YB: On the security of supersingular isogeny cryptosystems. In: J.H. Cheon, T. Takagi (eds.) Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, Lecture Notes in Computer Science, 10031, 63–91 (2016). https://doi.org/10.1007/978-3-662-53887-6_3

  12. Günther, C.G.: An identity-based key-exchange protocol. In: Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology EUROCRYPT’89. Springer, Berlin (1990)

  13. Hatano T, Miyaji A, Sato T: T-robust scalable group key exchange protocol with o(log n) complexity. In: Proceedings of the 16th Australasian Conference on Information Security and Privacy, ACISP’. Springer, Berlin (2011). http://dl.acm.org/citation.cfm?id=2029853.2029870

  14. Hougaard HB, Miyaji A: SIT: supersingular isogeny tree-based group key exchange. In: 15th Asia Joint Conference on Information Security, AsiaJCIS 2020, Taipei. IEEE (2020). https://doi.org/10.1109/AsiaJCIS50894.2020.00019

  15. Jager T, Kohlar F, Schäge S, Schwenk J: Generic compilers for authenticated key exchange. In: Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science. Springer (2010). https://www.iacr.org/archive/asiacrypt2010/6477232/6477232.pdf

  16. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography. Springer, Berlin (2011)

    MATH  Google Scholar 

  17. Katz, J., Yung, M.: Scalable protocols for authenticated group key exchange. J. Cryptol. 20(1), 85–113 (2007)

    Article  MathSciNet  Google Scholar 

  18. Li, Y., Schäge, S., Yang, Z., Bader, C., Schwenk, J.: New modular compilers for authenticated key exchange. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) Applied Cryptography and Network Security. Springer International Publishing, Cham (2014)

    Google Scholar 

  19. Manulis, M., Suzuki, K., Ustaoglu, B.: Modeling leakage of ephemeral secrets in tripartite/group key exchange. In: Lee, D., Hong, S. (eds.) Information, Security and Cryptology - ICISC 2009, pp. 16–33. Springer, Berlin (2010)

    Chapter  Google Scholar 

  20. Silverman, J.H.: The arithmetic of elliptic curves graduate texts in mathematics. Springer, Dordrecht (2009)

    Book  Google Scholar 

  21. Takashima K: Post-quantum constant-round group key exchange from static assumptions. In: Takagi T, Wakayama M, Tanaka K, Kunihiro N, Kimoto K, Ikematsu Y (eds.) International Symposium on Mathematics, Quantum Theory, and Cryptography. Springer, Singapore (2021)

  22. Tang, Q., Mitchell, C.: Efficient compilers for authenticated group key exchange. In: Lecture Notes in Computer Science, vol. 3802, pp. 192–197. Springer (2006)

  23. Washington LC: Elliptic Curves: Number Theory and Cryptography, Second Edition, 2 edn. Chapman & Hall/CRC (2008)

Download references

Funding

This work is partially supported by enPiT (Education Network for Practical Information Technologies) at MEXT, and Innovation Platform for Society 5.0 at MEXT.

Author information

Authors and Affiliations

  1. Graduate School of Engineering, Osaka University, Osaka, Japan

    Hector B. Hougaard & Atsuko Miyaji

  2. Center for Quantum Information and Quantum Biology, Osaka University, Osaka, Japan

    Atsuko Miyaji

  3. Japan Advanced Institute of Science and Technology (JAIST), Nomi, Japan

    Atsuko Miyaji

Authors
  1. Hector B. Hougaard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Atsuko Miyaji
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hector B. Hougaard.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hougaard, H.B., Miyaji, A. Authenticated logarithmic-order supersingular isogeny group key exchange. Int. J. Inf. Secur. 21, 207–221 (2022). https://doi.org/10.1007/s10207-021-00549-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10207-021-00549-4

Keywords

Search

Navigation