Abstract
The BBCRS scheme is a variant of the McEliece public-key encryption scheme where the hiding phase is performed by taking the inverse of a matrix which is of the form \(\varvec{T}+ \varvec{R}\) where \(\varvec{T}\) is a sparse matrix with average row/column weight equal to a very small quantity \(m\), usually \(m < 2\), and \(\varvec{R}\) is a matrix of small rank \(z\ge 1\). The rationale of this new transformation is the reintroduction of families of codes, like generalized Reed-Solomon codes, that are famously known for representin insecure choices. We present a key-recovery attack when \(z =1\) and \(m\) is chosen between \(1\) and \(1+R+O(\frac{1}{\sqrt{n}})\) where \(R\) denotes the code rate. This attack has complexity \(O(n^6)\) and breaks all the parameters suggested in the literature.
Chapter PDF
Similar content being viewed by others
Keywords
References
Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. preprint (2011). arXiv:1108.2462v2
Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. J. of Cryptology (2014). http://link.springer.com/article/10.1007/s00145-014-9187-8 and also ArXiv:1108.2462v4 (published online: August 15, 2014)
Baldi, M., Bodrato, M., Chiaraluce, F.: A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 246–262. Springer, Heidelberg (2008)
Baldi, M., Chiaraluce, G.F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. In: IEEE International Symposium on Information Theory, pp. 2591–2595. Nice (March 2007)
Barbulescu, R., Gaudry, P., Joux, A., Thomé, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1–16. Springer, Heidelberg (2014)
Berger, T.P., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35(1), 63–79 (2005)
Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: Selected Areas in Cryptography, pp. 143–158 (2010)
Biswas, B., Sendrier, N.: McEliece cryptosystem implementation: theory and practice. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 47–62. Springer, Heidelberg (2008)
Bosma, W., Cannon, J.J., Playoust, C.: The Magma algebra system I: The user language. J. Symbolic Comput. 24(3/4), 235–265 (1997)
Cascudo, I., Cramer, R., Mirandola, D., Zémor, G.: Squares of random linear codes. arXiv:1407.0848v1
Couvreur, A., Gaborit, P., Gauthier-Umaña, V., Otmani, A., Tillich, J.P.: Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr., pp. 1–26 (2014)
Couvreur, A., Gaborit, P., Gauthier-Umaña, V., Otmani, A., Tillich, J.P.: Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. In: International Workshop on Coding and Cryptography, WCC 2013. Bergen, Norway (April 15–19, 2013)
Couvreur, A., Márquez-Corbella, I., Pellikaan, R.: A polynomial time attack against algebraic geometry code based public key cryptosystems. In: IEEE International Symposium on Information Theory (ISIT 2014). Honolulu, US (2014)
Couvreur, A., Otmani, A., Tillich, J.P.: Polynomial time attack on wild McEliece over quadratic extensions. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 17–39. Springer, Heidelberg (2014)
Faugère, J.C., Gauthier, V., Otmani, A., Perret, L., Tillich, J.P.: A distinguisher for high rate McEliece cryptosystems. In: Proceedings of the Information Theory Workshop 2011. ITW 2011, pp. 282–286. Paraty, Brasil (2011)
Faugère, J.C., Gauthier-Umaña, V., Otmani, A., Perret, L., Tillich, J.P.: A distinguisher for high-rate McEliece cryptosystems. IEEE Trans. Inform. Theory 59(10), 6830–6844 (2013)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 5th edn. North-Holland, Amsterdam (1986)
Márquez-Corbella, I., Martínez-Moro, E., Pellikaan, R.: The non-gap sequence of a subcode of a generalized Reed-Solomon code. Des. Codes Cryptogr. 66(1–3), 317–333 (2013)
Márquez-Corbella, I., Pellikaan, R.: Error-correcting pairs for a public-key cryptosystem. preprint (2012)
McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–116. Jet Propulsion Lab (1978), dSN Progress Report 44
Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In: ISIT, pp. 2069–2073 (2013)
Monico, C., Rosenthal, J., Shokrollahi, A.: Using low density parity check codes in the McEliece cryptosystem. In: IEEE International Symposium on Information Theory (ISIT 2000), p. 215. Sorrento, Italy (2000)
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems Control Inform. Theory 15(2), 159–166 (1986)
Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Goldwasser, S. (ed.) Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, pp. 124–134. IEEE Computer Society, Los Alamitos (1994)
Sidelnikov, V., Shestakov, S.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Math. Appl. 1(4), 439–444 (1992)
Wieschebrink, C.: Cryptanalysis of the niederreiter public key scheme based on GRS subcodes. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 61–72. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Couvreur, A., Otmani, A., Tillich, JP., Gauthier–Umaña, V. (2015). A Polynomial-Time Attack on the BBCRS Scheme. In: Katz, J. (eds) Public-Key Cryptography -- PKC 2015. PKC 2015. Lecture Notes in Computer Science(), vol 9020. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46447-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-662-46447-2_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46446-5
Online ISBN: 978-3-662-46447-2
eBook Packages: Computer ScienceComputer Science (R0)