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/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s