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.