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/