SD + Goppa code indistinguishability ⇒ One-wayness of McEliece encryption
Statement
Let be the dimension, assumed to depend only on , of the binary Goppa codes of length and degree over used by McEliece encryption — McE78. If the McEliece assumptions hold for , that is, Goppa codes are indistinguishable for and syndrome decoding is hard for , then McEliece encryption is one-way for : for all efficient there are efficient and with
— folklore.
Sketch
, given , encrypts a uniform under it and outputs iff returns , so ‘s success probabilities on a scrambled Goppa key and on a uniform matrix differ by at most . , given , if has full rank (otherwise aborts), computes a uniformly random basis of , so that is distributed as a uniform full-rank matrix, and some with , runs on for uniform , which is a uniform-key encryption of a uniform message with error , and outputs for ‘s answer ; this is whenever succeeds. The term bounds the probability that or the uniform matrix is rank-deficient.
Notes
- Plain McEliece encryption is not IND-CPA, since has weight exactly when encrypts — standard. With the plaintext padded by random bits it is IND-CPA under Goppa code indistinguishability and the pseudorandomness that LPN implies — NIKM08.
- At sufficiently high rate Goppa codes are distinguishable in polynomial time, so the theorem says nothing there — FGO+13.
- Niederreiter’s dual scheme — Nie86 — instantiated with the same binary Goppa codes is one-way under the same two hypotheses, by the same hybrid applied to its parity-check public key, which is efficiently computable from a generator matrix of the same code — folklore.