Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.
Computational syndrome decoding is hard
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?
