Top

Published in:

2017 | OriginalPaper | Chapter

Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems

Authors : Steven D. Galbraith, Christophe Petit, Javier Silva

Published in: Advances in Cryptology – ASIACRYPT 2017

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We provide a new identification protocol and new signature schemes based on isogeny problems. Our identification protocol relies on the hardness of the endomorphism ring computation problem, arguably the hardest of all problems in this area, whereas the only previous scheme based on isogenies (due to De Feo, Jao and Plût) relied on potentially easier problems. The protocol makes novel use of an algorithm of Kohel-Lauter-Petit-Tignol for the quaternion version of the \(\ell \)-isogeny problem, for which we provide a more complete description and analysis. Our new signature schemes are derived from the identification protocols using the Fiat-Shamir (respectively, Unruh) transforms for classical (respectively, post-quantum) security. We study their efficiency, highlighting very small key sizes and reasonably efficient signing and verification algorithms.

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

next chapter An Existential Unforgeable Signature Scheme Based on Multivariate Quadratic Equations

Available only for authorised users

To some extent, Fiat-Shamir signatures are in fact not believed to be secure against quantum adversaries [33], although they can be proven to be secure under certain conditions [34] which the schemes presented do not verify.

These signatures schemes were independently proposed by Yoo et al. [42]; our versions have smaller signature sizes for the same security guarantees.

The special case \(E'=E\) occurs with negligible probability so it can be ignored.

One needs to pay close attention to the cases \(j=0\) and \(j=1728\) when counting isogenies, but this has no effect on our general schemes.

Random walks theorems are usually stated for a single graph whereas our walks will switch from one graph to another, all with the same vertex set but different edges.

In [26] an arbitrary Minkowski basis was chosen.

The reduced norm of an ideal element is the norm of this element divided by the norm of the ideal.

The exact procedure is irrelevant here.

Both signature sizes depend linearly on a parameter t which we fixed in a more conservative manner than Yoo et al. (see the full version of the paper for a discussion on this choice). With \(t=2\lambda \) their signatures are \(69\lambda ^2\) bits and ours are \(48\lambda ^2\) bits, and with \(t=3\lambda \) their signatures are \(\lceil 103.5\lambda ^2\rceil \) bits and ours are \(72\lambda ^2\) bits. Tables 1 and 2 report values for \(t=3\lambda \).

Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From identification to signatures via the fiat-shamir transform: minimizing assumptions for security and forward-security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 418–433. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_28 CrossRef

Alon, N., Benjamini, I., Lubetzky, E., Sodin, S.: Non-backtracking random walks mix faster. Commun. Contemp. Math. 9(4), 585–603 (2007)MathSciNetCrossRefMATH

Bellare, M., Poettering, B., Stebila, D.: From identification to signatures, tightly: a framework and generic transforms. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 435–464. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_15 CrossRef

Biasse, J.-F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428–442. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_25

Bisson, G., Sutherland, A.V.: Computing the endomorphism ring of an ordinary elliptic curve over a finite field. J. Number Theory 131(5), 815–831 (2011)MathSciNetCrossRefMATH

Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptol. 22(1), 93–113 (2009)MathSciNetCrossRefMATH

Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1–29 (2014)MathSciNetCrossRefMATH

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_21 CrossRef

Damgård, I.: On \(\sigma \)-protocols. University of Aarhus, Department for Computer Science, Lecture Notes (2010)

10.

Deligne, P.: La conjecture de Weil. I. Publications Mathématiques de l’Institut des Hautes Études Scientifiques 43(1), 273–307 (1974)MathSciNetCrossRefMATH

11.

Deuring, M.: Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 14, 197–272 (1941). https://doi.org/10.1007/BF02940746 MathSciNetCrossRefMATH

12.

Dewaghe, L.: Isogénie entre courbes elliptiques. Util. Math. 55, 123–127 (1999)MathSciNetMATH

13.

Feige, U., Fiat, A., Shamir, A.: Zero-knowledge proofs of identity. J. Cryptol. 1(2), 77–94 (1988)MathSciNetCrossRefMATH

14.

De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014)MathSciNetMATH

