Abstract
We present a structural attack against the Sidelnikov cryptosystem [8]. The attack creates a private key from a given public key. Its running time is subexponential and is effective if the parameters of the Reed-Muller code allow for efficient sampling of minimum weight codewords. For example, the length 2048, 3rd-order Reed-Muller code as proposed in [8] takes roughly an hour to break on a stock PC using the presented method.
Chapter PDF
Similar content being viewed by others
References
Canteaut, A., Chabaut, F.: A new algorithm for finding minimum-weight words in a linear code: application to primitive narrow-sense BCH-codes of length 511. IEEE Transactions on Information Theory 44(1), 367–378 (1998)
Dumer, I., Shabunov, K.: Soft-decision decoding of Reed-Muller codes: a simplified algorithm. IEEE Transactions on Information Theory 52(3), 954–963 (2006)
Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge (2003)
Kasami, T., Tokura, N.: On the Weight Structure of Reed-Muller Codes. IEEE Transactions on Information Theory 16(6), 752–759 (1970)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1978)
McEliece, R.J.: A public key cryptosystem based on algebraic coding theory. DSN progress report 42-44, 114–116 (1978)
Niederreiter, H.: Knapsack-Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15(2), 159–166 (1986)
Sidelnikov, V.M.: A public-key cryptosystem based on binary Reed-Muller codes. Discrete Mathematics and Applications 4(3) (1994)
Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 2(4), 439–444 (1992)
Sendrier, N.: On the Structure of a randomly permuted concatenated code. In: EUROCODE’94 (October 1994)
Sendrier, N.: Finding the permutation between equivalent codes: the support splitting algorithm. IEEE Transactions on Information Theory 46(4), 1193–1203 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Minder, L., Shokrollahi, A. (2007). Cryptanalysis of the Sidelnikov Cryptosystem. In: Naor, M. (eds) Advances in Cryptology - EUROCRYPT 2007. EUROCRYPT 2007. Lecture Notes in Computer Science, vol 4515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72540-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-72540-4_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72539-8
Online ISBN: 978-3-540-72540-4
eBook Packages: Computer ScienceComputer Science (R0)