Cited By
View all- Aragon NCouvreur ADyseryn VGaborit PVinçotte A(2024)MinRank Gabidulin Encryption Scheme on Matrix CodesAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0894-2_3(68-100)Online publication date: 13-Dec-2024
Refined F5 Algorithms for Ideals of Minors of Square Matrices
Pages 270 - 279
Abstract
We consider the problem of computing a grevlex Gröbner basis for the set Fr(M) of minors of size r of an n × n matrix M of generic linear forms over a field of characteristic zero or large enough. Such sets are not regular sequences; in fact, the ideal ⟨Fr(M)⟩ cannot be generated by a regular sequence. As such, when using the general-purpose algorithm F5 to find the sought Gröbner basis, some computing time is wasted on reductions to zero. We use known results about the first syzygy module of Fr(M) to refine the F5 algorithm in order to detect more reductions to zero. In practice, our approach avoids a significant number of reductions to zero. In particular, in the case r = n − 2, we prove that our new algorithm avoids all reductions to zero, and we provide a corresponding complexity analysis which improves upon the previously known estimates.
References
[1]
K. Akin, D. A. Buchsbaum, and J. Weyman. 1981. Resolutions of determinantal ideals: The submaximal minors. Advances in Mathematics 39, 1 (1981), 1–30.
[2]
J. Baena, P. Briaud, D. Cabarcas, R. Perlner, D. Smith-Tone, and J. Verbel. 2022. Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow. In Proceedings CRYPTO 2022. Springer, Cham, 376–405.
[3]
B. Bank, M. Giusti, J. Heintz, and L. M. Pardo. 2005. Generalized polar varieties: Geometry and algorithms. J. Complexity 21, 4 (2005), 377–412.
[4]
B. Bank, M. Giusti, J. Heintz, and M. Safey El Din. 2014. Intrinsic complexity estimates in polynomial optimization. J. Complexity 30, 4 (2014), 430–443.
[5]
B. Bank, M. Giusti, J. Heintz, M. Safey El Din, and É. Schost. 2010. On the geometry of polar varieties. Appl. Algebra Engrg. Comm. Comput. 21, 1 (2010), 33–83.
[6]
I. Bannwarth and M. Safey El Din. 2015. Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets. In Proceedings ISSAC 2015. ACM, 37–44.
[7]
M. Bardet, P. Briaud, M. Bros, P. Gaborit, V. Neiger, O. Ruatta, and J.-P. Tillich. 2020. An Algebraic Attack on Rank Metric Code-Based Cryptosystems. In Proceedings EUROCRYPT 2020(LNCS, Vol. 12105). Springer.
[8]
M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner, D. Smith-Tone, J.-P. Tillich, and J. Verbel. 2020. Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. In Proceedings ASIACRYPT 2020. 507–536.
[9]
M. Bardet, J.-C. Faugère, and B. Salvy. 2015. On the complexity of the F5 Gröbner basis algorithm. J. Symbolic Comput. 70 (2015), 49–70.
[10]
M. Bardet, J.-C. Faugère, B. Salvy, and P.-J. Spaenlehauer. 2013. On the complexity of solving quadratic Boolean systems. J. Complexity 29, 1 (2013), 53–75.
[11]
J. Berthomieu, C. Eder, and M. Safey El Din. 2022. New efficient algorithms for computing Gröbner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon). (2022). https://hal.science/hal-03590430 Working paper.
[12]
W. Beullens. 2022. Breaking Rainbow Takes a Weekend on a Laptop. In Proceedings CRYPTO 2022. Springer, 464–479.
[13]
W. Bruns, A. Conca, C. Raicu, and M. Varbaro. 2022. Determinants, Gröbner bases and cohomology. Springer.
[14]
W. Bruns and U. Vetter. 1988. Determinantal Rings. Springer Berlin Heidelberg.
[15]
B. Buchberger. 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph. D. Dissertation. University of Innsbruck.
[16]
J. F. Buss, G. S. Frandsen, and J. O. Shallit. 1999. The Computational Complexity of Some Problems of Linear Algebra. J. Comput. Syst. Sci. 58, 3 (1999), 572–596.
[17]
N. T. Courtois. 2001. Efficient Zero-Knowledge Authentication Based on a Linear Algebra Problem MinRank. In Proceedings ASIACRYPT 2001. Springer, 402–421.
[18]
D. A. Cox, J. Little, and D. O’Shea. 2015. Ideals, Varieties, and Algorithms (fourth edition). Springer.
[19]
J. Ding and D. Schmidt. 2005. Rainbow, a New Multivariable Polynomial Signature Scheme. In Proceedings ACNS 2005. Springer, 164–175.
[20]
J. A. Eagon and D. G. Northcott. 1962. Ideals Defined by Matrices and a Certain Complex Associated with Them. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 269, 1337 (1962), 188–204.
[21]
C. Eder and J.-C. Faugère. 2016. A survey on signature-based algorithms for computing Gröbner basis computations. J. Symbolic Comput. (2016), 1–75.
[22]
D. Eisenbud. 1995. Commutative Algebra: with a View Toward Algebraic Geometry. Springer.
[23]
D. Eisenbud. 2005. The geometry of syzygies: A second course in commutative algebra and algebraic geometry. Vol. 229. Springer.
[24]
J.-C. Faugère. 1999. A New Efficient Algorithm for Computing Gröbner bases (F4). J. Pure Appl. Algebra 139, 1 (1999), 61–88. https://doi.org/10/bpq5dx
[25]
J.-C. Faugère. 2002. A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F5). In Proceedings ISSAC 2002. ACM, 75–83.
[26]
J.-C. Faugère, F. Levy-dit-Vehel, and L. Perret. 2008. Cryptanalysis of MinRank. In Proceedings CRYPTO 2008. Springer, 280–296.
[27]
J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. 2010. Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In Proceedings ISSAC 2010. 257–264.
[28]
J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. 2012. Critical points and Gröbner bases: the unmixed case. In Proceedings ISSAC 2012. ACM, 162–169.
[29]
J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. 2013. On the complexity of the generalized MinRank problem. J. Symbolic Comput. 55 (2013), 30–58.
[30]
M. Giusti. 1984. Some effectivity problems in polynomial ideal theory. In Proceedings EUROSAM 84. Springer, 159–171.
[31]
A. Greuet and M. Safey El Din. 2014. Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set. SIAM J. Optim. 24, 3 (2014), 1313–1343.
[32]
The FFLAS-FFPACK group. 2019. FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package (v2.4.1 ed.). http://github.com/linbox-team/fflas-ffpack.
[33]
T. H. Gulliksen and O. G. Negård. 1972. Un complexe résolvant pour certains idéaux déterminantiels. C. R. Acad. Sci. Paris 274 (1972), 16–18.
[34]
J. D. Hauenstein, M. Safey El Din, É. Schost, and T. X. Vu. 2021. Solving determinantal systems using homotopy techniques. J. Symbolic Comput. 104 (2021), 754–804.
[35]
H. Hong and M. Safey El Din. 2009. Variant real quantifier elimination: algorithm and application. In Proceedings ISSAC 2009. 183–190.
[36]
H. Hong and M. Safey El Din. 2012. Variant quantifier elimination. J. Symbolic Comput. 47, 7 (2012), 883–901.
[37]
C.-P. Jeannerod, C. Pernet, and A. Storjohann. 2013. Rank-profile revealing Gaussian elimination and the CUP matrix decomposition. J. Symbolic Comput. 56 (2013), 46–68.
[38]
A. Kipnis and A. Shamir. 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In Proceedings CRYPTO 1999. Springer, 19–30.
[39]
K. Kurano. 1989. The first syzygies of determinantal ideals. J. Algebra 124, 2 (1989), 414–436.
[40]
G. Labahn, M. Safey El Din, É. Schost, and T. X. Vu. 2021. Homotopy techniques for solving sparse column support determinantal polynomial systems. J. Complexity 66 (2021), 101557.
[41]
P. Lairez and M. Safey El Din. 2021. Computing the Dimension of Real Algebraic Sets. In Proceedings ISSAC 2021. ACM, 257–264.
[42]
A. Lascoux. 1978. Syzygies des variétés déterminantales. Adv. Math 30, 3 (1978), 202–237.
[43]
D. Lazard. 1983. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In Proceedings EUROSAM 83. Springer, 146–156.
[44]
H. P. Le and M. Safey El Din. 2021. Faster one block quantifier elimination for regular polynomial systems of equations. In Proceedings ISSAC 2021. 265–272.
[45]
Y. Ma. 1994. On The Minors Defined By A Generic Matrix. J. Symbolic Comput. 18, 6 (1994), 503–518.
[46]
J. Patarin. 1996. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In Proceedings EUROCRYPT 1996. Springer, 33–48.
[47]
M. Safey El Din and É. Schost. 2003. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In Proceedings ISSAC 2003. ACM, 224–231.
[48]
M. Safey El Din and É. Schost. 2017. A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets. J. ACM 63, 6, Article 48 (jan 2017), 37 pages. https://doi.org/10.1145/2996450
[49]
P.-J. Spaenlehauer. 2014. On the Complexity of Computing Critical Points with Gröbner Bases. SIAM J. Optim. 24, 3 (2014), 1382–1401.
[50]
A. Storjohann. 2000. Algorithms for Matrix Canonical Forms. Ph. D. Dissertation. Swiss Federal Institute of Technology – ETH.
[51]
The Sage Developers. 2022. SageMath, the Sage Mathematics Software System (Version 9.8.beta6). https://www.sagemath.org.
Recommendations
A variant of the F4 algorithm
CT-RSA'11: Proceedings of the 11th international conference on Topics in cryptology: CT-RSA 2011Algebraic cryptanalysis usually requires to find solutions of several similar polynomial systems. A standard tool to solve this problem consists of computing the Gröbner bases of the corresponding ideals, and Faugère's F4 and F5 are two well-known ...
Computing Generic Fibers of Polynomial Ideals with FGLM and Hensel Lifting
ISSAC '24: Proceedings of the 2024 International Symposium on Symbolic and Algebraic ComputationWe describe a version of the FGLM algorithm that can be used to compute generic fibers of positive-dimensional polynomial ideals. It combines the FGLM algorithm with a Hensel lifting strategy. In analogy with Hensel lifting, we show that this algorithm ...
Computing Gröbner bases of pure binomial ideals via submodules of Zn
A binomial ideal is an ideal of the polynomial ring which is generated by binomials. In a previous paper, we gave a correspondence between pure saturated binomial ideals of K[x"1,...,x"n] and submodules of Z^n and we showed that it is possible to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
567 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ISSAC 2023
ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023
July 24 - 27, 2023
Tromsø, Norway
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 41Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
Cited By
View all- Aragon NCouvreur ADyseryn VGaborit PVinçotte A(2024)MinRank Gabidulin Encryption Scheme on Matrix CodesAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0894-2_3(68-100)Online publication date: 13-Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format