Top

Published in:

2020 | OriginalPaper | Chapter

Threshold Schemes from Isogeny Assumptions

Authors : Luca De Feo, Michael Meyer

Published in: Public-Key Cryptography – PKC 2020

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We initiate the study of threshold schemes based on the Hard Homogeneous Spaces (HHS) framework of Couveignes. Quantum-resistant HHS based on supersingular isogeny graphs have recently become usable thanks to the record class group precomputation performed for the signature scheme CSI-FiSh.

Using the HHS equivalent of the technique of Shamir’s secret sharing in the exponents, we adapt isogeny based schemes to the threshold setting. In particular we present threshold versions of the CSIDH public key encryption, and the CSI-FiSh signature schemes.

The main highlight is a threshold version of CSI-FiSh which runs almost as fast as the original scheme, for message sizes as low as 1880 B, public key sizes as low as 128 B, and thresholds up to 56; other speed-size-threshold compromises are possible.

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 Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512

next chapter Topology-Hiding Computation for Networks with Unknown Delays

The reader will excuse our extravagant font choices for set and group elements: our goal is to be consistent with the notation used in Sect. 4 for isogeny-based HHS.

Note that this action is only transitive if \(\mathfrak {g}\) generates \(\mathcal {G}\).

In this context, an order is a \(\mathbb {Z}\)-module isomorphic to \(\mathbb {Z}\oplus \omega \mathbb {Z}\simeq \mathbb {Z}[\omega ]\) for some \(\omega \notin \mathbb {Q}\).

Jao, Miller and Venkatesan [37] showed that it is indeed possible to bound the norms by \(O(\log ^2(p))\), assuming the Generalized Riemann Hypothesis.

This guarantee is only heuristic: it is possible, although unlikely, that all \(\mathfrak {l}_i\) have small order in \(\mathrm {cl}(\mathbb {Z}[\pi ])\), and thus generate a small subgroup.

NIST defines the security of level 1 as being equivalent to AES-128.

Using a quantum computer, the relation lattice can be computed in polynomial time, however lattice reduction still requires exponential time.

An alternative way to allow up to 36 participants is to use the action of \(\mathrm {cl}(\mathbb {Z}[(\pi +1)/2])\) on the horizontal isogeny class of \(y^2=x^3-x\): the class group is 3 times smaller than \(\mathrm {cl}(\mathbb {Z}[\pi ])\), and still generated by \(\langle 3,\pi -1\rangle \). Because the two class group actions are compatible, the CSI-FiSh data can easily be repurposed for this variant without additional computations. This approach is detailed in [10].

Benchmarks in [4] are based on the original CSIDH implementation [11]. A speed-up of roughly 30% is to be expected using the techniques in [42].

In reality, it is well known that the size of the search space can also be reduced by 3 in the original CSIDH, by walking to the surface. Thus, the only reduction in security comes from the factor of 37.

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986)MathSciNetCrossRef

Benaloh, J.C.: Secret sharing homomorphisms: keeping shares of a secret secret (extended abstract). In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 251–260. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_19CrossRef

Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 409–441. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_15CrossRef

Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019, pp. 227–247. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_9CrossRef

Beullens, W., Preneel, B., Szepieniec, A., Vercauteren, F.: LUOV. Round 2 submission, NIST Post-Quantum Cryptography Standardization (2019). https://www.esat.kuleuven.be/cosic/pqcrypto/luov/

Biasse, J.-F., Iezzi, A., Jacobson, M.J.: A note on the security of CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 153–168. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_9CrossRef

Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the National Computer Conference, vol. 48 (1979)

Bonnetain, X., Schrottenloher, A.: Submerging CSIDH. Cryptology ePrint Archive, Report 2018/537 (2018). https://eprint.iacr.org/2018/537

Brandão, L.T.A.N., Mouha, N., Vassilev, A.: Threshold schemes for cryptographic primitives: challenges and opportunities in standardization and validation of threshold cryptography. NISTIR 8214 (2018). https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8214.pdf

10.

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

11.

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

12.

Castryck, W., Panny, L., Vercauteren, F.: Rational isogenies from irrational endomorphisms. In: Eurocrypt 2020 (2020, to appear). https://eprint.iacr.org/2019/1202

13.

Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.J., De Feo, L., Rodríguez-Henríquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. To appear at LATINCRYPT 2019 (2019). https://eprint.iacr.org/2019/837

14.

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

15.

Cozzo, D., Smart, N.P.: Sharing the LUOV: threshold post-quantum signatures. In: Second PQC Standardization Conference (2019). https://csrc.nist.gov/CSRC/media/Events/Second-PQC-Standardization-Conference/documents/accepted-papers/cozzo-luov-paper.pdf

16.

De Feo, L.: Mathematics of isogeny based cryptography (2017). http://arxiv.org/abs/1711.04062

17.

