Article Contents
Article Contents

# On the computational hardness of the code equivalence problem in cryptography

Jean-Francois Biasse is supported by NIST grant 60NANB17D184 and NSF grant 183980; Edoardo Persichetti is supported by NSF grant 1906360

• Code equivalence is a well-known concept in coding theory. Recently, literature saw an increased interest in this notion, due to the introduction of protocols based on the hardness of finding the equivalence between two linear codes. In this paper, we analyze the security of code equivalence, with a special focus on the hardest instances, in the interest of cryptographic usage. Our work stems from a thorough review of existing literature, identifies the various types of solvers for the problem, and provides a precise complexity analysis, where previously absent. Furthermore, we are able to improve on the state of the art, providing more efficient algorithm variations, for which we include numerical simulation data. In the end, the goal of this paper is to provide a complete, single point of access, which can be used as a tool for designing schemes that rely on the code equivalence problem.

Mathematics Subject Classification: 11T71, 94A60.

 Citation:

• Figure 1.  Example of computation of ${\sf{Lex}}^{(2)}$ starting from generator matrices of two-dimensional subcodes with support size $w$. White-filled rectangles denote portions of the matrix that contain only zeros, while grey-filled rectangles indicate all-zeros sub-rows

Figure 2.  Cost of finding a subcode with support size $w$. All the considered codes have $q = 29$ and $n = 250$

Figure 3.  Comparison between several methods to solve LEP

Figure 4.  Example of lexicograph ordering, for the finite field with $q = 5$ elements and a vector $\boldsymbol a = (0, 3, 2, 0, 0, 3, 3, 2, 4, 1)$, for which ${\sf{Lex}}( \boldsymbol a) = 2 \boldsymbol a$. Figure (A) shows the multisets of entries for all scalar multiples of $\boldsymbol a$, while figure (B) reports the lexicographic order of such multisets

Figure 5.  Success probability of the probabilistic permutation recovery as a function of $L$, for codes with different parameters. For every configuration, we have tested the attack on $50$ codes. The empirical success probability has been computed by averaging over the trials

Figure 6.  Example of lexicographic ordering of a basis, for the finite field with $q = 5$ elements. In figure (A) we show the initial basis, while in the other figures we detail the steps we perform to find the corresponding lexicographic minimum. The matrix in figure (B) is obtained by scaling all columns so that the entry in the first row is a $1$. To obtain the matrix in figure (C), we sort the columns. Finally, we see that we have some degrees of freedom, since the third and fourth columns have a zero in the first row and a non null entry in the second row. Hence, we scale these columns and finally obtain the minimum lexicograph basis as in figure (D)

Table 1.  Notation used in this document

 $a$ a scalar $A$ a set $\boldsymbol a$ a vector $\boldsymbol{A}$ a matrix ${\sf{a}}$ a function or relation $\cal{A}$ an algorithm $\boldsymbol {I}_n$ the $n\times n$ identity matrix $[a;b]$ the set of integers $\{a, a+1, \dots, b\}$ $\mathbb{U}(A)$ the uniform distribution over the set $A$ $\stackrel{＄}{\leftarrow} A$ sampling uniformly at random from $A$

Table 2.  Comparison between numerical results and theoretical estimates on the composition of the list $P$ obtained with Algorithm 3. For each triplet $(n, k, q)$, the empirical results have been averaged over 100 random codes

 $(n, k, q)$ $(L', w', w)$ Num subcodes $M'$ $M''$ th. emp. th. emp. th. emp. $(40 , 20 , 7)$ $(10, 12, 19)$ 7.55 7.30 1.30 0.43 3.20 2.57 $(100, 13, 20)$ 626.86 614.00 58.76 59.40 18558.74 15016.60 $( 30, 10, 13)$ $(11, 15, 21)$ 8.88 8.37 10.77 7.98 $0.036$ $0.02$ $(40, 16, 24)$ 207.30 208.32 24.48 24.78 25.42 26.22 $( 30, 10, 19)$ $(25, 16, 24)$ 79.73 82.06 76.20 78.56 0.22 0.44 $(50, 17, 24)$ 341.36 343.15 5.82 4.70 1.11 1.30

Table 3.  Optimal setting and resulting complexity for our algorithm to solve LEP. All the considered codes have $n = 200$, $k = 100$

 $q$ $L'$ $w'$ $w$ Cost 11 13 56 97 $2^{83.76}$ 53 $183$ 62 111 $2^{105.34}$ 103 $8.83\cdot 10^7$ 80 124 $2^{111.90}$ 151 $5.57\cdot 10^9$ 83 128 $2^{114.19}$ 199 $4.48\cdot 10^{12}$ 86 126 $2^{115.17}$ 251 $3.39\cdot 10^{14}$ 88 127 $2^{115.78}$

