×

zbMATH — the first resource for mathematics

Code-based cryptosystems using generalized concatenated codes. (English) Zbl 1384.94097
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 397-423 (2017).
Summary: The security of public-key cryptosystems is mostly based on number-theoretic problems like factorization and the discrete logarithm. There exists an algorithm which solves these problems in polynomial time using a quantum computer. Hence, these cryptosystems will be broken as soon as quantum computers emerge. Code-based cryptography is an alternative which resists quantum computers since its security is based on an NP-complete problem, namely decoding of random linear codes. The McEliece cryptosystem is the most prominent scheme to realize code-based cryptography. Many code classes were proposed for the McEliece cryptosystem, but most of them are broken by now. Sendrier suggested to use ordinary concatenated codes, however, he also presented an attack on such codes. This work investigates generalized concatenated codes to be used in the McEliece cryptosystem. We examine the application of Sendrier’s attack on generalized concatenated codes and present alternative methods for both partly finding the code structure and recovering the plaintext from a cryptogram. Further, we discuss modifications of the cryptosystem making it resistant against these attacks.
For the entire collection see [Zbl 1379.13001].
MSC:
94A60 Cryptography
Software:
McEliece
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in · Zbl 1291.94206
[2] 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) · Zbl 1136.11327
[3] 3. Berlekamp, E.R., McEliece, R.J., Van Tilborg, H.C.A.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24 (3), 384-386 (1978) · Zbl 0377.94018
[4] 4. Bossert, M.: Channel Coding for Telecommunications. Wiley, New York (1999)
[5] 5. Blokh, È.L., Zyablov, V.V.: Coding of generalized concatenated codes. Problemy Peredachi Informatsii 10 (3), 45-50 (1974) · Zbl 0309.94030
[6] 6. Chizhov, I.V., Borodin, M.A.: The failure of McEliece PKC based on Reed-Muller codes. IACR Cryptol. ePrint Arch. 2013 , 287 (2013)
[7] 7. Coffey, J.T., Goodman, R.M.: The complexity of information set decoding. IEEE Trans. Inf. Theory 36 (5), 1031-1037 (1990) · Zbl 0738.94021
[8] 8. Couvreur, A., Márquez-Corbella, I., Pellikaan, R.: A polynomial time attack against algebraic geometry code based public key cryptosystems (2014). · Zbl 1398.94107
[9] 9. Chabanne, H., Sendrier, N.: On the concatenated structures of a [49, 18, 12] binary abelian code. Discret. Math. 112 (1), 245-248 (1993) · Zbl 0772.94009
[10] 10. Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22 (6), 644-654 (1976) · Zbl 0435.94018
[11] 11. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31 (4), 469-472 (1985) · Zbl 0571.94014
[12] 12. Forney, D.G.: Concatenated codes. vol. 11 MIT press, Cambridge (1966)
[13] 13. Heyse, S.: Post quantum cryptography: implementing alternative public key schemes on embedded devices. PhD thesis, dissertation for the degree of doktor-ingenieur: 10.2013/Stefan Heyse.-Bochum, 2013.-235 p.-Bibliogr (2013)
[14] 14. Janwa, H., Moreno, O.: McEliece public key cryptosystems using algebraic-geometric codes. Des. Codes Cryptogr. 8 (3), 293-307 (1996) · Zbl 0859.94008
[15] 15. Justesen, J.: Class of constructive asymptotically good algebraic codes. IEEE Trans. Inf. Theory 18 (5), 652-656 (1972) · Zbl 0256.94008
[16] 16. Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg. (1988) · Zbl 0655.94006
[17] 17. Li, Y.X., Deng, R.H., Wang, X.M.: On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Trans. Inf. Theory 40 (1), 271-273 (1994) · Zbl 0803.94016
[18] 18. Lidl, R., Niederreiter, H.: Finite Fields, vol. 20. Cambridge University Press, Cambridge (1997) · Zbl 1139.11053
[19] 19. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42 (44), 114-116 (1978)
[20] 20. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. Elsevier, Amsterdam (1977) · Zbl 0369.94008
[21] 21. Minder, L., Shokrollahi, A.: Cryptanalysis of the Sidelnikov cryptosystem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 347-360. Springer, Berlin (2007) · Zbl 1141.94365
[22] 22. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory (Problemy Upravleniya I Teorii Informatsii) 15 (2), 159-166 (1986) · Zbl 0611.94007
[23] 23. Peters, C.: Information-set decoding for linear codes over · Zbl 1284.94101
[24] 24. Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21 (2), 120-126 (1978) · Zbl 0368.94005
[25] 25. Sendrier, N.: On the structure of randomly permuted concatenated code. [Research Report] RR-2460, INRIA (1995). <inria-00074216>
[26] 26. Sendrier, N.: On the concatenated structure of a linear code. Appl. Algebra Eng. Commun. Comput. 9 (3), 221-242 (1998) · Zbl 0915.94008
[27] 27. Shor, P.W.: Algorithms for quantum computation: discrete Logarithms and factoring. In: 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124-134. IEEE (1994)
[28] 28. Sidelnikov, V.M.: Public-key cryptosystem based on binary Reed-Muller codes. Discret. Math. Appl. 4 (3), 191-207 (1994) · Zbl 0872.94040
[29] 29. Sidelnikov, V.M., Shestakov, S.O.: On the insecurity of cryptosystems based on generalized Reed-Solomon codes. Discret. Math. Appl. 2 (4), 439-444 (1992) · Zbl 0796.94006
[30] 30. Wardlaw, W.P.: Matrix representation of finite fields. Math. Mag. 67 , 289-293 (1994) · Zbl 0832.11044
[31] 31. Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: International Workshop on Post-Quantum Cryptography, pp. 61-72. Springer, Berlin (2010) · Zbl 1284.94124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.