On the computational hardness of the code equivalence problem in cryptography

Alessandro Barenghi; Jean-François Biasse; Edoardo Persichetti; Paolo Santini

doi:10.3934/amc.2022064

Article Contents

2023, Volume 17, Issue 1: 23-55. Doi: 10.3934/amc.2022064

This issue Previous Article Convolutional codes over finite chain rings, MDP codes and their characterization Next Article Minimal codewords arising from the incidence of points and hyperplanes in projective spaces

On the computational hardness of the code equivalence problem in cryptography

1.
Department of Electronics and Information, Politecnico di Milano
2.
Department of Mathematics and Statistics, University of South Florida
3.
Department of Mathematical Sciences, Florida Atlantic University
4.
Department of Information Engineering, Università Politecnica delle Marche

Received: August 2021

Revised: June 2022

Early access: August 2022

Published: December 2022

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

Abstract / Introduction Full Text(HTML) Figure(6) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 11T71, 94A60.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. Comparison between several methods to solve LEP

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

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 $

| Show Table

DownLoad: CSV

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'' $
$ (n, k, q) $	$ (L', w', w) $	th.	emp.	th.	emp.	th.	emp.
$ (40 , 20 , 7) $	$ (10, 12, 19) $	7.55	7.30	1.30	0.43	3.20	2.57
$ (40 , 20 , 7) $	$ (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 $
$ ( 30, 10, 13) $	$ (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
$ ( 30, 10, 19) $	$ (50, 17, 24) $	341.36	343.15	5.82	4.70	1.11	1.30

| Show Table

DownLoad: CSV

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} $

| Show Table

DownLoad: CSV

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\| $
$ (n, k, q) $	$ w $	$ L $	th.	emp.	th.	emp.	th.	emp.
$ (50, 25, 5) $	13	12	7.2	8.2	$ 1.2 $	3.3	8.4	11.5
$ (50, 25, 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
$ (40, 10, 11) $	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
$ (40, 10, 23) $	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
$ (30, 10, 31) $	9	200	3.5	4.5	$ 3.1\cdot 10^{-2} $	0	3.5	4.5

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.