Take Your MEDS: Digital Signatures from Matrix Code Equivalence | SpringerLink
Skip to main content
Springer Nature Link
Log in

Take Your MEDS: Digital Signatures from Matrix Code Equivalence

  • Conference paper
  • First Online:
Progress in Cryptology - AFRICACRYPT 2023 (AFRICACRYPT 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14064))

Included in the following conference series:

Abstract

In this paper, we show how to use the Matrix Code Equivalence (MCE) problem as a new basis to construct signature schemes. This extends previous work on using isomorphism problems for signature schemes, a trend that has recently emerged in post-quantum cryptography. Our new formulation leverages a more general problem and allows for smaller data sizes, achieving competitive performance and great flexibility. Using MCE, we construct a zero-knowledge protocol which we turn into a signature scheme named Matrix Equivalence Digital Signature (MEDS). We provide an initial choice of parameters for MEDS, tailored to NIST’s Category 1 security level, yielding public keys as small as 2.8 kB and signatures ranging from 18 kB to just around 6.5 kB, along with a reference implementation in C.

An extended and correctly typeset version of this paper can be found at https://eprint.iacr.org/2022/1559.

Tung Chou is supported by Taiwan National Science and Technology Council (NSTC, previously Ministry of Science and Technology) grant 109-2222-E-001-001-MY3. Edoardo Persichetti is supported by NSF grant 1906360 and NSA grant H98230-22-1-0328. Monika Trimoska is supported by the ERC Starting Grant 805031 (EPOQUE).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 10295
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 12869
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    https://eprint.iacr.org/2022/1559.pdf.

  2. 2.

    More accurately, as the action of an isometry (A, B) is only interesting up to scalars \(\lambda , \mu \in \mathbb {F}_q\), the group that is acting freely is \({\text {PGL}}_m(q) \times {\text {PGL}}_n(q)\).

  3. 3.

    Again, for convenience, we choose \(\textbf{A}_{0}=\textbf{I}_m\), \(\textbf{B}_{0}=\textbf{I}_n\).

  4. 4.

    https://bench.cr.yp.to/results-sign.html – amd64; Zen (800f11); 2017 AMD Ryzen 7 1700; 8 \(\times \) 3000 MHz; rumba7, supercop-20220506.

