Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomial-time after the emergence of quantum computers). While the McEliece PKC is based on another theory, i.e. coding theory, it is vulnerable against several practical attacks. In this paper, we carefully review currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose slightly modified versions of McEliece PKC that can be proven, in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversions can achieve the reduction of the redundant data down to 1/3 ∼ 1/4 compared with the generic conversions for practical parameters.
Since the concept of public-key cryptosystem (PKC) was introduced by Diffie and Hellman , many researchers have proposed numerous PKCs based on various problems, such as integer factoring, discrete logarithm, decoding a large linear code, knapsack, inverting polynomial equations and so on. While some of them are still alive, most of them were broken by cryptographers due to their intensive cryptanalysis. As a result, almost all of the current (so-called) secure systems employ only a small class of PKCs, such as RSA and elliptic curve cryptosystems, which are all based on either integer factoring problem (IFP) or discrete logarithm problem (DLP). This situation would cause a serious problem after someone discovers one practical algorithm which breaks both IFP and DLP in polynomial-time. No one can say that such an algorithm will never be found. Actually, Shor has already found a (probabilistic) polynomial-time algorithm in , even though it requires a quantum computer that is impractical so far. In order to prepare for that unfortunate situation, we need to find another secure scheme relying on neither IFP nor DLP.
The McEliece PKC, proposed by R.J. McEliece in , is one of few alternatives1 for PKCs based on IFP or DLP. It is based on the decoding problem of a large linear code with no visible structure which is conjectured to be an NP-complete problem.2 While no polynomial-time algorithm has been discovered yet for decoding an arbitrary linear code of large length with no visible structure, a lot of attacks (some of them work in polynomial-time) are known to the McEliece PKC [1,3,4,12,15,28,17,13].
In this paper, we carefully review these attacks in Section 3, and then point out that all the polynomial-time attacks to the McEliece PKC require either decryption oracles or partial knowledge on the corresponding plaintext of the challenge ciphertext. And then without them, no polynomial-time attack is known to invert the McEliece PKC (whose parameters are carefully chosen). Under the assumption that this inverting problem is hard, we convert this problem into semantically secure McEliece PKCs against adaptive chosen-ciphertext attacks (CCA2) by introducing some appropriate conversions. We discuss which conversions are appropriate for the McEliece PKC in Section 4. While some of the generic conversions proposed in [24,9] are also applicable to the McEliece PKC, they have a disadvantage in data redundancy (which is defined by the difference between the ciphertext size and the plaintext size). A large amount of redundant data is needed for the generic conversions since the block size of the McEliece PKC is relatively large. Our conversions in Section 4.4 need less redundant data than the generic ones.
2 McEliece Public-Key Cryptosystem
In this section, we briefly describe the McEliece PKC.
Key generation: Generate the following three matrices G,S,P:
G: k × n generator matrix of a binary Goppa code which can correct up to t errors, and for which an efficient decoding algorithm is known. The parameter t is given by dmin−1 2 where dmin denotes the minimum Hamming distance of the code.
3 Attacks to McEliece PKC
In this section, we review currently known attacks to the McEliece PKC.
While no efficient algorithm has been discovered yet for decomposing G into (S, G, P) , a structural attack has been discovered in . This attack reveals part of structure of a weak G which is generated from a “binary” Goppa polynomial. However, this attack can be avoided simply by avoiding the use of such weak public keys. (This implies G should not be a BCH code since it is equivalent to a Goppa code whose Goppa polynomial is 1 · x2t , i.e. “binary”. 3) Next case we have to consider is that an equivalent Goppa code of G (which is not necessarily G) and whose decoding algorithm is known happens to be found. This probability is estimated in , and then shown to be negligibly small.
All the other known attacks are for decrypting ciphertexts without breaking public-keys. We categorize them into the following two categories, critical attacks and non-critical attacks, according to whether these attacks can be avoided simply by enlarging the parameter size or not. If avoided, we categorize it in the non-critical attacks. Otherwise, in the critical ones. Interestingly, all the critical attacks require either additional information, such as partial knowledge on the target plaintexts, or an decryption oracle which can decrypt arbitrarily given ciphertexts except the challenge ciphertexts. And then without this additional information and this ability, no efficient algorithm is known to decrypt an arbitrarily given ciphertext of the McEliece PKC.
3.1 Non-critical Attacks
The following two attacks can be avoided simply by enlarging the parameter size or by applying Loidreau’s modification  without enlarging the parameter size. Thus, not critical.
3.2 Critical Attacks
The following attacks cannot be avoided by enlarging the parameter size or by applying Loidreau’s modification . Therefore critical.