TY - GEN

T1 - Code-based cryptosystems using generalized concatenated codes

AU - Puchinger, Sven

AU - Müelich, Sven

AU - Ishak, Karim

AU - Bossert, Martin

N1 - Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

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

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

KW - Code-based cryptosystems

KW - Generalized concatenated codes

KW - McEliece cryptosystem

KW - Post-Quantum cryptography

UR - http://www.scopus.com/inward/record.url?scp=85028321024&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-56932-1_26

DO - 10.1007/978-3-319-56932-1_26

M3 - Conference contribution

AN - SCOPUS:85028321024

SN - 9783319569307

T3 - Springer Proceedings in Mathematics and Statistics

SP - 397

EP - 423

BT - Applications of Computer Algebra

A2 - Kotsireas, Ilias S.

A2 - Martinez-Moro, Edgar

PB - Springer New York LLC

T2 - 21st International Conference on Applications of Computer Algebra, ACA 2015

Y2 - 20 July 2015 through 23 July 2015

ER -