References

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

    Google Scholar 

  2. Aguilar-Melchor, C., Gama, N., Howe, J., Hülsing, A., Joseph, D., Yue, D.: The return of the SDitH. Cryptology ePrint Archive, Paper 2022/1645 (2022, to appear at Eurocrypt 2023)

    Google Scholar 

  3. 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_14

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  6. Banegas, G., Debris-Alazard, T., Nedeljković, M., Smith, B.: Wavelet: code-based postquantum signatures with fast verification on microcontrollers. Cryptology ePrint Archive, Paper 2021/1432 (2021)

    Google Scholar 

  7. Bardet, M., et al.: Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 507–536. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_17

    Chapter  Google Scholar 

  8. 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 2021. LNCS, vol. 12841, pp. 23–43. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_2

    Chapter  MATH  Google Scholar 

  9. Barenghi, A., Biasse, J.-F., Ngo, T., Persichetti, E., Santini, P.: Advanced signature functionalities from the code equivalence problem. Int. J. Comput. Math. Comput. Syst. Theory 7(2), 112–128 (2022)

    Article  MathSciNet  Google Scholar 

  10. Beullens, W.: Not enough LESS: an improved algorithm for solving code equivalence problems over \(\mathbb{F}_q\). In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C. (eds.) SAC 2020. LNCS, vol. 12804, pp. 387–403. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81652-0_15

    Chapter  Google Scholar 

  11. Beullens, W., et al.: Oil and vinegar: modern parameters and implementations. Cryptology ePrint Archive, Paper 2023/059 (2023)

    Google Scholar 

  12. Beullens, W., Katsumata, S., Pintore, F.: Calamari and Falafl: logarithmic (linkable) ring signatures from isogenies and lattices. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 464–492. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_16

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  14. 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_3

    Chapter  Google Scholar 

  15. Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 493–522. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_17

    Chapter  Google Scholar 

  16. Bouillaguet, C.: Algorithms for some hard problems and cryptographic attacks against specific cryptographic primitives. Ph.D. thesis, Université Paris Diderot (2011)

    Google Scholar 

  17. Bouillaguet, C., Fouque, P.-A., Véber, A.: Graph-theoretic algorithms for the “isomorphism of polynomials’’ problem. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 211–227. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_13

    Chapter  Google Scholar 

  18. 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_15

    Chapter  Google Scholar 

  19. Courtois, N.T.: Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 402–421. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_24

    Chapter  Google Scholar 

  20. Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_27

    Chapter  Google Scholar 

  21. Couveignes, J.-M.: Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291 (2006)

    Google Scholar 

  22. Couvreur, A., Debris-Alazard, T., Gaborit, P.: On the hardness of code equivalence problems in rank metric. CoRR, abs/2011.04611 (2020)

    Google Scholar 

  23. 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_26

    Chapter  Google Scholar 

  24. Ding, J., et al.: Rainbow. Technical report, National Institute of Standards and Technology (2020)

    Google Scholar 

  25. Faugère, J.-C., Din, M.S.E., Spaenlehauer, P.-J.: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): algorithms and complexity. J. Symb. Comput. 46(4), 406–437 (2011)

    Article  MATH  Google Scholar 

  26. Faugère, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of MinRank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16

    Chapter  Google Scholar 

  27. Faugère, J.-C., Perret, L.: Polynomial equivalence problems: algorithmic and theoretical aspects. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 30–47. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_3

    Chapter  Google Scholar 

  28. 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

    Chapter  Google Scholar 

  29. 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)

    Article  Google Scholar 

  30. Haviv, I., Regev, O.: On the lattice isomorphism problem. In: Chekuri, C. (ed.) SODA 2014, pp. 391–404. ACM SIAM (2014)

    Google Scholar 

  31. Hulsing, A., et al.: SPHINCS+. NIST PQC Submission (2020)

    Google Scholar 

  32. Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_2

    Chapter  Google Scholar 

  33. 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, pp. 20–34. Schloss Dagstuhl (2013)

    Google Scholar 

  34. Leon, J.S.: Computing automorphism groups of error-correcting codes. IEEE Trans. Inf. Theory 28(3), 496–510 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  35. Lyubashevsky, V., et al.: CRYSTALS. NIST PQC Submission (2020)

    Google Scholar 

  36. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN PR 42-44, California Institute of Technology (1978)

    Google Scholar 

  37. Nguyen, P., Wolf, C.: International workshop on post-quantum cryptography (2006)

    Google Scholar 

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

  39. Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_4

    Chapter  Google Scholar 

  40. Perlner, R., Smith-Tone, D.: Rainbow band separation is better than we thought. Cryptology ePrint Archive, Paper 2020/702 (2020)

    Google Scholar 

  41. Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962)

    Article  MathSciNet  Google Scholar 

  42. Prest, T., et al.: FALCON. NIST PQC Submission (2020)

    Google Scholar 

  43. Randall, D.: Efficient Generation of Random Nonsingular Matrices. Technical Report UCB/CSD-91-658, EECS Department, UC Berkeley (1991)

    Google Scholar 

  44. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Theory of Computing, pp. 84–93. ACM (2005)

    Google Scholar 

  45. Reijnders, K., Samardjiska, S., Trimoska, M.: Hardness estimates of the code equivalence problem in the rank metric. Cryptology ePrint Archive, Paper 2022/276 (2022)

    Google Scholar 

  46. Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Paper 2006/145 (2006)

    Google Scholar 

  47. Tang, G., Duong, D.H., Joux, A., Plantard, T., Qiao, Y., Susilo, W.: Practical post-quantum signature schemes from isomorphism problems of trilinear forms. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13277, pp. 582–612. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_21

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Academia Sinica, Taipei, Taiwan

    Tung Chou & Ruben Niederhagen

  2. University of Southern Denmark, Odense, Denmark

    Ruben Niederhagen

  3. Florida Atlantic University, Boca Raton, USA

    Edoardo Persichetti

  4. Sapienza University, Rome, Italy

    Edoardo Persichetti

  5. Umea University, Umea, Sweden

    Tovohery Hajatiana Randrianarisoa

  6. Radboud Universiteit, Nijmegen, The Netherlands

    Krijn Reijnders, Simona Samardjiska & Monika Trimoska

Authors
  1. Tung Chou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ruben Niederhagen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Edoardo Persichetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tovohery Hajatiana Randrianarisoa
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Krijn Reijnders
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Simona Samardjiska
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Monika Trimoska
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Tung Chou , Ruben Niederhagen , Edoardo Persichetti , Tovohery Hajatiana Randrianarisoa , Krijn Reijnders , Simona Samardjiska or Monika Trimoska .

Editor information

Editors and Affiliations

  1. EMSE, Saint-Étienne, France

    Nadia El Mrabet

  2. IBM Research Europe, Rüschlikon, Switzerland

    Luca De Feo

  3. Université de Rennes 1, Rennes Cedex, France

    Sylvain Duquesne

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chou, T. et al. (2023). Take Your MEDS: Digital Signatures from Matrix Code Equivalence. In: El Mrabet, N., De Feo, L., Duquesne, S. (eds) Progress in Cryptology - AFRICACRYPT 2023. AFRICACRYPT 2023. Lecture Notes in Computer Science, vol 14064. Springer, Cham. https://doi.org/10.1007/978-3-031-37679-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-37679-5_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-37678-8

  • Online ISBN: 978-3-031-37679-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation