О криптоанализе системы BBCRS на двоичных кодах Рида-Маллера

В работе рассматривается система система BBCRS - модификация криптосистемы Мак-Элиса, предложенная М. Балди и др. В модификации матрица G_{pub} публичного ключа представляет собой произведение трех матриц: невырожденной (k\times k)-матрицы S, порождающей матрицы G секретного [n,k]_q-кода C_{sec} и невырожденной (n\times n)-матрицы Q специального вида. Отличие системы BBCRS от системы, предложенной Р. Мак-Элисом, состоит в том, что подстановочная матрица, используемая в системе Мак-Элиса, заменена матрицей Q, представляющей сумму подстановочной матрицы P и матрицы R малого ранга r(R). Позже В. Готье и др. построили атаку, позволяющую дешифровать сообщения в случае, когда C_{sec} - обобщенный код Рида - Соломона (ОРС-код) и r(R)=1. Ключевыми этапами построенной атаки являются, во-первых, нахождение пересечения линейных оболочек L(G_{pub})=C_{pub} и L(G P)=C, натянутых соответственно на строки матриц G_{pub} и G P, а во-вторых, нахождение кода С по подкоду C_{pub}\cap C. В настоящей работе строится атака в случае, когда C_{sec}=RM(r,m) - двоичный код Рида - Маллера порядка r и длины 2^m при r(R)=1. В построенной в настоящей работе атаке этапы нахождения кодов C_{pub}\cap C и C полностью отличаются от соответствующих этапов для ОРС-кодов, а остальные шаги атаки адаптируют известные результаты криптоанализа системы BBCRS на ОРС-кодах.

Ключевые слова

криптосистема BBCRS; коды Рида – Маллера; криптоанализ.

Литература

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.