Table 4.  Comparison between numerical results and theoretical estimates on the composition of list $P$. For each triplet $(n, k, q)$, the empirical results have been averaged over 10 random codes

 $(n, k, q)$ $w$ $L$ $M'$ $M''$ $|P|$ th. emp. th. emp. th. emp. $(50, 25, 5)$ 13 12 7.2 8.2 $1.2$ 3.3 8.4 11.5 14 100 47.3 47.6 71.1 268.9 118.4 316.5 $(40, 10, 11)$ 23 40 31.5 31.0 $7.78\cdot 10^{-4}$ 0 31.5 31 24 145 58.4 58.2 $7.4\cdot 10^{-3}$ 0.1 58.3 58.3 $(40, 10, 23)$ 26 250 52.7 54.2 $1.9\cdot 10^{-7}$ 0 52.7 54.2 28 2000 28.9 29.1 $3.9\cdot 10^{-6}$ 0 28.9 29.1 $(30, 10, 31)$ 8 90 51.9 51.9 $2.9\cdot 10^{-2}$ 0 51.9 51.9 9 200 3.5 4.5 $3.1\cdot 10^{-2}$ 0 3.5 4.5
•  [1] M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. von Maurich, R. Misoczki, R. Niederhagen, K. G. Paterson, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson and W. Wang, Classic McEliece: Conservative code-based cryptography, https://classic.mceliece.org/. [2] N. Aragon, P. S. L. M. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Güneysu, C. A. Melchor, R. Misoczki, E. Persichetti, N. Sendrier, J.-P. Tillich, V. Vasseur and G. Zémor, BIKE: Bit flipping key encapsulation, NIST Post-Quantum Standardization, 3rd Round, https://bikesuite.org/. [3] L. Babai, Graph isomorphism in quasipolynomial time, STOC'16-Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, (2016), 684–697, http://arXiv.org/abs/1512.03547. doi: 10.1145/2897518.2897542. [4] M. Baldi, A. Barenghi, F. Chiaraluce, G. Pelosi and P. Santini, A finite regime analysis of information set decoding algorithms, Algorithms, 12, (2019), Paper No. 209, 34 pp, https://www.mdpi.com/1999-4893/12/10/209. doi: 10.3390/a12100209. [5] M. Bardet, A. Otmani and M. Saeed-Taha, Permutation code equivalence is not harder than graph isomorphism when hulls are trivial, IEEE ISIT 2019, (2019), 2464–2468. [6] A. Barenghi, J.-F. Biasse, E. Persichetti, T. Ngo and P. Santini, Advanced signature functionalities from the code equivalence problem, International Journal of Computer Mathematics: Computer Systems Theory, (2022), 112–128. [7] A. Barenghi, J.-F. Biasse, E. Persichetti and P. Santini, LESS-FM: Fine-tuning signatures from the code equivalence problem, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 12841 (2021), 23-43.  doi: 10.1007/978-3-030-81293-5_2. [8] W. Beullens, Not enough LESS: An improved algorithm for solving code equivalence problems over $\mathbb{F}_q$, Selected Areas in Cryptography, Lecture Notes in Comput. Sci., Springer, Cham, 12804 (2021), 387-403.  doi: 10.1007/978-3-030-81652-0_15. [9] J.-F. Biasse, G. Micheli, E. Persichetti and P. Santini, LESS is more: Code-based signatures without syndromes, Progress in Cryptology—AFRICACRYPT 2020, Lecture Notes in Comput. Sci., Springer, Cham, 12174 (2020), 45-65.  doi: 10.1007/978-3-030-51938-4_3. [10] A. Couvreur, T. Debris-Alazard and P. Gaborit, On the hardness of code equivalence problems in rank metric, arXiv preprint, arXiv: 2011.04611. [11] T. Feulner, The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes, Adv. Math. Commun., 3 (2009), 363-383.  doi: 10.3934/amc.2009.3.363. [12] A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO '86, Lecture Notes in Comput. Sci., Springer, Berlin, 263 (1986), 186-194.  doi: 10.1007/3-540-47721-7_12. [13] J. S. Leon, Computing automorphism groups of error-correcting codes, IEEE Trans. Inform. Theory, 28 (1982), 496-511.  doi: 10.1109/TIT.1982.1056498. [14] C. A. Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J.-C. Deneuville, I.-S. Arnaud Dion, P. Gaborit, J. Lacan, E. Persichetti, J.-M. Robert, P. Véron and G. Zémor, HQC: Hamming Quasi-Cyclic, NIST Post-Quantum Standardization, 3rd Round, http://pqc-hqc.org/. [15] C. Peters, Information-set decoding for linear codes over $\mathbb{F}_q$, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 6061 (2010), 81-94.  doi: 10.1007/978-3-642-12929-2_7. [16] E. Petrank and R. M. Roth, Is code equivalence easy to decide?, IEEE Trans. Inform. Theory, 43 (1997), 1602-1604.  doi: 10.1109/18.623157. [17] M. A. Saeed, PhD Thesis. [18] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory, 46 (2000), 1193-1203.  doi: 10.1109/18.850662. [19] N. Sendrier, On the dimension of the hull, SIAM J. Discrete Math., 10 (1997), 282-293.  doi: 10.1137/S0895480195294027.

Figures(6)

Tables(4)