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.

[1] http://www.sha.rub.de/research/projects/code/

grocid.net

scribbles from past, present and possibly future

Attack on the prime-length QC-MDPC McEliece PKC

Leave a Reply Cancel reply

Menu

grocid.net

scribbles from past, present and possibly future

Share this:

Like this:

Leave a Reply Cancel reply

Menu