15.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12

16.

Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math 2, 118–138 (1999)MathSciNetCrossRefMATH

17.

Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3 CrossRef

18.

Galbraith, S.D., Petit, C., Silva, J.: Signature schemes based on supersingular isogeny problems. Cryptology ePrint Archive, Report 2016/1154 (2016). http://eprint.iacr.org/2016/1154

19.

Gélin, A., Wesolowski, B.: Loop-abort faults on supersingular isogeny cryptosystems. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 93–106. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_6 CrossRef

20.

Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. 43, 439–561 (2006)MathSciNetCrossRefMATH

21.

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_2 CrossRef

22.

Jao, D., Soukharev, V.: Isogeny-based quantum-resistant undeniable signatures. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 160–179. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_10

23.

Katz, J.: Digital Signatures. Springer, Heidelberg (2010)CrossRefMATH

24.

Kedlaya, K.S., Umans, C.: Fast polynomial factorization and modular composition. SIAM J. Comput. 40(6), 1767–1802 (2011)MathSciNetCrossRefMATH

25.

Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California, Berkeley (1996)

26.

Kohel, D., Lauter, K., Petit, C., Tignol, J.-P.: On the quaternion \(\ell \)-isogeny path problem. LMS J. Comput. Math. 17A, 418–432 (2014)MathSciNetCrossRefMATH

27.

Nguyen, P.Q., Stehlé, D.: Low-dimensional lattice basis reduction revisited. ACM Trans. Algorithms 5(4), 46 (2009)MathSciNetCrossRefMATH

28.

Petit, C.: On the quaternion \(\ell \)-isogeny problem. Presentation slides from a talk at the University of Neuchâtel, March 2015

29.

Petit, C.: Faster algorithms for isogeny problems using torsion point images. In: ASIACRYPT 2017 (2017, to appear). http://eprint.iacr.org/2017/571

30.

Pizer, A.K.: Ramanujan graphs and Hecke operators. Bull. Am. Math. Soc. 23(1), 127–137 (1990)MathSciNetCrossRefMATH

31.

Silverman, J.H.: The Arithmetic of Elliptic Curves. Springer, Heidelberg (1986)CrossRefMATH

32.

Ti, Y.B.: Fault attack on supersingular isogeny cryptosystems. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 107–122. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_7 CrossRef

33.

Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_25

34.

Unruh, D.: Post-quantum security of Fiat-Shamir. In: ASIACRYPT 2017 (2017, to appear). https://eprint.iacr.org/2017/398

35.

Venturi, D.: Zero-knowledge proofs and applications. University of Rome, Lecture Notes (2015)

36.

Vignéras, M.-F.: Arithmétique des algébres de quaternions. Springer, Heidelberg (1980)CrossRefMATH

37.

Voight, J.: Quaternion algebras (2017). https://math.dartmouth.edu/~jvoight/quat-book.pdf

38.

von zur Gathen, J., Shoup, V.: Computing Frobenius maps and factoring polynomials. Comput. Complex. 2, 187–224 (1992)MathSciNetCrossRefMATH

39.

Vélu, J.: Isogénies entre courbes elliptiques. Commun. de l’Académie royale des Sci. de Paris 273, 238–241 (1971)MATH

40.

Waterhouse, W.C.: Abelian varieties over finite fields. Ann. scientifiques de l’ENS 2, 521–560 (1969)MathSciNetMATH

41.

Xi, S., Tian, H., Wang, Y.: Toward quantum-resistant strong designated verifier signature from isogenies. Int. J. Grid Util. Comput. 5(2), 292–296 (2012)

42.

Yoo, Y., Azarderakhsh, R., Jalali, A., Jao, D., Soukharev, V.: A post-quantum digital signature scheme based on supersingular isogenies. In: Financial Crypto 2017 (2017)

Title: Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems
Authors: Steven D. Galbraith
Christophe Petit
Javier Silva
Publisher: Springer International Publishing
Book: Advances in Cryptology – ASIACRYPT 2017
Print ISBN: 978-3-319-70693-1

Electronic ISBN: 978-3-319-70694-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-70694-8_1

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