Cryptanalysis of the BBCRS System on Reed–Muller Binary Codes

The paper considers the BBCRS system which is a modification of the McEliece cryptosystem proposed by M. Baldi and some others. In this modification matrix G_{pub} of the public key is the product of three matrices: a non-singular (k\times k)-matrix S, a generator matrix G of a secret [n,k]_q-code C_{sec}, and a non-singular (n\times n)-matrix Q. The difference between the modified system and the original system is that the permutation matrix used in the McEliece system is replaced by a non-singular matrix Q. The matrix Q is obtained as the sum of a permutation matrix P and a matrix R of small rank r(R). Later, V. Gauthier and some others constructed an attack that allows decrypting messages in the case when C_{sec} is a generalized Reed-Solomon code (GRS code) and r(R)=1. The key stages of the constructed attack are, firstly, finding the intersection of the linear span \mathcal{L}(G_{pub})=C_{pub} and \mathcal{L}(G P)=C that spanned on the rows of the matrices G_{pub} and G P respectively, and secondly, finding the code C by the subcode C_{pub}\cap C. In this paper we present an attack in the case when C_{sec} is the Reed-Muller binary code of order r, length 2^m and r(R)=1. The stages of finding the codes C_{pub}\cap C and C in this paper are completely different from the corresponding steps in attack by V. Gauthier and some others and other steps are the adaptation of the known results of cryptanalysis that applied in the case of GRS codes.

Keywords

BBCRS cryptosystem; Reed-Muller codes; cryptanalysis.

References

1. McEliece R.J. A Public-Key Cryptosystem Based On Algebraic Coding Theory. DSN Progress Report, 1978, pp. 42-44.
2. Sendrier N. Finding the Permutation Between Equivalent Linear Codes: the Support Splitting Algorithm. IEEE Transactions on Information Theory, 2000, vol. 46, no. 4, pp. 1193-1203.
3. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem. Advances in Cryptology, 2007, vol. 4515, pp. 347-360. DOI: 10.1007/978-3-540-72540-4_20
4. Borodin M.A., Chizhov I.V. Efficiency of Attack on the McEliece Cryptosystem Constructed on the Basis of Reed-Muller Codes. Discrete Mathematics and Applications, 2014, vol. 24, no. 5, pp. 273-280. DOI: 10.1515/dma-2014-0024
5. Sidel'nikov V.M., Shestakov S.O. On an Encoding System Constructed on the Basis of Generalized Reed-Solomon Codes. Discrete Mathematics and Applications, 1992, vol. 2, no. 4, pp. 439-444. DOI: 10.1515/dma.1994.4.3.191
6. Wieschebrink C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes. Post-Quantum Cryptography, Darmstadt, 2010, pp. 61-72. DOI: 10.1007/978-3-642-12929-2_5
7. Chizhov I.V., Borodin M.A. Hadamard Products Classification of Subcodes of Reed–Muller Codes Codimension 1. Discrete Mathematics and Applications, 2020, vol. 32, no. 1, pp. 115-134.
8. Berger T., Loidreau P. How to Mask the Structure of Codes for a Cryptographic Use. Designs, Codes and Cryptography, 2005, vol. 35, no. 1, pp. 63-79.
9. Sidelnikov V.M. Public-Key Cryptosystem Based on Binary Reed-Muller Codes. Discrete Mathematics and Applications, 1994, vol. 4, no. 3, pp. 191-208. DOI: 10.1515/dma.1994.4.3.191
10. Egorova E., Kabatiansky G., Krouk E., Tavernier C. A New Code-Based Public-Key Cryptosystem Resistant to Quantum Computer Attacks. Journal of Physics, 2019, no. 1163, pp. 1-5. DOI: 10.1088/1742-6596/1163/1/012061
11. Deundyak V.M., Kosolapov Yu.V. On the Strength of Asymmetric Code Cryptosystems Based on the Merging of Generating Matrices of Linear Codes. Proceedings of the XVI International Symposium Problems of Redundancy in Information and Control Systems, Moscow, 2019, pp. 143-148.
12. Baldi M., Bianchi M., Chiaraluce F., Rosenthal J., Schipani D. Enhanced Public Key Security for the McEliece Cryptosystem. Available at: https://arxiv.org/abs/1108.2462 (accessed 28 July 2021).
13. Randriambololona H. On Products and Powers of Linear Codes Under Componentwise Multiplication. Available at: http://arxiv.org/abs/1312.0022 (accessed 28 July 2021).
14. Gauthier V., Otmani A., Tillich J.-P. A Distinguisher-Based Attack on a Variant of McEliece's Cryptosystem Based on Reed-Solomon Codes. Available at: https://arxiv.org/abs/1204.6459 (accessed 28 July 2021).
15. Betten A., Braun M., Fripertinger H., Kerber A., Kohnert A., Wassermann A. Error-Correcting Linear Codes: Classification by Isometry and Applications, Heidelberg, Springer, 2006.