Syndrome decoding

The syndrome decoding (SD) assumption states that, given a uniformly random parity-check matrix and the syndrome of a uniformly random vector of Hamming weight , no efficient algorithm finds a weight- vector with that syndrome.

Assumption

The assumption is parameterized by a code length , a dimension (rate ), and an error weight . The parameters are computable in time , with . Write for the Hamming weight and . The kernel of is a random binary linear code of length and, except with probability at most , dimension ; finding from is decoding for any codeword of that code — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sd}}_{n,k,w,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{H} \getsr \FF_2^{(n-k) \times n}$; $\mathbf{e} \getsr S_{n,w}$
\State $\mathbf{y} := \mathbf{H}\mathbf{e}$
\State $\mathbf{e}' \gets \calA(1^\secpar, \mathbf{H}, \mathbf{y})$
\Return $[\mathbf{e}' \in S_{n,w} \wedge \mathbf{H}\mathbf{e}' = \mathbf{y}]$
\end{algorithmic}
\end{algorithm}

SD is hard for if for all efficient ,

is negligible. The adversary wins with any weight- solution. Over , each weight- vector other than has syndrome with probability , so has weight- preimages in expectation: the solution is unique with high probability when , below the Gilbert–Varshamov bound, and has many weight- preimages when — standard. Two regimes are in use: linear in , and sublinear , as in McEliece encryption below — standard.

Known Results

Worst-case hardness

The decision problem — given , and , is there with and — is NP-complete, as is deciding, given and , whether some has and — BMvT78.

Relation to LPN

samples of LPN in dimension with noise rate are a noisy codeword of the random code spanned by the columns of . Multiplying by a parity-check matrix of that code () maps it to the syndrome , so search LPN is syndrome decoding with length , dimension , and Bernoulli noise in place of fixed-weight noise — standard. Conditioned on , Bernoulli noise is uniform on — standard.

Constructions

Variations

Syndrome decoding at the FS96 parameters

SD is hard at the FS96 parameters if SD is hard for the family of parameters for which FS96 prove their generator pseudorandom. Each such parameter satisfies , below the Gilbert–Varshamov bound, since otherwise the generator does not stretch — standard. The node is narrower than that inequality: whether FS96’s theorem covers every parameter satisfying it is not recorded here.

Goppa code indistinguishability

A binary Goppa code is given by a support of distinct elements of and an irreducible polynomial of degree ; it has dimension and an efficient decoder correcting errors — standard. McEliece key generation samples such a code with generator matrix , an invertible and an permutation matrix , and publishes — McE78. The assumption states that is indistinguishable from a uniform matrix. The parameters are computable in time , with and .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{goppa}}_{n,m,t,\calA}(\secpar)$}
\begin{algorithmic}
\State Sample $\mathbf{G}, \mathbf{S}, \mathbf{P}$ as in McEliece key generation
\State $\hat{\mathbf{G}}_0 := \mathbf{S}\mathbf{G}\mathbf{P}$; $\hat{\mathbf{G}}_1 \getsr \FF_2^{k \times n}$
\State $b \getsr \bits$
\State $b' \gets \calA(1^\secpar, \hat{\mathbf{G}}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

Goppa codes are indistinguishable for if for all efficient ,

is negligible. The CFS signature scheme uses binary Goppa codes of high rate — CFS01. Goppa code indistinguishability is false at sufficiently high rate (Attacks) — FGO+13.

McEliece assumptions

The parameters are computable in time , with and , as in Goppa code indistinguishability. Let be the dimension of the binary Goppa codes that McEliece key generation samples — McE78 — assumed to depend only on , and so computable in time by running key generation. The McEliece assumptions hold for if Goppa codes are indistinguishable for and SD is hard for .

One-wayness of McEliece encryption

McEliece encryption maps to for ; the key holder decodes with the Goppa decoder and multiplies by — McE78. One-wayness asks to recover a uniform from . The parameters are computable in time , with and .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{mce\text{-}ow}}_{n,m,t,\calA}(\secpar)$}
\begin{algorithmic}
\State Sample $\mathbf{G}, \mathbf{S}, \mathbf{P}$ as in McEliece key generation; $\hat{\mathbf{G}} := \mathbf{S}\mathbf{G}\mathbf{P}$
\State $\mathbf{m} \getsr \FF_2^k$; $\mathbf{e} \getsr S_{n,t}$
\State $\mathbf{c} := \mathbf{m}\hat{\mathbf{G}} + \mathbf{e}$
\State $\hat{\mathbf{m}} \gets \calA(1^\secpar, \hat{\mathbf{G}}, \mathbf{c})$
\Return $[\hat{\mathbf{m}} = \mathbf{m}]$
\end{algorithmic}
\end{algorithm}

McEliece encryption is one-way for if for all efficient ,

is negligible.

The scheme is not IND-CPA: a Goppa code correcting errors has minimum distance at least , so has weight if and only if encrypts — standard. Niederreiter’s dual scheme publishes a scrambled parity-check matrix and encrypts a message encoded as to — Nie86; inverting it on a uniform is SD — standard.

Attacks

  • Information-set decoding. Prange’s algorithm picks a random set of coordinates with invertible and outputs on and elsewhere — Pra62. It succeeds when is supported on , with probability per trial — standard. Stern’s variant allows a few errors on the complementary information set, split in two halves and matched by a birthday collision — Ste88. Representation techniques bring information-set decoding to time for half-distance decoding — BJMM12.
  • Distinguishing high-rate Goppa codes. There is a polynomial-time distinguisher for alternant and Goppa codes of sufficiently high rate over any field; it distinguishes the public keys of the CFS signature scheme for all parameters considered secure, and some McEliece parameters — FGO+13. It refutes Goppa code indistinguishability at those rates only, and is a distinguisher, not a key-recovery or decryption attack — FGO+13.

Participates in

Builds on Syndrome decoding

Produces Syndrome decoding