Code indistinguishability assumption for Code based cryptography (in special cases)

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?

Even though a quasi-cyclic matrix can be distinguished from a random one, what we're really concerned about is distinguishing a specific structured quasi-cyclic matrix (that generates a low-density parity-check code, LDPC) from a random quasi-cyclic matrix. This is a more accurate interpretation of the IA in this context. The structure inherent in these specific matrices is what provides security.

Here are some references on the topics you mentioned:

Error-Correcting Codes and Cryptography:

McEliece, R.J., "A Public-Key Cryptosystem Based On Algebraic Coding Theory," DSN Progress Report, pp. 42–44, 1978. PDF Link

LDPC codes and Cryptography:

J. Proos and C. Zalka, "Shor's discrete logarithm quantum algorithm for elliptic curves," Quantum Info. Comput., vol. 3, no. 4, pp. 317–344, 2003. Link

Post-Quantum Cryptography and Code-based Cryptography (like QC-MDPC):

Bernstein, D.J., Buchmann, J., Dahmen, E. (Eds.), "Post-Quantum Cryptography". Springer, Berlin, Heidelberg. 2009. Link