A digital signature scheme $\mathrm{mCFS}^{\mathrm{QC{-}LDPC}}$ based on $\mathrm{QC}$-$\mathrm{LDPC}$ codes

E. D. Fiallo

Matematičeskie voprosy kriptografii, Tome 12 (2021), pp. 99-113.

Résumé

We propose to replace the Goppa codes with $\mathrm{QC}$-$\mathrm{LDPC}$ codes in the digital signature scheme $\mathrm{mCFS}_c$. With this modification, we obtain a considerable reduction ($50$ times on average) of the public key sizes without losing security. Our theoretical security model is the same as for the $\mathrm{mCFS}$ scheme. We discuss the possibility of applying some known methods to attacks on the hash function and on the public/private key setting. We also propose a set of parameters for several security levels; for example, we can get $80$ bits of security with the public key size $\approx 1.82$ KB, $128$ bits of security with $\approx 3.87$ KB, and $256$ bits of security with $\approx 13.88$ KB.

Bibliographie

[1] Shor P. W., “Algorithms for quantum computation: discrete logarithms and factoring”, Proc. 35th Annu. Symp. Found. Computer Sci., Ieee, 1994, 124–134 | DOI

[2] Chen L., Chen L., Jordan S., Liu Y., Moody D., Peralta R., Perlner R., Smith-Tone D., Report on post-quantum cryptography, No 12, US Dept of Commerce, NIST, 2016 | Zbl

[3] Alagic G., Alagic G., Alperin-Sheriff J., Apon D., Cooper D., Dang Q., Liu Y., Miller C., Moody D., Peralta R., e. a., Status report on the first round of the NIST post-quantum cryptography standardization process, US Dept of Commerce, NIST, 2019

[4] Alagic G., Alperin-Sheriff J., Apon D., Cooper D., Dang Q., Kelsey J., Liu Y., Miller C., Moody D., Peralta R., e. a., Status report on the second round of the NIST post-quantum cryptography standardization process, US Dept of Commerce, NIST, 2020

[5] Courtois N. T., Finiasz M., Sendrier N., “How to achieve a McEliece-based digital signature scheme”, ASIACRYPT 2001, Lect. Notes Comput. Sci., 2248, 2001, 157–174 | DOI | Zbl

[6] Dallot L., “Towards a concrete security proof of Courtois, Finiasz and Sendrier signature scheme”, West. Eur. Workshop Research in Cryptology, Lect. Notes Comput. Sci., 4945, 2007, 65–77 | DOI

[7] Merkle R. C., “One way hash functions and DES”, CRYPTO'89, Lect. Notes Comput. Sci., 435, 1989, 428–446 | DOI

[8] Damgård I. B., “A design principle for hash functions”, CRYPTO'89, Lect. Notes Comput. Sci., 435, 1989, 416–427

[9] Ren F., Zheng D., Wang W., e. a., “An efficient code based digital signature algorithm”, Int. J. Netw. Secur., 19:6 (2017), 1072–1079

[10] Baldi M., Barenghi A., Chiaraluce F., Pelosi G., Santini P., LEDAcrypt, Second round submiss. NIST postquant. crypt. call, 2019

[11] Gallager R., “Low-density parity-check codes”, IRE Trans. Inf. Theory, 8:1 (1962), 21–28 | DOI | Zbl

[12] Katz J., Lindell Y., Introduction to modern cryptography, 3rd, CRC press, 2020, 648 pp.

[13] Augot D., Finiasz M., Sendrier N., “A family of fast syndrome based cryptographic hash functions”, Int. Conf. Cryptology in Malaysia, Lect. Notes Comput. Sci., 3715, 2005, 64–83 | DOI | Zbl

[14] Chen C.L., Peterson W. W., Weldon Jr. E.J., “Some results on quasi-cyclic codes”, Inf. and Control, 15:5 (1969), 407–423 | DOI | Zbl

[15] Finiasz M., Gaborit P., Sendrier N., “Improved fast syndrome based cryptographic hash functions” (2007), Proc. ECRYPT Hash Workshop, 2007, 155

[16] MacWilliams F.J., Sloane N.J.A., The theory of error correcting codes, North Holland Publ. Co., Amsterdam – N.Y. – Oxford, 1977 | Zbl

[17] Gaborit P., Zemor G., “Asymptotic improvement of the Gilbert–Varshamov bound for linear codes”, IEEE Trans. Inf. Theory, 54 (2008), 3865–3872 | DOI | Zbl

[18] Wagner D., “A generalized birthday problem”, CRYPTO 2002, Lect. Notes Comput. Sci., 2442, 2002, 288–304 | DOI

[19] Zoni D., Galimberti A., Fornaciari W., “Efficient and scalable FPGA-oriented design of QC-LDPC bit-flipping decoders for post-quantum cryptography”, IEEE Access, 8 (2020), 163419–163433 | DOI

[20] Sendrier N., “Code-based cryptography: State of the art and perspectives”, IEEE Security $\$ Privacy, 15:4 (2017), 44–50 | DOI

[21] Sendrier N., “Decoding one out of many”, PQCrypto 2011, Lect. Notes Comput. Sci., 7071, 2011, 51–67 | DOI | MR | Zbl

[22] Hauteville A., Tillich J., “New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem”, Proc. IEEE Int. Symp. Inf. Theory, ISIT, IEEE, 2015, 2747–2751

[23] Saarinen M., “Linearization attacks against syndrome based hashes”, INDOCRYPT 2007, Lect. Notes Comput. Sci., 4859, 2007, 1–9 | DOI

[24] Fouque P., Leurent G., “Cryptanalysis of a hash function based on quasi-cyclic codes”, CT-RSA 2008, Lect. Notes Comput. Sci., 4964, 2008, 19–35 | DOI | MR | Zbl

[25] Baldi M., Chiaraluce F., “Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes”, IEEE Int. Symp. Inf. Theory, IEEE, 2007, 2591–2595

[26] Apon D., Perlner R., Robinson A., Santini P., “Cryptanalysis of LEDAcrypt”, CRYPTO 2020, Lect. Notes Comput. Sci., 12172, 2020, 389–418 | DOI | MR

[27] Monico C., Rosenthal J., Shokrollahi A., “Using low density parity check codes in the McEliece cryptosystem”, IEEE Int. Symp. Inf. Theory, 2000, 215, IEEE

[28] Baldi M., Chiaraluce F., Garello R., “On the usage of quasi-cyclic low-density parity-check codes in the McEliece cryptosystem”, First Int. Conf. Communic. and Electronics, IEEE, 2006, 305–310

[29] Bernstein D.J., Lange T., Peters C., “Attacking and defending the McEliece cryptosystem”, PQCrypto 2008, Lect. Notes Comput. Sci., 5299, 2008, 31–46 | DOI | Zbl