Code used for McEliece cryptosystem

In the McEliece cryptosystem, is choice of the code known to the attacker? And if a structural attack succeeded and the attacker found the generator matrix of the code, how did the attacker decode the encrypted message?

• Thanks for your answer. Please excuse me for my English. You said that "the code is known (via G) ti everyone", but if G is known there is no reason to mask the code, do you agree? Commented Aug 19, 2020 at 9:35
• Hi Paul, what happens is that by the masking via permutation and matrix multiplication an equivalent code is produced, with similar properties to the original code. So the equivalent decoding problem looks like it is for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder. Commented Aug 19, 2020 at 9:38
• Ok, i agree. the attacker know exactly the matrix G, but He don't know S and P, is this true? Commented Aug 19, 2020 at 10:41
• $G$ is NOT publicly known. Commented Apr 8, 2021 at 16:14

This is a (general, mathematical) perspective which may not be useful for all readers, but I still find particularly nice. It comes via analogy with the Lattice Isomorphism Problem. This is a relatively new hardness assumption (see here, although there are two other works dealing with it I know of) that is in a certain sense a "Generalization of the McEliece Assumption" from "Codes to Lattices". I'll first describe this second part, before describing how it gives a nice mathematical characterization about what precisely the matrix $$G$$ (and $$\hat{G}$$) are.

First, a brief discussion of notation. A linear code is a subset $$C\subseteq\mathbb{F}_2^n$$ (or a subset of $$\mathbb{F}_p^n$$ more generally). One measures sizes of a linear code in terms of the Hamming metric. A similar concept is that of a lattice, which is a subset of $$\mathbb{R}^n$$, where one measures sizes in the lattice in terms of the Euclidean metric. Note that lattices $$L$$ used in cryptography are often assumed to be $$q$$-ary for some constant (that is not necessairly prime) $$q$$. This means that $$q\mathbb{Z}^n\subseteq L$$. When addiitionally $$L\subseteq\mathbb{Z}^n$$, one can draw a strong connection between the lattice $$L$$, and the $$q$$-ary code $$L\cap [0,q)^n$$. One side of this connection goes by the name of construction A. This takes a $$q$$-ary code $$C\subseteq\mathbb{Z}_q^n$$, and builds the lattice $$C + q\mathbb{Z}^n$$.

Anyway, the McEliece assumption has been generalized to lattices in terms of the lattice isomorphism problem. This problem is (roughly) as follows. Given a lattice $$L$$, one often wants to explicitly represent it via multiplication by a basis $$B$$, i.e. write any lattice point $$l =Bx$$for $$x\in\mathbb{Z}^n$$. There are two obvious ways that this is non-unique, namely

1. Given an automorphism of $$\mathbb{Z}^n$$ that we call $$U$$ (often called unimodular, or an element of $$\mathsf{SL}_n(\mathbb{Z})$$. One can equivalently view this as a "change of basis"), one can replace $$x\mapsto Ux$$, i.e. the lattice is invariant under the natural action of $$\mathsf{SL}_n(\mathbb{Z})$$ on the right, and

2. Given an orthogonal transformation $$O$$ (which one can think of as a generalized rotation), the lattice doesn't fundamentally change by rotating it on the left, i.e. $$OB\mathbb{Z}^n\approx B\mathbb{Z}^n$$ are essentially the same.

This is to say that given a basis $$B\in\mathsf{Mat}_{n\times n}(\mathbb{R})$$, it is associated with a lattice $$L\in\mathcal{L}_n$$, the space of $$n$$-dimensional lattices. The above two points can be used to argue that $$\mathcal{L}_n = O(n) \backslash \mathsf{Mat}_{n\times n}(\mathbb{R})/ \mathsf{SL}_n(\mathbb{Z})$$. This is a "double coset space", and (in short) means that changing $$B\mapsto BU$$ doesn't fundamentally change things, as well as $$B\mapsto OB$$ doesn't fundamentally change things.

What does this mean for codes? Well, one can repeat the exact same argument for codes. One gets that

1. the action on the right is still $$\mathsf{SL}_n(\mathbb{Z})$$, but
2. the action on tohe left should be by $$S_n$$. This is (roughly) because the group of matrices that preserves the norm $$\lVert\cdot\rVert_0$$ is simply permutations, while the group of matrices that preserves the norm $$\lVert\cdot\rVert_2$$ is much larger (it is $$O(n)$$, often called "the orthogonal group").

This leads to a code being described as some matrix $$G$$, up to multiplication by a unimodular matrix $$S$$ on the right, and permutation matrix $$P$$ on the left, i.e. $$\hat{G} = PGS$$ defines "the same code" as $$G$$ (note that I use the convention that encoding under a code is $$x\mapsto Gx$$. If one prefers the other notation $$\mapsto xG^t$$, you swap the "left" and "right" in the above discussion).

With this background, the McEliece cryptosystem makes public a (suitably random) representative of the equivalence class that the code $$G$$ belongs to. It does this via multiplying by a random choice of $$P$$ and $$S$$ as in the above. But fundamentally, $$\hat{G}$$ and $$G$$ are "the same code", where we say that "the same" is up to

1. a potential change of basis $$S$$, and
2. a potential "rotation" (in the Hamming norm) $$P$$.

The "seed" code is known (via $$G$$) to everyone including the attacker, but the actual code used is unknown. The seed code coordinates are permuted on the right ($$P$$) after an invertible transformation $$S$$ applied on the left, forming a trapdoor. $$S,P$$ are secret. If the permuted generator matrix is $$\hat{G}$$ we have $$\hat{G}=SGP.$$

If the attacker finds the (unpermuted) generator matrix, then they can just decode as explained in the next paragraph.

If the received ciphertext is $$c=c'\oplus e,$$ where $$e$$ is the noise vector added for security, and $$c'=m\hat{G},$$ the legitimate recipient can do $$\hat{c}=cP^{-1},$$ and can decode $$\hat{c}$$ to $$\hat{m}$$ using the standard decoding algorithm for the code. Finally she can compute $$m=\hat{m}S^{-1}.$$ You can check in a routine way this works.

Edit: To clarify where the security comes from, the masking via permutation and matrix multiplication produces an equivalent “pseudorandom” code with similar properties to the original code.

So the equivalent decoding problem looks like a decoding problem for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder.

Note that the noise added must not be beyond the correction capability of the code. If it was, the legitimate receiver might decode to the wrong codeword even with the trapdoor information or fail to decode to the correct codeword.

• $G$ is NOT known to the adversary. However, $\hat{G}$ is. Commented Apr 8, 2021 at 16:13