Reproducible families of codes and cryptographic applications. (English) Zbl 1476.94043

Summary: Structured linear block codes such as cyclic, quasi-cyclic and quasi-dyadic codes have gained an increasing role in recent years both in the context of error control and in that of code-based cryptography. Some well known families of structured linear block codes have been separately and intensively studied, without searching for possible bridges between them. In this article, we start from well known examples of this type and generalize them into a wider class of codes that we call \(\mathcal{F} \)-reproducible codes. Some families of \(\mathcal{F} \)-reproducible codes have the property that they can be entirely generated from a small number of signature vectors, and consequently admit matrices that can be described in a very compact way. We denote these codes as compactly reproducible codes and show that they encompass known families of compactly describable codes such as quasi-cyclic and quasi-dyadic codes. We then consider some cryptographic applications of codes of this type and show that their use can be advantageous for hindering some current attacks against cryptosystems relying on structured codes. This suggests that the general framework we introduce may enable future developments of code-based cryptography.


94B05 Linear codes (general theory)
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)


CAKE; McEliece; BIKE; LEDAkem
Full Text: DOI


[1] Misoczki R, Barreto PSLM. Compact McEliece keys from Goppa codes. In: Selected Areas in Cryptography, Lecture Notes in Computer Science 5867. Springer Verlag; 2009. p. 376-92. · Zbl 1267.94086
[2] McEliece RJ. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report. 1978;4244:114-6.
[3] Gaborit P. Shorter keys for code based cryptography. In: Proceedings of the International Workshop on Coding and Cryptography (WCC 2005). Bergen, Norway; March 2005. p. 81-90.
[4] Monico C, Rosenthal J, Shokrollahi A. Using low density parity check codes in the McEliece cryptosystem. In: Proceedingsof the IEEE International Symposium on Information Theory (ISIT 2000) Sorrento, Italy; June 2000. p. 215.
[5] Misoczki R, Tillich JP, Sendrier N, Barreto PSLM. MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In: 2013 IEEE International Symposium on Information Theory; July 2013. p. 2069-73.
[6] Baldi M. LDPC codes in the McEliece cryptosystem: attacks and countermeasures. NATO Science for Peace and Security Series - D: Information and Communication Security 23. IOS Press; 2009. p. 160-74.
[7] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput. 1997;26:1484-509. · Zbl 1005.11065
[8] https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.
[9] Bootland C, Castryck W, Szepieniec A, Vercauteren F. A framework for cryptographic problems from linear algebra. J Math Cryptol. 2019;14:202-17.
[10] Alagic C, Alperin-Sheriff J, Apon D, Cooper D, Dang Q, Liu YK, et al. Status report on the first round of the NIST post-quantum cryptography standardization process. Washington, DC: US Department of Commerce, National Institute of Standards and Technology; 2019.
[11] Berlekamp E, McEliece R, van Tilborg H. On the inherent intractability of certain coding problems. IEEE Trans Inform Theory 1978;24:384-86. · Zbl 0377.94018
[12] Sidelnikov VM, Shestakov SO. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discr Math Appl. 1992;2:439-44. · Zbl 0796.94006
[13] Faugère J-C, Otmani A, Perret L, Tillich J-P. A distinguisher for high rate McEliece cryptosystems. In: Proceedings of IEEE Information Theory Workshop (ITW). Paraty, Brazil; October 2011. p. 282-6.
[14] Gallager RG. Low-density parity-check codes. IRE Transactions on Information Theory. IEEE; 1963;8(1).
[15] Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation. In:Kalai Y, Reyzin L, editors. Theory of Cryptography. Cham: Springer International Publishing; 2017. p. 341-71. · Zbl 1410.94082
[16] Baldi M, Barenghi A, Chiaraluce F, Pelosi G, Santini P. Failure rate model of bit-flipping decoders for QC-LDPC and QC-MDPC code-based cryptosystems. In: Proceedings of the 17th International Joint Conference on e-Business and Telecommunications - Volume 3: SECRYPT, INSTICC. SciTePress; 2020. p. 238-49.
[17] Prange E. The use of information sets in decoding cyclic codes. IRE Trans Inform Theory. 1962;8:5-9.
[18] Leon JS. A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans Inform Theory. 1988;34:1354-9.
[19] Stern J. A method for finding codewords of small weight. In: Coding Theory and Applications. Cohen G, Wolfmann J, editors. Lecture Notes in Computer Science 388. Springer Verlag; 1989. p. 106-13.
[20] May A, Meurer A, Thomae E. Decoding random linear codes in O(20.054n). ASIACRYPT, LNCS 7073. Springer; 2011. p. 107-24. · Zbl 1227.94055
[21] Becker A, Joux A, May A, Meurer A. Decoding random binary linear codes in 2n∕20: How 1+1=0 improves information set decoding. In: Pointcheval D, Johansson T, editors. Advances in Cryptology - EUROCRYPT 2012, Lecture Notes in Computer Science 7237. Springer Verlag; 2012. p. 520-36. · Zbl 1291.94206
[22] Grover LK. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. Philadephia, PA; May 1996. p. 212-9.
[23] Bernstein DJ. Grover vs. McEliece. In: PQCrypto. 2010. · Zbl 1284.94053
[24] Baldi M, Bodrato M, Chiaraluce F. A new analysis of the McEliece Cryptosystem based on QC-LDPC codes. In: Security and Cryptography for Networks, Lecture Notes in Computer Science 5229. Springer Verlag; 2008. p. 246-62. · Zbl 1180.94046
[25] Berger TP, Cayrel P-L, Gaborit P, Otmani A. Reducing key length of the McEliece cryptosystem. In: Progress in Cryptology - AFRICACRYPT 2009, Lecture Notes in Computer Science 5580. Springer Verlag; 2009. p. 77-97. · Zbl 1246.94022
[26] Faugère J-C, Otmani A, Perret L, Tillich J-P. Algebraic cryptanalysis of McEliece variants with compact keys. In: EUROCRYPT 2010, Lecture Notes in Computer Science 6110. Springer Verlag; 2010. p. 279-98. · Zbl 1280.94051
[27] https://bigquake.inria.fr/.
[28] Sendrier N. Decoding one out of many. In: Post-quantum cryptography. Yang BY, editor. Lecture Notes in Computer Science 7071. Springer Verlag; 2011. p. 51-67. · Zbl 1290.94167
[29] Guo Q, Johansson T, Stankovski P. A key recovery attack on MDPC with CCA security using decoding errors. In: ASIACRYPT, LNCS 10031. Springer; 2016. p. 789-815. · Zbl 1404.94079
[30] Baldi M, Barenghi A, Chiaraluce F, Pelosi G, Santini P. LEDAkem: A Post-quantum Key Encapsulation Mechanism Based on QC-LDPC Codes. In: 9th International Conference on Post-Quantum Cryptography. Fort Lauderdale, FL, USA: PQCrypto; April 9-11 2018. p. 3-24. · Zbl 1425.94046
[31] Barreto PSLM, Gueron S, Gueneysu T, Misoczki R, Persichetti E, Sendrier N, et al. CAKE: code-based algorithm for key encapsulation. In: IMA International Conference on Cryptography and Coding. Springer; 2017. p. 207-26. · Zbl 1397.94047
[32] Tillich J-P. The decoding failure probability of MDPC codes. In:2018 IEEE International Symposium on Information Theory (ISIT), IEEE; 2018. p. 941-5.
[33] Santini P, Battaglioni M, Baldi M, Chiaraluce F. Analysis of the error correction capability of LDPC and MDPC codes under parallel bit-flipping decoding and application to cryptography. IEEE Trans Commun. 2020;68:4648-60.
[34] Santini P, Baldi M, Cancellieri G, Chiaraluce F. Hindering reaction attacks by using monomial codes in the McEliece cryptosystem. In:2018 IEEE International Symposium on Information Theory (ISIT), IEEE; 2018. p. 951-5.
[35] Baldi M, Bianchi M, Chiaraluce F. Optimization of the parity-check matrix density in QC-LDPC code-based McEliece cryptosystems. In: Proc. IEEE ICC 2013 - Workshop on Information Security over Noisy and Lossy Communication Systems. Budapest, Hungary; June 2013.
[36] Householder AS. Unitary triangularization of a nonsymmetric matrix. J ACM. 1958;5:339-42. · Zbl 0121.33802
[37] Aragon N, Barreto PSLM, Bettaieb S, Bidoux L, Blazy O, Deneuville Jc. BIKE: Bit flipping key encapsulation; 2017.
[38] Fabšič T, Hromada V, Stankovski P, Zajac P, Guo Q, Johansson T. A reaction attack on the QC-LDPC McEliece cryptosystem. In:Post-Quantum Cryptography, LNCS 10346. Cham: Springer; 2017. p. 51-68. · Zbl 1437.94061
[39] Fabsic T, Hromada V, Zajac P. A reaction attack on LEDApkc. IACR Cryptol ePrint Archive. 2018;2018:140.
[40] Eaton E, Lequesne M, Parent A, Sendrier N. QC-MDPC: A timing attack and a CCA2 KEM. In: PQCrypto. Cham: Springer; 2018. p. 47-76. · Zbl 1425.94055
[41] CantoTorres R, Sendrier N. Analysis of information set decoding for a sub-linear error weight. Cham: Springer International Publishing; 2016. p. 144-61.
[42] Melchor CA, Aragon N, Bettaieb S, Bidoux L, Blazy O, Deneuville Jc, et al. HQC: Hamming Quasi Cyclic. 2017.
[43] Aguilar C, Gaborit P, Schrek J. A new zero-knowledge code based identification scheme with reduced communication. In:2011 IEEE Information Theory Workshop (ITW). Paraty, Brazil; Oct 2011. p. 648-52.
[44] Persichetti E. Compact McEliece keys based on quasi-dyadic Srivastava codes. J Math Cryptol 2012;6:149-69. · Zbl 1277.94037
[45] Banegas G, Barreto PSLM, Boidje BO, Cayrel P-L, Dione K, Gaj GN, et al. DAGS: Key encapsulation using dyadic GS codes. J Math Cryptol. 2018;12:221-39. · Zbl 1420.94102
[46] Banegas G, Barreto PSLM, Boidje BO, Cayrel P-L, Dione K, Gaj GN, et al. Dags: Reloaded revisiting dyadic key encapsulation. In: Code-Based Cryptography Workshop. Springer; 2019. p. 69-85.
[47] Barelli E, Couvreur A. An efficient structural attack on NIST submission DAGS. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer; 2018. p. 93-118. · Zbl 1446.94098
[48] Banegas G, Barreto PSLM, Persichetti E, Santini P. Designing efficient dyadic operations for cryptographic applications. J Math Cryptol. 2020;14:95-109. · Zbl 1441.94069
[49] Battaglioni M, Chiaraluce F, Baldi M, Lentmaier M. Girth analysis and design of periodically time-varying SC-LDPC codes. IEEE Trans Inform Theor. 2021;67(4):2217-35. · Zbl 1473.94037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.