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?



Your Answer

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

Browse other questions tagged or ask your own question.