Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems

Springer Science and Business Media LLC - Tập 33 - Trang 130-175 - 2019
Steven D. Galbraith1, Christophe Petit2, Javier Silva3
1Mathematics Department, University of Auckland, Auckland, New Zealand
2School of Computer Science, University of Birmingham, Birmingham, UK
3Universitat Pompeu Fabra, Barcelona, Spain

Tóm tắt

We present signature schemes whose security relies on computational assumptions relating to isogeny graphs of supersingular elliptic curves. We give two schemes, both of them based on interactive identification protocols. The first identification protocol is due to De Feo, Jao and Plût. The second one, and the main contribution of the paper, makes novel use of an algorithm of Kohel, Lauter, Petit and Tignol for the quaternion version of the $$\ell $$-isogeny problem, for which we provide a more complete description and analysis, and is based on a more standard and potentially stronger computational problem. Both identification protocols lead to signatures that are existentially unforgeable under chosen message attacks in the random oracle model using the well-known Fiat-Shamir transform, and in the quantum random oracle model using another transform due to Unruh. A version of the first signature scheme was independently published by Yoo, Azarderakhsh, Jalali, Jao and Soukharev. This is the full version of a paper published at ASIACRYPT 2017.

Tài liệu tham khảo

M. Abdalla, J.H. An, M. Bellare, C. Namprempre, From identification to signatures via the Fiat–Shamir transform: minimizing assumptions for security and forward-security, in L.R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science (Springer, 2002), pp. 418–433

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

R. Azarderakhsh, D. Jao, K. Kalach, B. Koziel, C. Leonardi, Key compression for isogeny-based cryptosystems, in AsiaPKC ’16 (ACM, New York, NY, USA, 2016), pp. 1–10

R. Beals, S. Brierley, O. Gray, A.W. Harrow, S. Kutin, N. Linden, D. Shepherd, M. Stather, Efficient distributed quantum computing. Proc. R. Soc. A 469(2153), 20120686 (2013)

M. Bellare, B. Poettering, D. Stebila, From identification to signatures, tightly: a framework and generic transforms, in J.H. Cheon, T. Takagi, editors, ASIACRYPT 2016, volume 10032 of Lecture Notes in Computer Science (Springer, 2016), pp. 435–464

D.J. Bernstein, Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?, in SHARCS’09 Special-purpose Hardware for Attacking Cryptographic Systems, p. 105 (2009)

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Cryptographic sponge functions. Submission to NIST (Round 3) (2011)

J.-F. Biasse, D. Jao, A. Sankar, A quantum algorithm for computing isogenies between supersingular elliptic curves, in W. Meier, D. Mukhopadhyay, editors, INDOCRYPT 2014, volume 8885 of Lecture Notes in Computer Science (Springer, 2014), pp. 428–442

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

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

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

C. Costello, P. Longa, M. Naehrig, Efficient algorithms for supersingular isogeny Diffie–Hellman, in M. Robshaw, J. Katz, editors, CRYPTO 2016, volume 9814 of Lecture Notes in Computer Science (Springer, 2016), pp. 572–601

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

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

M. Deuring, 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

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

K. Eisenträger, S. Hallgren, K.E. Lauter, T. Morrison, C. Petit, Supersingular isogeny graphs and endomorphism rings: reductions and solutions, in J.B. Nielsen, V. Rijmen, editors, Advances in Cryptology—EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29–May 3, 2018 Proceedings, Part III, volume 10822 of Lecture Notes in Computer Science (Springer, 2018), pp. 329–368

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

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

A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in A.M. Odlyzko, editor, CRYPTO, volume 263 of Lecture Notes in Computer Science (Springer, 1986), pp. 186–194

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

S.D. Galbraith, C. Petit, B. Shani, Y. Bo Ti, On the security of supersingular isogeny cryptosystems, in J.H. Cheon, T. Takagi, editors, ASIACRYPT 2016, volume 10031 of Lecture Notes in Computer Science (Springer, 2016), pp. 63–91

S. Goldfeder, M. Chase, G. Zaverucha, Efficient post-quantum zero-knowledge and signatures (draft). Cryptology ePrint Archive, Report 2016/1110 (2016). http://eprint.iacr.org/2016/1110

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

D. Jao, L. De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, in B.-Y. Yang, editor, PQCrypto 2011, volume 7071 of Lecture Notes in Computer Science (Springer, 2011), pp. 19–34

D. Jao, S.D. Miller, R. Venkatesan, Do all elliptic curves of the same order have the same difficulty of discrete log?, in B.K. Roy, editor, ASIACRYPT, volume 3788 of Lecture Notes in Computer Science (Springer, 2005), pp. 21–40

D. Jao, V. Soukharev, Isogeny-based quantum-resistant undeniable signatures, in M. Mosca, editor, PQCrypto 2014, volume 8772 of Lecture Notes in Computer Science (Springer, 2014), pp. 160–179

J. Katz, Digital Signatures. (Springer, Berlin, 2010)

J. Katz, Y. Lindell, Introduction to Modern Cryptography. (CRC Press, Boca Raton, 2014)

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

J. Kelsey, T. Kohno, Herding hash functions and the nostradamus attack, in S. Vaudenay, editor, EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science (Springer, 2006), pp. 183–200

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

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

G. Neven, N.P. Smart, B. Warinschi, Hash function requirements for schnorr signatures. J. Math. Cryptol. 3(1), 69–87 (2009)

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

C. Petit, Faster algorithms for isogeny problems using torsion point images, in T. Takagi, T. Peyrin, editors, Advances in Cryptology—ASIACRYPT 2017-23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II, volume 10625 of Lecture Notes in Computer Science (Springer, 2017), pp. 330–353

C. Petit, K.E. Lauter, Hard and easy problems for supersingular isogeny graphs. IACR Cryptology ePrint Archive 2017, 962 (2017)

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

J.H. Silverman, The Arithmetic of Elliptic Curves. (Springer, Berlin, 1986)

D. Unruh, Non-interactive zero-knowledge proofs in the quantum random oracle model, in E. Oswald, M. Fischlin, editors, EUROCRYPT 2015, volume 9057 of Lecture Notes in Computer Science (Springer, 2015), pp. 755–784

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

M.-F. Vignéras, The arithmetic of quaternion algebra (2006). http://maths.nju.edu.cn/~guoxj/notes/qa.pdf

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

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

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

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

W.C. Waterhouse, Abelian varieties over finite fields. Annales scientifiques de l’E.N.S. 2, 521–560 (1969)

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

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

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 33

130-175

Thông tin tác giả