Editing McEliece cryptosystem (section)

{{Short description|Asymmetric encryption algorithm developed by Robert McEliece}}
{{Use dmy dates|date=October 2020}}

In [[cryptography]], the '''McEliece cryptosystem''' is an [[asymmetric encryption]] algorithm developed in 1978 by [[Robert McEliece]].<ref name="McEliece">
{{cite journal
 |url=https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
 |last=McEliece |first=Robert J.
 |bibcode=1978DSNPR..44..114M
 |title=A Public-Key Cryptosystem Based on Algebraic Coding Theory
 |journal=DSN Progress Report
 |volume=44
 |pages=114–116
 |year=1978
}}</ref> It was the first such scheme to use [[randomized algorithm|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.<ref name="quantum-fourier">
{{cite conference
 |year=2011
 |title=McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks
 | last1=Dinh | first1=Hang
 | last2=Moore | first2=Cristopher
 | last3=Russell | first3=Alexander
 |pages=761–779
 |location=Heidelberg
 |publisher=Springer
 |mr=2874885
 |doi=10.1007/978-3-642-22792-9_43
 |editor1-first=Philip | editor1-last=Rogaway
 |series=Lecture Notes in Computer Science
 |volume=6841
 |isbn=978-3-642-22791-2
 |conference=Advances in cryptology—CRYPTO 2011
 |doi-access=free
}}</ref>

The algorithm is based on the hardness of [[decoding methods#Syndrome decoding|decoding]] a general [[linear code]] (which is known to be [[NP-hard]]<ref name="intractability">
{{cite journal
 |last1=Berlekamp |first1= Elwyn R.
 |last2=McEliece |first2=Robert J.
 |last3=Van Tilborg |first3=Henk C.A.
 |year=1978
 |title=On the Inherent Intractability of Certain Coding Problems
 |journal=IEEE Transactions on Information Theory
 |volume=IT-24
 |issue= 3
 |pages=384–386
 | doi = 10.1109/TIT.1978.1055873
 | mr = 0495180
 |url= https://authors.library.caltech.edu/5607/
}}</ref>). For a description of the private key, an [[error-correcting code]] is selected for which an efficient decoding algorithm is known, and that is able to correct <math>t</math> errors. The original algorithm uses [[binary Goppa code]]s (subfield codes of [[Algebraic geometry code|algebraic geometry 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.<ref name="Patterson">
{{cite journal
 |author=N. J. Patterson
 |year=1975
 |title=The algebraic decoding of Goppa codes
 |journal=IEEE Transactions on Information Theory
 |volume=IT-21
 |issue=2
 |pages=203–207 
 |doi=10.1109/TIT.1975.1055350
}}</ref> 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]] <math>G</math> is perturbated by two randomly selected invertible matrices <math>S</math> and <math>P</math> (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 [[decoding methods#Information set decoding|information-set decoding]] algorithms. A 2008 paper describes both an attack and a fix.<ref name="fix">
{{cite book
 |last1=Bernstein |first1=Daniel J.
 |last2=Lange |first2=Tanja|author2-link=Tanja Lange
 |last3=Peters |first3=Christiane
 |title=Post-Quantum Cryptography
 |chapter=Attacking and Defending the McEliece Cryptosystem
 |date=8 August 2008
 |series=Lecture Notes in Computer Science
 |volume=5299 |pages=31–46
 |doi=10.1007/978-3-540-88403-3_3
 |url=https://eprint.iacr.org/2008/318
 |isbn=978-3-540-88402-6
 |citeseerx=10.1.1.139.3548
}}</ref> Another paper shows that for [[quantum computing]], key sizes must be increased by a factor of four due to improvements in information set decoding.<ref>
{{cite conference
 |first=Daniel J. | last=Bernstein
 |year=2010
 |title=Grover vs. McEliece
 |url=https://cr.yp.to/codes/grovercode-20091123.pdf
 |publisher=Springer
 |location=Berlin
 |series=Lecture Notes in Computer Science
 |volume=6061
 |conference=Post-quantum cryptography 2010
 |mr=2776312
 |pages=73–80
 |doi=10.1007/978-3-642-12929-2_6
 |editor1-first=Nicolas | editor1-last=Sendrier
 |isbn=978-3-642-12928-5
}}</ref>

The McEliece cryptosystem has some advantages over, for example, [[RSA (algorithm)|RSA]]. The encryption and decryption are faster.<ref>
{{cite web
 | url=https://bench.cr.yp.to/ebats.html
 | title=eBATS: ECRYPT Benchmarking of Asymmetric Systems
 | date=2018-08-25
 | website=bench.cr.yp.to
 | access-date=2020-05-01
}}</ref> For a long time, it was thought that McEliece could not be used to produce [[Digital signature|signatures]]. However, a signature scheme can be constructed based on the [[Niederreiter cryptosystem|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.