Square Code Attack on a Modified Sidelnikov Cryptosystem

1. Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009)

   Chapter  Google Scholar 

2. Berger, T.P., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35(1), 63–79 (2005)

   Article  MATH  MathSciNet  Google Scholar 

3. Chizhov, I.V., Borodin, M.A.: The failure of McEliece PKC based on Reed-Muller codes. IACR Cryptology ePrint Archive, Report 2013/287 (2013), http://eprint.iacr.org/

4. Courtois, N.T., Finiasz, M., Sendrier, N.: How to achieve a McEliece-based digital signature scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

5. 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. 73(2), 641–666 (2014), http://dx.doi.org/10.1007/s10623-014-9967-z

   Article  MATH  MathSciNet  Google Scholar 

6. Faugère, J.C., Gauthier, V., Otmani, A., Perret, L., Tillich, J.P.: A distinguisher for high rate McEliece cryptosystems. In: Proc. IEEE Inf. Theory Workshop, ITW 2011, Paraty, Brasil, pp. 282–286 (October 2011)

   Google Scholar 

7. Faugère, J.C., Gauthier, V., Otmani, A., Perret, L., Tillich, J.P.: A distinguisher for high rate McEliece cryptosystems. IEEE Trans. Inf. Theory 59(10), 6830–6844 (2013)

   Article  Google Scholar 

8. Faugère, J.C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.P.: Structural weakness of compact variants of the McEliece cryptosystem. In: Proc. IEEE Int. Symposium Inf. Theory, ISIT 2014, Honolulu, HI, USA, pp. 1717–1721 (July 2014)

   Google Scholar 

9. Faugère, J.C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.P.: Structural cryptanalysis of McEliece schemes with compact keys. Des. Codes Cryptogr. (2015), to appear, see also IACR Cryptology ePrint Archive, Report2014/210

   Google Scholar 

10. Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

11. Gaborit, P.: Shorter keys for code based cryptography. In: Proceedings of the 2005 International Workshop on Coding and Cryptography (WCC 2005), Bergen, Norway, pp. 81–91 (March 2005)

    Google Scholar 

12. Gauthier, V., Otmani, A., Tillich, J.P.: A distinguisher-based attack of a homomorphic encryption scheme relying on Reed-Solomon codes. CoRR abs/1203.6686 (2012)

    Google Scholar 

13. Gauthier, V., Otmani, A., Tillich, J.P.: A distinguisher-based attack on a variant of McEliece’s cryptosystem based on Reed-Solomon codes. CoRR abs/1204.6459 (2012)

    Google Scholar 

14. Gueye, C.T., Mboup, E.H.M.: Secure cryptographic scheme based on modified Reed Muller codes. International Journal of Security and its Applications 7(3), 55–64 (2013)

    Google Scholar 

15. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 4th edn. North–Holland, Amsterdam (1986)

    Google Scholar 

16. Márquez-Corbella, I., Pellikaan, R.: Error-correcting pairs for a public-key cryptosystem. preprint (2012) (preprint)

    Google Scholar 

17. McEliece, R.J.: A Public-Key System Based on Algebraic Coding Theory, pp. 114–116. Jet Propulsion Lab (1978), dSN Progress Report 44

    Google Scholar 

18. Minder, L., Shokrollahi, M.A.: Cryptanalysis of the Sidelnikov cryptosystem. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 347–360. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

19. Misoczki, R., Barreto, P.: Compact McEliece keys from Goppa codes. In: Selected Areas in Cryptography, Calgary, Canada (August 13-14, 2009)

    Google Scholar 

20. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory 15(2), 159–166 (1986)

    MATH  MathSciNet  Google Scholar 

21. Sendrier, N.: Cryptosystèmes à clé publique basés sur les codes correcteurs d’erreurs. Ph.D. thesis, Université Paris 6, France (2002)

    Google Scholar 

22. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)

    Article  MATH  MathSciNet  Google Scholar 

23. Sidelnikov, V.M.: A public-key cryptosytem based on Reed-Muller codes. Discrete Mathematics and Applications 4(3), 191–207 (1994)

    Article  MathSciNet  Google Scholar 

24. Sidelnikov, V.M., Shestakov, S.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 1(4), 439–444 (1992)

    MathSciNet  Google Scholar 

25. Wieschebrink, C.: Two NP-complete problems in coding theory with an application in code based cryptography. In: Proc. IEEE Int. Symposium Inf. Theory, ISIT 2006, pp. 1733–1737 (2006)

    Google Scholar 

26. Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. IACR Cryptology ePrint Archive, Report 2009/452 (2009), http://eprint.iacr.org/2009/452.pdf

27. Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Post-Quantum Cryptography 2010, pp. 61–72 (2010)

    Google Scholar 

Download references