<p>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.</p>
<p>Here are some references on the topics you mentioned:</p>
<p><strong>Error-Correcting Codes and Cryptography:</strong></p>
<p>McEliece, R.J., &quot;A Public-Key Cryptosystem Based On Algebraic Coding Theory,&quot; DSN Progress Report, pp. 42–44, 1978. <a href="https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF" rel="nofollow noreferrer">PDF Link</a></p>
<p><strong>LDPC codes and Cryptography:</strong></p>
<p>J. Proos and C. Zalka, &quot;Shor's discrete logarithm quantum algorithm for elliptic curves,&quot; Quantum Info. Comput., vol. 3, no. 4, pp. 317–344, 2003. <a href="https://www.rintonpress.com/journals/qiconline.html#v3n4" rel="nofollow noreferrer">Link</a></p>
<p><strong>Post-Quantum Cryptography and Code-based Cryptography (like QC-MDPC):</strong></p>
<p>Bernstein, D.J., Buchmann, J., Dahmen, E. (Eds.), &quot;Post-Quantum Cryptography&quot;. Springer, Berlin, Heidelberg. 2009. <a href="https://www.springer.com/gp/book/9783540887010" rel="nofollow noreferrer">Link</a></p>

CC BY-SA 4.0
2023-06-25T08:39:05.603Z
2023-06-25T08:39:05.603Z
tomasantunes
<p>Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.</p>
<ol>
<li><p>Computational syndrome decoding is hard</p>
</li>
<li><p>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.)</p>
</li>
</ol>
<p>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?</p>

<reference-request><coding-theory><cryptography>
Code indistinguishability assumption for Code based cryptography (in special cases)
Root
# Code indistinguishability assumption for Code based cryptography (in special cases)

(Asked by: username_0 on 2022-05-12)

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?

**Tags:** reference-request, coding-theory, cryptography

---

## 1 answers

### Answer by username_1 on 2023-06-25. Score: -1

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](https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF)

**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](https://www.rintonpress.com/journals/qiconline.html#v3n4)

**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](https://www.springer.com/gp/book/9783540887010)


---

