Effective structural attack on McEliece-Sidelnikov public-key cryptosystem

Ivan Chizhov, Sergei Koniukhov, Alexandra Davletshina

Abstract


The authors propose an algorithm for recovering the secret key of the MсEliece–Sidelnikov cryptosystem in general case: with u ∈ N copies of the Reed–Muller codes. Recovering the secret key of the McEliece–Sidelnikov cryptosystem is reduced to u problems of recovering the secret key of the McEliece cryptosystem  based on the Reed–Muller codes. It is proved in the paper that the proposed attack is polynomial. A set of keys for which the algorithm is applicable is described. The set is called the set of weak keys. The authors believe that the most of the keys are weak and show that it should be assumed that the ratio of the weak keys in the cryptosystem’s key space is close to one. Methods for calculating the number of the weak keys are described and computational experiments confirming it have  been performed.

Full Text:

PDF (Russian)

References


McEliece Robert J. A public­key cryptosystem based on algebraic coding theory // DSN Progress Report. –– 1978. –– Vol. 42–44. –– P. 114–116.

Shor Peter W. Polynomial­time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Journal on Computing. –– 1997. –– Oct. –– Vol. 26, no. 5. –– P. 1484–1509.

Niederreiter Harald. Knapsack­type cryptosystems and algebraic cod­

ing theory // Prob. Control and Inf. Theory. –– 1986. –– Vol. 15, no. 2. –– P. 159–166.

Sidelnikov V. M. Public encryption based on reed–muller codes // Discrete Math. Appl. –– 1994. –– Vol. 6, no. 2. –– P. 3–20.

Courtois Nicolas T., Finiasz Matthieu, Sendrier Nicolas. How to achieve a mceliece­based digital signature scheme // Advances in Cryptology — ASIACRYPT 2001 / Ed. by Colin Boyd. –– Lecture Notes in Computer Science. –– Springer, 2001. –– P. 157–174.

Minder Lorenz, Shokrollahi Amin. Cryptanalysis of the sidelnikov cryptosystem // Annual International Conference on the Theory and Applications of Cryptographic Techniques / Springer. –– 2007. –– P. 347–360.

Borodin M. A., Chizhov I. V. Jeffektivnaja ataka na kriptosistemu mak­ jelisa, postroennuju na osnove kodov rida–mallera // Discrete Math. Appl. –– Vol. 26, no. 1. –– P. 10–20.

Wieschebrink Christian. Cryptanalysis of the niederreiter public key scheme based on grs subcodes // International Workshop on Post­ Quantum Cryptography / Springer. –– 2010. –– P. 61–72.

A polynomial­time attack on the bbcrs scheme / Alain Couvreur, Ayoub Otmani, Jean­Pierre Tillich, Valérie Gauthier­Umana // IACR International Workshop on Public Key Cryptography / Springer.–– 2015. –– P. 175–193.

Squares of random linear codes / Ignacio Cascudo, Ronald Cramer, Diego Mirandola, Gilles Zémor // IEEE Transactions on Information Theory. –– 2015. –– Vol. 61, no. 3. –– P. 1159–1173.

Chizhov I. V., Borodin M. A. Hadamard products classification of subcodes of reed–muller codes codimension 1 // Discrete Math. Appl. –– 2020. –– Vol. 32, no. 1. –– P. 115–134.

Davletshina A. M. Search for equivalent keys of the mceliece ­ sidelnikov cryptosystem built on the reed ­ muller binary codes // Prikladnaya diskretnaya matematika. Prilozhenie. –– no. 12. –– P. 98– 100. –– URL: http://journals.tsu.ru/pdm2/&journal_page=archive&id= 1897&article_id=42419.

MacWilliams Florence Jessie, Sloane Neil J. A. The theory of error­ correcting codes. North­Holland mathematical Library no. 16. –– 2. print edition.–– North­Holland.–– ISBN: 978­0­444­85010­2 978­0­ 444­85009­6. –– OCLC: 613292217.

Legeay Matthieu, Loidreau Pierre. Projected subcodes of the second order binary reed­muller code // 2012 IEEE International Symposium on Information Theory Proceedings / IEEE. –– 2012. –– P. 254–258.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162