1
$\begingroup$

Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.

  1. Computational syndrome decoding is hard

  2. Indistinguishability Assumption (IA): Distinguishing a code from chosen family from a random linear code is hard. (or distinguishing a public key from a random matrix of the same size.)

Now consider cryptosystems such as those based on quasi-cyclic matrices eg.BIKE, LEDAcrypt, QC-MDPC. Obviously, one can easily distinguish with high probability a quasi-cyclic matrix from a random one. So, I guess the correction version of this assumption would here be, distinguishing a random quasi-cyclic matrix to one that generates an quasi-cyclic LDPC code. Is this correct? Secondly, what are the best known algorithms for distinguishing codes that come from a family (say QC-MDPC) to random matrix (potentially restricting it to some structure as said above). In particular, can we do significantly better than brute forcing?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy