Theoretical analysis of decoding failure rate of non-binary QC-MDPC codes. (English) Zbl 07860285
Esser, Andre (ed.) et al., Code-based cryptography. 11th international workshop, CBCrypto 2023, Lyon, France, April 22–23, 2023. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 14311, 35-55 (2023).
Summary: In this paper, we study the decoding failure rate (DFR) of non-binary QC-MDPC codes using theoretical tools, extending the results of previous binary QC-MDPC code studies. The theoretical estimates of the DFR are particularly significant for cryptographic applications of QC-MDPC codes. Specifically, in the binary case, it is established that exploiting decoding failures makes it possible to recover the secret key of a QC-MDPC cryptosystem. This implies that to attain the desired security level against adversaries in the CCA2 model, the decoding failure rate must be strictly upper-bounded to be negligibly small. In this paper, we observe that this attack can also be extended to the non-binary case as well, which underscores the importance of DFR estimation. Consequently, we study the guaranteed error-correction capability of non-binary QC-MDPC codes under one-step majority logic (OSML) decoder and provide a theoretical analysis of the 1-iteration parallel symbol flipping decoder and its combination with OSML decoder. Utilizing these results, we estimate the potential public-key sizes for QC-MDPC cryptosystems over \(\mathbb{F}_4\) for various security levels. We find that there is no advantage in reducing key sizes when compared to the binary case.
For the entire collection see [Zbl 1539.94001].
For the entire collection see [Zbl 1539.94001].
References:
| [1] | Alagic, G., et al.: Status report on the third round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST (2022). doi:10.6028/NIST.IR.8413 |
| [2] | Apon, D.; Perlner, R.; Robinson, A.; Santini, P.; Micciancio, D.; Ristenpart, T., Cryptanalysis of LEDAcrypt, Advances in Cryptology - CRYPTO 2020, 389-418, 2020, Cham: Springer, Cham · Zbl 1504.94093 · doi:10.1007/978-3-030-56877-1_14 |
| [3] | Aragon, N., et al.: Bike: bit flipping key encapsulation. bikesuite.org |
| [4] | Arpin, S.; Billingsley, TR; Hast, DR; Lau, JB; Perlner, R.; Robinson, A.; Cheon, JH; Johansson, T., A study of error floor behavior in QC-MDPC codes, Post-Quantum Cryptography, 89-103, 2022, Cham: Springer, Cham · Zbl 1521.94123 · doi:10.1007/978-3-031-17234-2_5 |
| [5] | Baldi, M.; Barenghi, A.; Chiaraluce, F.; Pelosi, G.; Santini, P.; Obaidat, MS; Ben-Othman, J., Analysis of in-place randomized bit-flipping decoders for the design of LDPC and MDPC code-based cryptosystems, E-Business and Telecommunications, 151-174, 2021, Cham: Springer, Cham · doi:10.1007/978-3-030-90428-9_7 |
| [6] | Baldi, M.; Barenghi, A.; Chiaraluce, F.; Pelosi, G.; Santini, P.; Wachter-Zeh, A.; Bartz, H.; Liva, G., Performance bounds for QC-MDPC codes decoders, Code-Based Cryptography, 95-122, 2022, Cham: Springer International Publishing, Cham · Zbl 1425.94046 · doi:10.1007/978-3-030-98365-9_6 |
| [7] | Baldi, M.; Bianchi, M.; Chiaraluce, F.; Rosenthal, J.; Schipani, D., Enhanced public key security for the McEliece cryptosystem, J. Cryptol., 29, 1, 1-27, 2014 · Zbl 1351.94024 · doi:10.1007/s00145-014-9187-8 |
| [8] | Baldi, M.; Bodrato, M.; Chiaraluce, F.; Ostrovsky, R.; De Prisco, R.; Visconti, I., A new analysis of the McEliece cryptosystem based on QC-LDPC codes, Security and Cryptography for Networks, 246-262, 2008, Heidelberg: Springer, Heidelberg · Zbl 1180.94046 · doi:10.1007/978-3-540-85855-3_17 |
| [9] | Baldi, M., Cancellieri, G., Chiaraluce, F., Persichetti, E., Santini, P.: Using non-binary LDPC and MDPC codes in the McEliece cryptosystem. In: 2019 AEIT International Annual Conference (AEIT), pp. 1-6. IEEE (2019) |
| [10] | Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. In: 2007 IEEE International Symposium on Information Theory, pp. 2591-2595. IEEE (2007) |
| [11] | Baldi, M., Chiaraluce, F., Garello, R., Mininni, F.: Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem. In: 2007 IEEE International Conference on Communications, pp. 951-956. IEEE (2007) |
| [12] | Berger, TP; Cayrel, P-L; Gaborit, P.; Otmani, A.; Preneel, B., Reducing key length of the McEliece cryptosystem, Progress in Cryptology - AFRICACRYPT 2009, 77-97, 2009, Heidelberg: Springer, Heidelberg · Zbl 1246.94022 · doi:10.1007/978-3-642-02384-2_6 |
| [13] | Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24, 384-386 (1978). doi:10.1109/TIT.1978.1055873 · Zbl 0377.94018 |
| [14] | Bernstein, DJ; Lange, T., Post-quantum cryptography, Nature, 549, 188-194, 2017 · doi:10.1038/nature23461 |
| [15] | Borodin, MA; Chizhov, IV, Effective attack on the McEliece cryptosystem based on reed-muller codes, Discret. Math. Appl., 24, 5, 273-280, 2014 · Zbl 1403.94045 · doi:10.1515/dma-2014-0024 |
| [16] | Couvreur, A.; Lequesne, M.; Tillich, J-P; Ding, J.; Steinwandt, R., Recovering short secret keys of RLCE in polynomial time, Post-Quantum Cryptography, 133-152, 2019, Cham: Springer, Cham · Zbl 1509.94080 · doi:10.1007/978-3-030-25510-7_8 |
| [17] | Couvreur, A.; Márquez-Corbella, I.; Pellikaan, R.; Pinto, R.; Malonek, PR; Vettori, P., Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes, Coding Theory and Applications, 133-140, 2015, Cham: Springer, Cham · Zbl 1372.94418 · doi:10.1007/978-3-319-17296-5_13 |
| [18] | Couvreur, A.; Otmani, A.; Tillich, J-P; Gauthier-Umaña, V.; Katz, J., A polynomial-time attack on the BBCRS scheme, Public-Key Cryptography - PKC 2015, 175-193, 2015, Heidelberg: Springer, Heidelberg · Zbl 1345.94054 · doi:10.1007/978-3-662-46447-2_8 |
| [19] | Deundyak, VM; Kosolapov, YV; Maystrenko, IA; Baldi, M.; Persichetti, E.; Santini, P., On the decipherment of Sidel’nikov-type cryptosystems, Code-Based Cryptography, 20-40, 2020, Cham: Springer, Cham · Zbl 1459.94107 · doi:10.1007/978-3-030-54074-6_2 |
| [20] | Faugère, J-C; Otmani, A.; Perret, L.; Tillich, J-P; Gilbert, H., Algebraic cryptanalysis of McEliece variants with compact keys, Advances in Cryptology - EUROCRYPT 2010, 279-298, 2010, Heidelberg: Springer, Heidelberg · Zbl 1280.94051 · doi:10.1007/978-3-642-13190-5_14 |
| [21] | Fossorier, MP; Lin, S., Soft-decision decoding of linear block codes based on ordered statistics, IEEE Trans. Inf. Theory, 41, 5, 1379-1396, 1995 · Zbl 0833.94021 · doi:10.1109/18.412683 |
| [22] | Gabidulin, EM; Paramonov, AV; Tretjakov, OV; Davies, DW, Ideals over a non-commutative ring and their application in cryptology, Advances in Cryptology — EUROCRYPT ’91, 482-489, 1991, Heidelberg: Springer, Heidelberg · Zbl 0766.94009 · doi:10.1007/3-540-46416-6_41 |
| [23] | Gaborit, P.: Shorter keys for code based cryptography. In: Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), pp. 81-91 (2005) |
| [24] | Gallager, R., Low-density parity-check codes, IRE Trans. Inf. Theory, 8, 1, 21-28, 1962 · Zbl 0107.11802 · doi:10.1109/TIT.1962.1057683 |
| [25] | Gueye, CT; Klamti, JB; Hirose, S.; El Hajji, S.; Nitaj, A.; Souidi, EM, Generalization of BJMM-ISD using may-Ozerov nearest neighbor algorithm over an arbitrary finite field \(\mathbb{F}_q\), Codes, Cryptology and Information Security, 96-109, 2017, Cham: Springer, Cham · Zbl 1365.94429 · doi:10.1007/978-3-319-55589-8_7 |
| [26] | Guo, Q.; Johansson, T.; Wagner, PS, A key recovery reaction attack on QC-MDPC, IEEE Trans. Inf. Theory, 65, 1845-1861, 2019 · Zbl 1432.81024 · doi:10.1109/TIT.2018.2877458 |
| [27] | Interlando, C., Khathuria, K., Rohrer, N., Rosenthal, J., Weger, V.: Generalization of the ball-collision algorithm. arXiv preprint: arXiv:1812.10955 (2018) · Zbl 1468.94462 |
| [28] | Ivanov, F., Krouk, E., Zyablov, V.: New code-based cryptosystem based on binary image of generalized reed-Solomon code. In: 2021 XVII International Symposium “Problems of Redundancy in Information and Control Systems”(REDUNDANCY), pp. 66-69. IEEE (2021) |
| [29] | Janwa, H.; Moreno, O., McEliece public key cryptosystems using algebraic-geometric codes, Des. Codes Crypt., 8, 3, 293-307, 1996 · Zbl 0859.94008 · doi:10.1023/A:1027351723034 |
| [30] | Kosolapov, Y., Lelyuk, A.: Cryptanalysis of the BBCRS system on reed-muller binary codes. Bull. South Ural State Univ. Ser. Math. Modell. Program. Comput. Softw. 14, 18-32 (2021). doi:10.14529/mmp210302 · Zbl 1485.94100 |
| [31] | McEliece, RJ, Public-key cryptosystem based on algebraic coding theory, PL Deep Space Netw. Prog. Report, 42, 114-116, 1978 |
| [32] | Minder, L.; Shokrollahi, A.; Naor, M., Cryptanalysis of the Sidelnikov cryptosystem, Advances in Cryptology - EUROCRYPT 2007, 347-360, 2007, Heidelberg: Springer, Heidelberg · Zbl 1141.94365 · doi:10.1007/978-3-540-72540-4_20 |
| [33] | Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes, pp. 2069-2073. IEEE (2013). doi:10.1109/ISIT.2013.6620590 |
| [34] | Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in the McEliece cryptosystem, pp. 215. IEEE (2000). doi:10.1109/ISIT.2000.866513 |
| [35] | Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Prob. Control Inf. Theory, 15, 159-166, 1986 · Zbl 0611.94007 |
| [36] | Otmani, A.; Tillich, JP; Dallot, L., Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes, Math. Comput. Sci., 3, 129-140, 2010 · Zbl 1205.94095 · doi:10.1007/s11786-009-0015-8 |
| [37] | Overbeck, R.; Batten, LM; Safavi-Naini, R., Statistical decoding revisited, Information Security and Privacy, 283-294, 2006, Heidelberg: Springer, Heidelberg · Zbl 1176.94055 · doi:10.1007/11780656_24 |
| [38] | Overbeck, R., Structural attacks for public key cryptosystems based on Gabidulin codes, J. Cryptol., 21, 2, 280-301, 2008 · Zbl 1159.94009 · doi:10.1007/s00145-007-9003-9 |
| [39] | 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., 68, 4648-4660, 2020 · doi:10.1109/TCOMM.2020.2987898 |
| [40] | Sendrier, N.: On the structure of randomly permuted concatenated code. Ph.D. thesis, INRIA (1995) |
| [41] | Sendrier, N.; Yang, B-Y, Decoding one out of many, Post-Quantum Cryptography, 51-67, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94167 · doi:10.1007/978-3-642-25405-5_4 |
| [42] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124-134. IEEE (1994) |
| [43] | Sidelnikov, VM, A public-key cryptosystem based on binary reed-muller codes, Discret. Math. Appl., 4, 3, 191-208, 1994 · Zbl 0872.94040 · doi:10.1515/dma.1994.4.3.191 |
| [44] | Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized reed-solomon codes. Discrete Math. Appl. 2 (1992) · Zbl 0796.94006 |
| [45] | Tillich, J.P.: The decoding failure probability of MDPC codes, pp. 941-945. IEEE (2018). doi:10.1109/ISIT.2018.8437843 |
| [46] | Vasseur, V.: Post-quantum cryptography: a study of the decoding of QC-MDPC codes. Ph.D. thesis, Université de Paris (2021) |
| [47] | Vedenev, K.; Kosolapov, Y.; Deneuville, JC, Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem, Code-Based Cryptography, 137-153, 2023, Cham: Springer Nature Switzerland, Cham · Zbl 1521.94063 · doi:10.1007/978-3-031-29689-5_8 |
| [48] | Wang, Y.: Quantum resistant random linear code based public key encryption scheme RLCE. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 2519-2523. IEEE (2016) |
| [49] | Weger, V.: Information set decoding in the lee metric and the local to global principle for densities. Ph.D. thesis, PhD thesis, University of Zurich (2020) |
| [50] | Wieschebrink, C.; Sendrier, N., Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes, Post-Quantum Cryptography, 61-72, 2010, Heidelberg: Springer, Heidelberg · Zbl 1284.94124 · doi:10.1007/978-3-642-12929-2_5 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
