SD + Goppa code indistinguishability ⇒ One-wayness of McEliece encryption

Fully-black-box reduction · standard model · folklore · security loss: additive: the Goppa-distinguishing advantage plus the decoding advantage plus at most for rank-deficient matrices

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.