4
$\begingroup$

Take a McEliece cryptosystem with public generator matrix $G' = S G P$ where $G$ is a generator of a secret code with known fast decoding (not necessarily a Goppa code over $\mathbb{F}_2$), $S$ is random & non-singular and $P$ is a permutation.

Let's say an attacker Eve has a way to find $G$ from $G'$ but not $S$ or $P$. How would Eve now continue the attack on a encrypted codeword $c = mSGP+e$?

There are ways to find $P$, if you know $SG$: Support splitting algorithm, but I don't see how Eve can continue without $S$.


Clarification / Example / Thoughts from previous answers

One of the problems is, that $P$ changes the code enough already, that it will be hard to decode. This is an example over $\mathbb{F}_2$

$G:=\left( \begin{eqnarray} 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{eqnarray} \right)$ generates the code $\mathcal{C} = \mathbb{F}_2^2G= \left\{ (0,0,0,0,0),(1,1,0,0,1),(0,0,1,1,1),(1,1,1,1,0) \right\}$.
Take the permutation that switches the 2nd and 3rd component $P = (23)$.

The generator $GP$ now generates the code $\mathcal{C}P = \left\{ (0,0,0,0,0),(1,0,1,0,1),(0,1,0,1,1),(1,1,1,1,0) \right\}$.

Take a codeword in $\mathcal{C}P$: $c = (1,0,1,0,1) \in \mathcal{C}P$ and an error vector $e=(1,0,0,0,0)$.

$y=c+e=(0,0,1,0,1)$ has distance 1 to a codeword in $\mathcal{C}P$; so for someone who knows $P$ it could be translated into a codeword in $\mathcal{C}$ and decoded with $G$.

$y$ also has a distance of 1 to a codeword in $\mathcal{C}$, but to the wrong one; so simple decoding does not work.

$\endgroup$

2 Answers 2

0
$\begingroup$

After another good read through the current research papers [1, 2, 3] I'm not so sure anymore that the above stated problem does indeed have a solution, yet. I think it heavily depends on the chosen code $G$ whether it is possible to break the system; and all system breaking algorithms gave $S$ as well (or their equivalent in the Niederreiter cryptosstem).

I now do not think it is possible to retrieve $S$ given $G$ alone.

$\endgroup$
0
$\begingroup$

The stated problem is discussed in this paper, called the Scrambler-Permutation Problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.