McEliece cryptosystem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and — more generally — measuring coset states using Fourier sampling.[2]

The algorithm is based on the hardness of decoding a general linear code (which is known to be NP-hard[3]). For a description of the private key, an error-correcting code is selected for which an efficient decoding algorithm is known, and which is able to correct errors. The original algorithm uses binary Goppa codes (subfield codes of geometric Goppa codes of a genus-0 curve over finite fields of characteristic 2); these codes can be efficiently decoded, thanks to an algorithm due to Patterson.[4] The public key is derived from the private key by disguising the selected code as a general linear code. For this, the code's generator matrix is perturbated by two randomly selected invertible matrices and (see below).

Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by structural decoding.

McEliece with Goppa codes has resisted cryptanalysis so far. The most effective attacks known use information-set decoding algorithms. A 2008 paper describes both an attack and a fix.[5] Another paper shows that for quantum computing, key sizes must be increased by a factor of four due to improvements in information set decoding.[6]

The McEliece cryptosystem has some advantages over, for example, RSA. The encryption and decryption are faster.[7] For a long time, it was thought that McEliece could not be used to produce signatures. However, a signature scheme can be constructed based on the Niederreiter scheme, the dual variant of the McEliece scheme. One of the main disadvantages of McEliece is that the private and public keys are large matrices. For a standard selection of parameters, the public key is 512 kilobits long.

Scheme definition[edit]

McEliece consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm.

All users in a McEliece deployment share a set of common security parameters: .

Key generation[edit]

The principle is that Alice chooses a linear code from some family of codes for which she knows an efficient decoding algorithm, and to make public knowledge but keep the decoding algorithm secret. Such a decoding algorithm requires not just knowing , in the sense of knowing an arbitrary generator matrix, but requires one to know the parameters used when specifying in the chosen family of codes. For instance, for binary Goppa codes, this information would be the Goppa polynomial and the code locators. Therefore, Alice may publish a suitably obfuscated generator matrix of publicly.

More specifically, the steps are as follows:

  1. Alice selects a binary -linear code capable of (efficiently) correcting errors from some large family of codes, e.g. binary Goppa codes. This choice should give rise to an efficient decoding algorithm . Let also be any generator matrix for . Any linear code has many generator matrices, but often there is a natural choice for this family of codes. Knowing this would reveal so it should be kept secret.
  2. Alice selects a random binary non-singular matrix .
  3. Alice selects a random permutation matrix .
  4. Alice computes the matrix .
  5. Alice's public key is ; her private key is . Note that could be encoded and stored as the parameters used for selecting .

Message encryption[edit]

Suppose Bob wishes to send a message m to Alice whose public key is :

  1. Bob encodes the message as a binary string of length .
  2. Bob computes the vector .
  3. Bob generates a random -bit vector containing exactly ones (a vector of length and weight )[1]
  4. Bob computes the ciphertext as .

Message decryption[edit]

Upon receipt of , Alice performs the following steps to decrypt the message:

  1. Alice computes the inverse of (i.e. ).
  2. Alice computes .
  3. Alice uses the decoding algorithm to decode to .
  4. Alice computes .

Proof of message decryption[edit]

Note that , and that is a permutation matrix, thus has weight .

The Goppa code can correct up to errors, and the word is at distance at most from . Therefore, the correct code word is obtained.

Multiplying with the inverse of gives , which is the plain text message.

Key sizes[edit]

McEliece originally suggested security parameter sizes of ,[1] resulting in a public key size of 524*(1024-524) = 262,000 bits[clarification needed]. Recent analysis suggests parameter sizes of for 80 bits of security when using standard algebraic decoding, or when using list decoding for the Goppa code, giving rise to public key sizes of 520,047 and 460,647 bits respectively.[5] For resiliency against quantum computers, sizes of with Goppa code were proposed, giving the size of public key of 8,373,911 bits.[8]

Attacks[edit]

An attack consists of an adversary, who knows the public key but not the private key, deducing the plaintext from some intercepted ciphertext . Such attempts should be infeasible.

There are two main branches of attacks for McEliece:

Brute-force / Unstructured attacks[edit]

The attacker knows which is the generator matrix of an code which is combinatorially able to correct errors. The attacker may ignore the fact that is really the obfuscation of a structured code chosen from a specific family, and instead just use an algorithm for decoding with any linear code. Several such algorithms exist, such as going through each codeword of the code, syndrome decoding, or information set decoding.

Decoding a general linear code, however, is known to be NP-hard[3], however, and all of the above-mentioned methods have exponential running time.

In 2008, Bernstein, Lange and Peters[5] described a practical attack on the original McEliece cryptosystem, using the Information Set Decoding method by Stern[9]. Using the parameters originally suggested by McEliece, the attack could be carried out in 260.55 bit operations. Since the attack is embarrassingly parallel (no communication between nodes is necessary), it can be carried out in days on modest computer clusters.

Structural attacks[edit]

The attacker may instead attempt to recover the "structure" of , thereby recovering the efficient decoding algorithm or another sufficiently strong, efficient decoding algorithm.

The family of codes from which is chosen completely determines whether this is possible for the attacker. Many code families have been proposed for McEliece, and most of them have been completely "broken" in the sense that attacks which recover an efficient decoding algorithm has been found, such as Reed-Solomon codes.

The originally proposed binary Goppa codes remain one of the few suggested families of codes which have largely resisted attempts at devising structural attacks.

References[edit]

  1. ^ a b c McEliece, Robert J. (1978). "A Public-Key Cryptosystem Based On Algebraic Coding Theory" (PDF). DSN Progress Report. 44: 114–116. Bibcode:1978DSNPR..44..114M.
  2. ^ Dinh, Hang; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks. Advances in cryptology—CRYPTO 2011. Lecture Notes in Computer Science. 6841. Heidelberg: Springer. pp. 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. MR 2874885.
  3. ^ a b Berlekamp, Elwyn R.; McEliece, Robert J.; Van Tilborg, Henk C.A. (1978). "On the Inherent Intractability of Certain Coding Problems". IEEE Transactions on Information Theory. IT-24 (3): 384–386. doi:10.1109/TIT.1978.1055873. MR 0495180.
  4. ^ N. J. Patterson (1975). "The algebraic decoding of Goppa codes". IEEE Transactions on Information Theory. IT-21 (2): 203–207. doi:10.1109/TIT.1975.1055350.
  5. ^ a b c Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane (8 August 2008). Attacking and defending the McEliece cryptosystem. Proc. 2nd International Workshop on Post-Quantum Cryptography. Lecture Notes in Computer Science. 5299. pp. 31–46. CiteSeerX 10.1.1.139.3548. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.
  6. ^ Bernstein, Daniel J. (2010). Sendrier, Nicolas (ed.). Grover vs. McEliece (PDF). Post-quantum cryptography 2010. Lecture Notes in Computer Science. 6061. Berlin: Springer. pp. 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. MR 2776312.
  7. ^ "eBATS: ECRYPT Benchmarking of Asymmetric Systems". bench.cr.yp.to. 25 August 2018. Retrieved 1 May 2020.
  8. ^ Daniel Augot; et al. (7 September 2015). "Initial recommendations of long-term secure post-quantum systems" (PDF). PQCRYPTO: Post-Quantum Cryptography for Long-Term Security.
  9. ^ Jacques Stern (1989). A method for finding codewords of small weight. Coding Theory and Applications. Lecture Notes in Computer Science. 388. Springer Verlag. pp. 106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.

External links[edit]