De Feo, L., Galbraith, S.D.: SeaSign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 759–789. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_26CrossRef

18.

De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 365–394. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_14CrossRef

19.

Decru, T., Panny, L., Vercauteren, F.: Faster seasign signatures through improved rejection sampling. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 271–285. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_15CrossRef

20.

Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_p\). Des. Codes Crypt. 78(2), 425–440 (2016). https://doi.org/10.1007/s10623-014-0010-1MathSciNetCrossRefMATH

21.

Desmedt, Y.: Threshold cryptosystems. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 1–14. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_47CrossRef

22.

Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_37CrossRef

23.

Ding, J., Chen, M.S., Petzoldt, A., Schmidt, D., Yang, B.Y.: Rainbow. Round 2 submission, NIST Post-Quantum Cryptography Standardization (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions

24.

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Secure two-party threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 980–997. IEEE (2018)

25.

Doulgerakis, E., Laarhoven, T., de Weger, B.: Finding closest lattice vectors using approximate Voronoi cells. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 3–22. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_1CrossRef

26.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRef

27.

Elkies, N.D.: Elliptic and modular curves over finite fields and related computational issues. In: 1995 Computational Perspectives on Number Theory. Studies in Advanced Mathematics, Chicago, IL, vol. 7, pp. 21–76. AMS International Press, Providence (1998)

28.

Felderhoff, J.: Hard homogenous spaces and commutative super singular isogeny based Diffie-Hellman. Internship report, Inria, France, August 2019. https://hal.archives-ouvertes.fr/hal-02373179

29.

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_12CrossRef

30.

Fouque, P.-A., Stern, J.: One round threshold discrete-log key generation without private channels. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 300–316. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_22CrossRefMATH

31.

Gennaro, R., Goldfeder, S.: Fast multiparty threshold ECDSA with fast trustless setup. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1179–1194. ACM (2018)

32.

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold DSS signatures. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 354–371. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_31CrossRef

33.

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_21CrossRef

34.

Harn, L.: Group-oriented (t, n) threshold digital signature scheme and digital multisignature. IEEE Proc.-Comput. Digit. Tech. 141(5), 307–313 (1994)CrossRef

35.

Jao, D., et al.: SIKE. Round 2 submission, NIST Post-Quantum Cryptography Standardization (2019). https://sike.org/

36.

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

37.

Jao, D., Miller, S.D., Venkatesan, R.: Expander graphs based on GRH with an application to elliptic curve cryptography. J. Number Theory 129(6), 1491–1504 (2009). https://doi.org/10.1016/j.jnt.2008.11.006MathSciNetCrossRefMATH

38.

Kiltz, E.: A tool box of cryptographic functions related to the Diffie-Hellman function. In: Rangan, C.P., Ding, C. (eds.) INDOCRYPT 2001. LNCS, vol. 2247, pp. 339–349. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45311-3_32CrossRef

39.

Kuperberg, G.: Another sub exponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC. LIPIcs, vol. 22, pp. 22–34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

40.

Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005)MathSciNetCrossRef

41.

Meyer, M., Campos, F., Reith, S.: On Lions and Elligators: an efficient constant-time implementation of CSIDH. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 307–325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_17CrossRef

42.

Meyer, M., Reith, S.: A faster way to the CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 137–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_8CrossRef

43.

National Institute of Standards and Technology (NIST): Post-Quantum Cryptography Standardization (2016). https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Cryptography-Standardization

44.

Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: (Short paper) a faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds.) IWSEC 2019. LNCS, vol. 11689, pp. 23–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26834-3_2CrossRef

45.

Pedersen, T.P.: A threshold cryptosystem without a trusted party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_47CrossRef

46.

Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9CrossRef

47.

Peikert, C.: He gives C-Sieves on the CSIDH. In: Eurocrypt 2020 (2020, to appear). https://eprint.iacr.org/2019/725

48.

Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv preprint quant-ph/0406151 (2004). https://arxiv.org/abs/quant-ph/0406151

49.

Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). http://eprint.iacr.org/2006/145

50.

Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22CrossRef

51.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRef

52.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)MathSciNetCrossRef

53.

Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207–220. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_15CrossRef

54.

Stinson, D.R., Strobl, R.: Provably secure distributed Schnorr signatures and a (t, n) threshold scheme for implicit certificates. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 417–434. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-47719-5_33CrossRefMATH

55.

Stolbunov, A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215–235 (2010)MathSciNetCrossRef

56.

Stolbunov, A.: Cryptographic schemes based on isogenies. Doctoral thesis, NTNU (2012)

57.

Vélu, J.: Isogénies entre courbes elliptiques. C.R. Acad. Sc. Paris, Série A. 271, 238–241 (1971)

Title: Threshold Schemes from Isogeny Assumptions
Authors: Luca De Feo
Michael Meyer
Publisher: Springer International Publishing
Book: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_7

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