A Polynomial-Time Attack on the BBCRS Scheme

详细信息    查看全文

• 作者：Alain Couvreur (15) (16)
  Ayoub Otmani (17)
  Jean-Pierre Tillich (14)
  Val茅rie Gauthier鈥揢ma帽a (18)
  
  15. INRIA ; Grace Team ; 1 rue H. d鈥橢stienne d鈥橭rves ; 91120 ; Palaiseau Cedex ; France
  16. 脡cole Polytechnique ; Grace Team and LIX ; CNRS UMR 7161 ; All茅e H. D鈥橢stienne d鈥橭rves ; 91120 ; Palaiseau Cedex ; France
  17. LITIS ; University of Rouen ; 76821 ; Mont-Saint-Aignan ; France
  14. INRIA ; Secret Team ; 78153 ; Le Chesnay Cedex ; France
  18. Faculty of Natural Sciences and Mathematics ; Department of Mathematics ; Universidad Del Rosario ; Bogot谩 ; Colombia
  
• 关键词：Code ; based cryptography ; Distinguisher ; Generalized Reed ; Solomon codes ; Key ; recovery ; Component ; wise product of codes
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9020
• 期：1
• 页码：175-193
• 全文大小：307 KB
• 参考文献：1. Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. preprint (2011). arXiv:1108.2462v2
  2. 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)
  3. Baldi, M, Bodrato, M, Chiaraluce, F A new analysis of the McEliece cryptosystem based on QC-LDPC codes. In: Ostrovsky, R, Prisco, R, Visconti, I eds. (2008) Security and Cryptography for Networks. Springer, Heidelberg, pp. 246-262 CrossRef
  4. 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鈥?595. Nice (March 2007)
  5. Barbulescu, R, Gaudry, P, Joux, A, Thom茅, E A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, PQ, Oswald, E eds. (2014) Advances in Cryptology 鈥?EUROCRYPT 2014. Springer, Heidelberg, pp. 1-16 CrossRef
  6. Berger, TP, Loidreau, P (2005) How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35: pp. 63-79 CrossRef
  7. Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: Selected Areas in Cryptography, pp. 143鈥?58 (2010)
  8. Biswas, B, Sendrier, N McEliece cryptosystem implementation: theory and practice. In: Buchmann, J, Ding, J eds. (2008) Post-Quantum Cryptography. Springer, Heidelberg, pp. 47-62 CrossRef
  9. Bosma, W, Cannon, JJ, Playoust, C (1997) The Magma algebra system I: The user language. J. Symbolic Comput. 24: pp. 235-265 CrossRef
  10. Cascudo, I., Cramer, R., Mirandola, D., Z茅mor, G.: Squares of random linear codes. arXiv:1407.0848v1
  11. 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鈥?6 (2014)
  12. 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鈥?9, 2013)
  13. 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)
  14. Couvreur, A, Otmani, A, Tillich, JP Polynomial time attack on wild McEliece over quadratic extensions. In: Nguyen, PQ, Oswald, E eds. (2014) Advances in Cryptology 鈥?EUROCRYPT 2014. Springer, Heidelberg, pp. 17-39 CrossRef
  15. 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鈥?86. Paraty, Brasil (2011)
  16. Faug猫re, JC, Gauthier-Uma帽a, V, Otmani, A, Perret, L, Tillich, JP (2013) A distinguisher for high-rate McEliece cryptosystems. IEEE Trans. Inform. Theory 59: pp. 6830-6844 CrossRef
  17. MacWilliams, FJ, Sloane, NJA (1986) The Theory of Error-Correcting Codes. North-Holland, Amsterdam
  18. M谩rquez-Corbella, I, Mart铆nez-Moro, E, Pellikaan, R (2013) The non-gap sequence of a subcode of a generalized Reed-Solomon code. Des. Codes Cryptogr. 66: pp. 317-333 CrossRef
  19. M谩rquez-Corbella, I., Pellikaan, R.: Error-correcting pairs for a public-key cryptosystem. preprint (2012)
  20. McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114鈥?16. Jet Propulsion Lab (1978), dSN Progress Report 44
  21. 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鈥?073 (2013)
  22. 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)
  23. Niederreiter, H (1986) Knapsack-type cryptosystems and algebraic coding theory. Problems Control Inform. Theory 15: pp. 159-166
  24. 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鈥?34. IEEE Computer Society, Los Alamitos (1994)
  25. Sidelnikov, V, Shestakov, S (1992) On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Math. Appl. 1: pp. 439-444
  26. Wieschebrink, C Cryptanalysis of the niederreiter public key scheme based on GRS subcodes. In: Sendrier, N eds. (2010) Post-Quantum Cryptography. Springer, Heidelberg, pp. 61-72 CrossRef
  
• 作者单位：Public-Key Cryptography -- PKC 2015
• 丛书名：978-3-662-46446-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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 , 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.