# Attack on the prime-length QC-MDPC McEliece PKC

Let the polynomial that defines the rate $n_0$ cyclic code be

$x^p+1 = (x+1)(x^{p-1}+\cdots +x+1)$

where $p$ is any number (prime or not). Consider the ciphertext from the McEliece oracle

$(c_1,c_2,\ldots,c_r)=(m\cdot g_1 + e_1, m\cdot g_2 + e_2,\ldots,m\cdot g_r + e_r).$

Taking the expression modulo $x+1$, it follows that

$c_i \bmod (x+1)=(m \bmod (x+1)) \cdot \underbrace{(g_i \bmod (x+1))}_{= w \bmod 2 \equiv 1} + e_i \bmod (x+1),$

for $1 \leq i \leq n_0$. Assume that we observe $N$ encrypted messages of the form $c_i \bmod (x+1)$, $1 \leq i \leq n_0$. Then, for fixed message $m \bmod (x+1)$, we have $n_0$ equations of the form

$\hat c = \hat m + \hat e_i$

where $\mathbf{Pr}[\hat m = 1] = \mathbf{Pr}[\hat m=0] = \frac{1}{2}$ and $\hat c$ is known. The distribution of $\hat e$ has bias $\epsilon$. We obtain the samples

$\hat c_1 + \hat m,\hat c_2 + \hat m,...,$

and from the sequence we can create a sequence of sums

$\hat c_1 + \hat c_2, \hat c_1 + \hat c_3, ...$

Using the procedure, we can collect $N(n_0-1)$ independent samples that are $\epsilon^2$-biased.

In the QC-MDPC implementation [1], the following code is used

void array_add_error(WORD *data,uint16_t length,uint16_t weight){
for(uint16_t i=weight;0<i--;){

uint16_t error=rand()%(WORD_SIZE*length);
if(error>N){
printf("out of bounds\n";);
}

uint32_t error=rand()%(N);
arraySetBit(data,error);
}
}


A McEliece oracle using the above error-generation subroutine has an error weight with even parity with probability 0.84645 and bias 0.69290, when parameters $[9600,4800]$ and $t=42$. It is a well-established fact that a binary hypothesis test requires on average

$2\ln 2 \frac{\log_2 1/\theta}{\epsilon^4 } \approx 4.32 \log_2 1/\theta$

ciphertexts to distinguish a QC-MDPC source from a random one, for some error probability $\theta$. I wrote the same function in Python, to simulate the behavior over 40000 instances. This code can be found below.

import random
even = 0
odd = 0
for i in range(0,40000):
V = [0]*4800
vikt = 0
for i in range(0,42):
j = random.randint(0,4800-1)
if V[j] != 1:
vikt = vikt+1
V[j] = 1

if (vikt % 2) == 0:
even = even + 1
else:
odd = odd + 1

print 1.0*even/(even+odd)


This is a possible weakness in the current QC-MDPC construction. A different type of error-generation procedure would solve this problem, but it requires careful study before implemented in practice.