Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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