Let the polynomial that defines the rate cyclic code be

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

Taking the expression modulo , it follows that

for . Assume that we observe encrypted messages of the form , . Then, for fixed message , we have equations of the form

where and is known. The distribution of has bias . We obtain the samples

and from the sequence we can create a sequence of sums

Using the procedure, we can collect independent samples that are -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 and . It is a well-established fact that a binary hypothesis test requires on average

ciphertexts to distinguish a QC-MDPC source from a random one, for some error probability . 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/

### Like this:

Like Loading...