nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

An Efficient Authenticated Key Exchange from Random Self-reducibility on CSIDH

verfasst von : Tomoki Kawashima, Katsuyuki Takashima, Yusuke Aikawa, Tsuyoshi Takagi

Erschienen in: Information Security and Cryptology – ICISC 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

SIDH and CSIDH are key exchange protocols based on isogenies and conjectured to be quantum-resistant. Since the protocols are similar to the classical Diffie–Hellman, they are vulnerable to the man-in-the-middle attack. A key exchange which is resistant to such an attack is called an authenticated key exchange (AKE), and many isogeny-based AKEs have been proposed. However, the parameter sizes of the existing schemes should be large since they all have relatively large security losses in security proofs. This is partially because the random self-reducibility of isogeny-based decisional problems has not been proved yet.

In this paper, we show that the computational problem and the gap problem of CSIDH are random self-reducible. A gap problem is a computational problem given access to the corresponding decision oracle. Moreover, we propose a CSIDH-based AKE with small security loss, following the construction of Cohn-Gordon et al. in CRYPTO 2019, as an application of the random self-reducibility of the gap problem of CSIDH. Our AKE is proved to be the fastest CSIDH-based AKE when we aim at 110-bit security level.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel (Quantum) Cryptanalysis of Misty Schemes

Nächstes Kapitel A Sub-linear Lattice-Based Submatrix Commitment Scheme

Nur mit Berechtigung zugänglich

Informally, a reduction is simple if the reduction runs the adversary only once.

As mentioned above, we assume that \(z = xy\) if and only if \(b = 1\) to avoid pathology.

Similarly, the proof of Cohn-Gordon et al. can be considered as an application of the random self-reducibility of the stDH problem.

In this case, the advantage of the adversary is zero.

Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Cryptology ePrint Archive, Report 2020/341 (2020). https://eprint.iacr.org/2020/341

Brendel, J., Fischlin, M., Günther, F., Janson, C., Stebila, D.: Towards post-quantum security for signal’s X3DH handshake. In: Selected Areas in Cryptography (SAC) (2020, to appear)

Canetti, R., Krawczyk, H.: Analysis of key-exchange protocols and their use for building secure channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453–474. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_28CrossRef

Castryck, W., Decru, T.: CSIDH on the surface. Cryptology ePrint Archive, Report 2019/1404 (2019). https://eprint.iacr.org/2019/1404

Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15CrossRef

Castryck, W., Sotáková, J., Vercauteren, F.: Breaking the decisional Diffie-Hellman problem for class group actions using genus theory. Cryptology ePrint Archive, Report 2020/151 (2020). https://eprint.iacr.org/2020/151

Cohn-Gordon, K., Cremers, C., Gjøsteen, K., Jacobsen, H., Jager, T.: Highly efficient key exchange protocols with optimal tightness. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 767–797. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_25CrossRef

Couveignes, J.-M.: Hard Homogeneous Spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291

de Kock, B., Gjøsteen, K., Veroni, M.: Practical isogeny-based key-exchange with optimal tightness. In: Selected Areas in Cryptography (SAC) 2020 (2020, to appear)

10.

Dobson, S., Galbraith, S.D.: On the degree-insensitive SI-GDH problem and assumption. Cryptology ePrint Archive, Report 2019/929 (2019). https://eprint.iacr.org/2019/929

11.

El Kaafarani, A., Katsumata, S., Pintore, F.: Lossy CSI-FiSh: efficient signature scheme with tight reduction to decisional CSIDH-512. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 157–186. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_6CrossRef

12.

Fujioka, A., Takashima, K., Terada, S., Yoneyama, K.: Supersingular isogeny Diffie-Hellman authenticated key exchange. In: ICISC 2018, pp. 177–195 (2018)

13.

Fujioka, A., Takashima, K., Yoneyama, K.: One-round authenticated group key exchange from isogenies. In: Steinfeld, R., Yuen, T.H. (eds.) ProvSec 2019. LNCS, vol. 11821, pp. 330–338. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31919-9_20CrossRef

14.

Galbraith, S.D.: Authenticated key exchange for SIDH. Cryptology ePrint Archive, Report 2018/266 (2018). https://eprint.iacr.org/2018/266

15.

Galbraith, S.D., Vercauteren, F.: Computational problems in supersingular elliptic curve isogenies. Quantum Inf. Process. 17(10), 265 (2018)MathSciNetCrossRef

16.

Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2CrossRefMATH

17.

Krawczyk, H.: HMQV: a high-performance secure Diffie-Hellman protocol. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_33CrossRef

18.

LaMacchia, B., Lauter, K., Mityagin, A.: Stronger security of authenticated key exchange. In: Susilo, W., Liu, J.K., Mu, Y. (eds.) ProvSec 2007. LNCS, vol. 4784, pp. 1–16. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75670-5_1CrossRefMATH

19.

Longa, P.: A Note on Post-Quantum Authenticated Key Exchange from Supersingular Isogenies. Cryptology ePrint Archive, Report 2018/267 (2018). https://eprint.iacr.org/2018/267

20.

Neukirch, J.: Algebraic Number Theory, vol. 322. Springer, Heidelberg (2013)MATH

21.

Okamoto, T., Pointcheval, D.: The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes. An Efficient Authenticated Key Exchange from Random Self-Reducibility on CSIDH. In: Public Key Cryptography 2001, pp. 104–118. Springer, Heidelberg (2001)

22.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef

23.

Xu, X., Xue, H., Wang, K., Au, M.H., Tian, S.: Strongly secure authenticated key exchange from supersingular isogenies. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 278–308. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_11CrossRef

Titel: An Efficient Authenticated Key Exchange from Random Self-reducibility on CSIDH
verfasst von: Tomoki Kawashima
Katsuyuki Takashima
Yusuke Aikawa
Tsuyoshi Takagi
Verlag: Springer International Publishing
Buch: Information Security and Cryptology – ICISC 2020
Print ISBN: 978-3-030-68889-9

Electronic ISBN: 978-3-030-68890-5

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-68890-5_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"