Top

Published in:

2021 | OriginalPaper | Chapter

An Alternative Approach for SIDH Arithmetic

Authors : Cyril Bouvier, Laurent Imbert

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we present new algorithms for the field arithmetic layers of supersingular isogeny Diffie-Hellman; one of the fifteen remaining candidates in the NIST post-quantum standardization process. Our approach uses a polynomial representation of the field elements together with mechanisms to keep the coefficients within bounds during the arithmetic operations. We present timings and comparisons for SIKEp503 and suggest a novel 736-bit prime that offers a \(1.17\times \) speedup compared to SIKEp751 for a similar level of security.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter QCCA-Secure Generic Key Encapsulation Mechanism with Tighter Security in the Quantum Random Oracle Model

next chapter The Convergence of Slide-Type Reductions

With \(p_A=2\).

We use commit 4eb51ae0 (few commits after tag version 3.3).

Alagic, G., et al.: Status report on the second round of the NIST post-quantum cryptography standardization process. Technical report NISTIR 8309, National Institute of Standards and Technology, U.S. Department of Commerce, July 2020. https://doi.org/10.6028/NIST.IR.8309

Bajard, J.-C., Imbert, L., Plantard, T.: Arithmetic operations in the polynomial modular number system. In: Proceedings of the 17th IEEE Symposium on Computer Arithmetic, ARITH17, pp. 206–213. IEEE Computer Society (2005). https://doi.org/10.1109/ARITH.2005.11

Bajard, J.-C., Marrez, J., Plantard, T., Véron, P.: On polynomial modular number systems over \(\mathbb{Z}/p\mathbb{Z}\) (2020). https://hal.sorbonne-universite.fr/hal-02883341

Bos, J.W., Friedberger, S.: Faster modular arithmetic for isogeny-based crypto on embedded devices. J. Cryptogr. Eng. 10(2), 97–109 (2020). https://doi.org/10.1007/s13389-019-00214-6

Buchanan, W., Woodward, A.: Will quantum computers be the end of public key encryption? J. Cyber Secur. Technol. 1(1), 1–22 (2017). https://doi.org/10.1080/23742917.2016.1226650CrossRef

Costello, C.: Supersingular isogeny key exchange for beginners. In: Paterson, K.G., Stebila, D. (eds.) SAC 2019. LNCS, vol. 11959, pp. 21–50. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-38471-5_2CrossRef

Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 572–601. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_21CrossRef

Faz-Hernández, A., López-Hernández, J.C., Ochoa-Jiménez, E., Rodríguez-Henríquez, F.: A faster software implementation of the supersingular isogeny diffie-hellman key exchange protocol. IEEE Trans. Comput. 67(11), 1622–1636 (2018). https://doi.org/10.1109/TC.2017.2771535

De Feo, L.: Mathematics of isogeny based cryptography (2017)

10.

Galbraith, S.D., Vercauteren, F.: Computational problems in supersingular elliptic curve isogenies. Cryptology ePrint Archive, Report 2017/774 (2017). https://eprint.iacr.org/2017/774

11.

Jao, D., et al.: SIKE - supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization project (2017), sike.org

12.

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

13.

Karmakar, A., Roy, S.S., Vercauteren, F., Verbauwhede, I.: Efficient finite field multiplication for isogeny based post quantum cryptography. In: Duquesne, S., Petkova-Nikova, S. (eds.) WAIFI 2016. LNCS, vol. 10064, pp. 193–207. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-55227-9_14CrossRefMATH

14.

Longa, P., et al.: PQCrypto-SIDH (2020). https://github.com/microsoft/PQCrypto-SIDH

15.

Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)MathSciNetCrossRef

16.

Negre, C., Plantard, T.: Efficient modular arithmetic in adapted modular number system using Lagrange representation. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 463–477. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70500-0_34CrossRef

17.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994). https://doi.org/10.1109/sfcs.1994.365700

18.

Smith, B.: Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies. In: Budaghyan, L., Rodríguez-Henríquez, F. (eds.) WAIFI 2018. LNCS, vol. 11321, pp. 3–40. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05153-2_1

19.

Tian, J., Wang, P., Liu, Z., Lin, J., Wang, Z., Großschadl, J.: Faster Software Implementation of the SIKE Protocol Based on A New Data Representation. Cryptology ePrint Archive, Report 2020/660 (2020). https://eprint.iacr.org/2020/660

Title: An Alternative Approach for SIDH Arithmetic
Authors: Cyril Bouvier
Laurent Imbert
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2021
Print ISBN: 978-3-030-75244-6

Electronic ISBN: 978-3-030-75245-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-75245-3_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner