nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Cutting the GRASS: Threshold GRoup Action Signature Schemes

verfasst von : Michele Battagliola, Giacomo Borin, Alessio Meneghetti, Edoardo Persichetti

Erschienen in: Topics in Cryptology – CT-RSA 2024

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Group actions are fundamental mathematical tools, with a long history of use in cryptography. Indeed, the action of finite groups at the basis of the discrete logarithm problem is behind a very large portion of modern cryptographic systems. With the advent of post-quantum cryptography, however, other group actions, such as isogeny-based ones, received interest from the cryptographic community, attracted by the possibility of translating old discrete logarithm-based functionalities.

Usually, research focuses on abelian group actions; however in this work we show that isomorphism problems which stem from non-abelian cryptographic group actions can be viable building blocks for threshold signature schemes. In particular, we construct a full N-out-of-N threshold signature scheme, and discuss the efficiency issues arising from extending it to the generic T-out-of-N case. To give a practical outlook on our constructions, we instantiate them with two different flavors of code-based cryptographic group actions, respectively at the basis of the LESS and MEDS signature schemes, two of NIST’s candidates in the recent call for post-quantum standardization.

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 SoK: Parameterization of Fault Adversary Models Connecting Theory and Practice

Nur mit Berechtigung zugänglich

This is a generic signature scheme that is simply an abstraction, but has appeared in literature when instantiated in various works, such as LESS [8] and MEDS [29].

Unfortunately, while standard linear secret sharing would be more efficient, it is difficult to use in a non-abelian setting.

i.e. the probability of guessing the commitment is negligible.

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_28CrossRef

Aguilar Melchor, C., et al.: HQC. NIST PQC Submission (2020)

Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 411–439. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_14CrossRef

Albrecht, M.R., et al.: Classic McEliece. NIST PQC Submission (2020)

Aragon, N., et al.: BIKE. NIST PQC Submission (2020)

Baldi, M., et al.: Matrix equivalence digital signature (2023). https://www.less-project.com/LESS-2023-08-18.pdf. Accessed 15 Sept 2023

Barenghi, A., Biasse, J.-F., Ngo, T., Persichetti, E., Santini, P.: Advanced signature functionalities from the code equivalence problem. Cryptology ePrint Archive, Paper 2022/710 (2022). https://eprint.iacr.org/2022/710

Barenghi, A., Biasse, J.-F., Persichetti, E., Santini, P.: LESS-FM: fine-tuning signatures from the code equivalence problem. In: Cheon, J.H., Tillich, J.P. (eds.) PQCrypto 2021. LNCS, vol. 12841, pp. 23–43. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_2CrossRef

Barenghi, A., Biasse, J.-F., Persichetti, E., Santini, P.: On the computational hardness of the code equivalence problem in cryptography. Adv. Math. Commun. 17(1), 23–55 (2023)MathSciNetCrossRef

10.

Basso, A., et al.: Supersingular curves you can trust. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14005, pp. 405–437. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30617-4_14CrossRef

11.

Battagliola, M., Galli, A., Longo, R., Meneghetti, A.: A provably-unforgeable threshold schnorr signature with an offline recovery party. In: DLT2022 at Itasec 2022, CEUR Workshop Proceedings (2022)

12.

Battagliola, M., Longo, R., Meneghetti, A.: Extensible decentralized secret sharing and application to schnorr signatures (2022). https://eprint.iacr.org/2022/1551

13.

Battagliola, M., Longo, R., Meneghetti, A., Sala, M.: A provably-unforgeable threshold EdDSA with an offline recovery party (2020). https://arxiv.org/abs/2009.01631

14.

Battagliola, M., Longo, R., Meneghetti, A., Sala, M.: Threshold ECDSA with an offline recovery party. Mediterr. J. Math. 19(4) (2022)

15.

Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, pp. 390–399. Association for Computing Machinery, New York (2006)

16.

Beullens, W., Disson, L., Pedersen, R., Vercauteren, F.: CSI-RAShi: distributed key generation for CSIDH. In: Cheon, J.H., Tillich, J.P. (eds.) PQCrypto 2021. LNCS, vol. 12841, pp. 257–276. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_14CrossRef

17.

Beullens, W., Katsumata, S., Pintore, F.: Calamari and Falafl: logarithmic (linkable) ring signatures from isogenies and lattices. Cryptology ePrint Archive, Paper 2020/646 (2020). https://eprint.iacr.org/2020/646

18.

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

19.

Biasse, J.-F., Micheli, G., Persichetti, E., Santini, P.: Less is more: code-based signatures without syndromes. In: Nitaj, A., Youssef, A. (eds.) AFRICACRYPT 2020. LNCS, vol. 12174, pp. 45–65. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51938-4_3CrossRef

20.

Bläser, M., et al.: On digital signatures based on isomorphism problems: qrom security, ring signatures, and applications. Cryptology ePrint Archive (2022)

21.

Boneh, D., Gennaro, R., Goldfeder, S.: Using level-1 homomorphic encryption to improve threshold DSA signatures for bitcoin wallet security. In: Lange, T., Dunkelman, O. (eds.) LATINCRYPT 2017. LNCS, vol. 11368, pp. 352–377. Springer, Cham (2017). https://doi.org/10.1007/978-3-030-25283-0_19CrossRef

22.

Bonte, C., Smart, N.P., Tanguy, T.: Thresholdizing hasheddsa: MPC to the rescue. Int. J. Inf. Secur. 20, 879–894 (2021)CrossRef

23.

Brandão, L.T.A.N., Davidson, M.: Notes on threshold eddsa/schnorr signatures. Accessed 01 May 2023

24.

Brandão, L.T.A.N., Davidson, M., Vassilev, A.: NIST roadmap toward criteria for threshold schemes for cryptographic primitives. Accessed 27 Aug 2020

25.

Campos, F., Muth, P.: On actively secure fine-grained access structures from isogeny assumptions. In: Cheon, J.H., Johansson, T. (eds.) PQCrypto 2022. LNCS, vol. 13512, pp. 375–398. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-17234-2_18CrossRef

26.

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

27.

Chailloux, A.: On the (in) security of optimized stern-like signature schemes. In: WCC (2022)

28.

Chou, T., et al.: Matrix equivalence digital signature (2023). https://meds-pqc.org/spec/MEDS-2023-05-31.pdf. Accessed 12 Sept 2023

29.

Chou, T., Niederhagen, R., Persichetti, E., Randrianarisoa, T.H., Reijnders, K., Samardjiska, S., Trimoska, M.: Take your meds: digital signatures from matrix code equivalence. In: El Mrabet, N., De Feo, L., Duquesne, S. (eds.) AFRICACRYPT 2023. LNCS, vol. 14064, pp. 28–52. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-37679-5_2CrossRef

30.

Chou, T., Persichetti, E., Santini, P.: On linear equivalence, canonical forms, and digital signatures (2023). https://tungchou.github.io/papers/leq.pdf. Accessed 20 Sept 2023

31.

Cozzo, D., Smart, N.P.: Sharing the LUOV: threshold post-quantum signatures. In: Albrecht, M. (ed.) IMACC 2019. LNCS, vol. 11929, pp. 128–153. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35199-1_7CrossRef

32.

Cozzo, D., Smart, N.P.: Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 169–186. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_10CrossRef

33.

D’Alconzo, G., Scala, A.J.D.: Representations of group actions and their applications in cryptography. Cryptology ePrint Archive, Paper 2023/1247 (2023)

34.

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

35.

De Feo, L., Meyer, M.: Threshold schemes from isogeny assumptions. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 187–212. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_7CrossRef

36.

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)

37.

Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Threshold ECDSA from ECDSA assumptions: the multiparty case. In: 2019 IEEE Symposium on Security and Privacy (SP), pp. 1051–1066. IEEE (2019)

38.

Don, J., Fehr, S., Majenz, C., Schaffner, C.: Security of the Fiat-Shamir transformation in the quantum random-oracle model. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_13CrossRef

39.

Feneuil, T., Joux, A., Rivain, M.: Syndrome decoding in the head: shorter signatures from zero-knowledge proofs. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 541–572. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_19CrossRef

40.

Feneuil, T., Joux, A., Rivain, M.: Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature. Des. Codes Crypt. 91(2), 563–608 (2023)MathSciNetCrossRef

41.

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. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

42.

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 (2018)

43.

Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. In: Manulis, M., Sadeghi, A.R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 156–174. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_9CrossRef

44.

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

45.

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. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_21CrossRef

46.

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. J. Cryptol. 20, 51–83 (2007)MathSciNetCrossRef

47.

Grilo, A.B., Hövelmanns, K., Hülsing, A., Majenz, C.: Tight adaptive reprogramming in the QROM. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_22CrossRef

48.

Gueron, S., Persichetti, E., Santini, P.: Designing a practical code-based signature scheme from zero-knowledge proofs with trusted setup. Cryptography 6(1), 5 (2022)CrossRef

49.

Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electron. Commun. Japan 72(9), 56–64 (1989)MathSciNetCrossRef

50.

Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Severini, S., Brandão, F.G.S.L. (eds.) TQC 2013. LIPIcs, vol. 22. Schloss Dagstuhl (2013)

51.

Lindell, Y.: Fast secure two-party ECDSA signing. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_21CrossRef

52.

Liu, Q., Zhandry, M.: Revisiting post-quantum Fiat-Shamir. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 326–355. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_12CrossRef

53.

MacKenzie, P., Reiter, M.K.: Two-party generation of DSA signatures. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 137–154. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_8CrossRef

54.

MacKenzie, P., Reiter, M.K.: Two-party generation of DSA signatures. Int. J. Inf. Secur. (2004)

55.

NIST. Post-Quantum Cryptography Standardization (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

56.

NIST. Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process (2023). https://csrc.nist.gov/projects/pqc-dig-sig/standardization/call-for-proposals

57.

Persichetti, E., Santini, P.: A new formulation of the linear equivalence problem and shorter less signatures. Cryptology ePrint Archive (2023)

58.

Schwabe, P., et al.: CRYSTALS-KYBER. NIST PQC Submission (2020)

59.

Unruh, D.: Post-quantum security of Fiat-Shamir. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 65–95. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_3CrossRef

Titel: Cutting the GRASS: Threshold GRoup Action Signature Schemes
verfasst von: Michele Battagliola
Giacomo Borin
Alessio Meneghetti
Edoardo Persichetti
Verlag: Springer Nature Switzerland
Buch: Topics in Cryptology – CT-RSA 2024
Print ISBN: 978-3-031-58867-9

Electronic ISBN: 978-3-031-58868-6

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58868-6_18

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"

Premium Partner