More Web Proxy on the site http://driver.im/

research-article

Solving degree, last fall degree, and related invariants

Authors:

Alessio Caminata,

Elisa GorlaAuthors Info & Claims

Volume 114, Issue C

Pages 322 - 335

https://doi.org/10.1016/j.jsc.2022.05.001

Published: 01 January 2023 Publication History

Abstract

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Gröbner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo–Mumford regularity.

References

[1]

M. Bardet, Étude des systémes algébriques surdéterminés. Applications aux codes correcteurs et á la cryptographie, Ph.D. thesis Université Paris 6, 2004.

[2]

M. Bardet, J.-C. Faugère, B. Salvy, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, in: ICPPSS International Conference on Polynomial System Solving, 2004.

[3]

G. Caviglia, H.T. Hà, J. Herzog, M. Kummini, N. Terai, N.V. Trung, Depth and regularity modulo a principal ideal, J. Algebraic Comb. 49 (2019) 1–20.

[4]

Caminata, A.; Ceria, M.; Gorla, E. (2021): The complexity of solving Weil restriction systems. arXiv:2112.10506.

[5]

A. Caminata, E. Gorla, Solving multivariate polynomial systems and an invariant from commutative algebra, in: Arithmetic of Finite Fields, in: Lecture Notes in Comput. Sci., vol. 12542, Springer, Cham, 2021, pp. 3–36.

[6]

A. Caminata, E. Gorla, The Complexity of MinRank, Association for Women in Mathematics Series, vol. 24, Springer, Cham, 2021, pp. 163–169.

[7]

N. Courtois, A. Klimov, J. Patarin, A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT), in: Lecture Notes in Computer Science, vol. 1807, Springer, Bruges, Belgium, 2000, pp. 392–407.

[8]

J. Ding, J. Buchmann, M. Mohamed, W. Moahmed, R.P. Weinmann, MutantXL, in: Proceedings of the 1st International Conference on Symbolic Computation and Cryptography (SCC08), Beijing, China, LMIB, 2008, pp. 16–22.

[9]

J. Ding, A. Petzoldt, D. Schmidt, Multivariate public key cryptosystems, in: Adv. Information Security, Springer, New York, NY, 2020.

[10]

J. Ding, D. Schmidt, Solving degree and degree of regularity for polynomial systems over finite fields, in: Number Theory and Cryptography, in: Lecture Notes in Comput. Sci., vol. 8260, Springer, Heidelberg, 2013, pp. 34–49.

[11]

V. Dubois, N. Gama, The Degree of Regularity of HFE Systems, International Conference on the Theory and Application of Cryptology and Information Security, Springer, Berlin, Heidelberg, 2010.

[12]

J.C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra 139 (1999) 61–88.

[13]

J.C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC '02, New York, NY, USA, 2002, pp. 75–83.

[14]

P. Gaudry, Index calculus for Abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symb. Comput. 44 (2009) 1690–1702.

[15]

E. Gorla, D. Müller, C. Petit, Stronger bounds on the cost of computing Gröbner bases for HFE systems, J. Symb. Comput. 109 (2022) 386–398.

[16]

M.-D.A. Huang, M. Kosters, Y. Yang, S.L. Yeo, On the last fall degree of zero-dimensional Weil descent systems, J. Symb. Comput. 87 (2018) 207–226.

[17]

M.-D.A. Huang, M. Kosters, S.L. Yeo, Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP, in: Advances in Cryptology – CRYPTO 2015, Springer-Verlag, 2015, pp. 581–600.

[18]

Huang, Y.-J.; Petit, C.; Shinohara, N.; Takagi, T. (2015): On generalized first fall degree assumptions. https://eprint.iacr.org/2015/358.

[19]

D. Lazard, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, in: Computer Algebra, in: Lecture Notes in Comput. Sci., vol. 162, London, 1983, Springer, Berlin, 1983, pp. 146–156.

[20]

I. Semaev, A. Tenti, Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases, J. Algebra 565 (2021) 651–674.

[21]

A. Tenti, Sufficiently overdetermined random polynomial systems behave like semiregular ones, PhD Thesis University of Bergen, 2019, available at https://hdl.handle.net/1956/21158.

Cited By

Øygarden MFelke PRaddum H(2024)Analysis of Multivariate Encryption Schemes: Application to Dob and Journal of Cryptology10.1007/s00145-024-09501-w37:3Online publication date: 18-Apr-2024
https://dl.acm.org/doi/10.1007/s00145-024-09501-w
Steiner M(2024)The Complexity of Algebraic Algorithms for LWEAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58734-4_13(375-403)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58734-4_13
Luengo IAvendaño MCoscojuela P(2023)DME: A Full Encryption, Signature and KEM Multivariate Public Key CryptosystemPost-Quantum Cryptography10.1007/978-3-031-40003-2_14(379-402)Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-40003-2_14

Index Terms

Solving degree, last fall degree, and related invariants

Index terms have been assigned to the content through auto-classification.

Recommendations

A Pommaret bases approach to the degree of a polynomial ideal

In this paper, we study first the relationship between Pommaret bases and Hilbert series. Given a finite Pommaret basis, we derive new explicit formulas for the Hilbert series and for the degree of the ideal generated by it which exhibit more clearly ...
On the last fall degree of Weil descent polynomial systems
Abstract
Given a polynomial system F over a finite field k which is not necessarily of dimension zero, we consider the Weil descent F ′ of F over a subfield k ′. We prove a theorem which relates the last fall degrees of F 1 and F 1 ′, where the ...
Stronger bounds on the cost of computing Gröbner bases for HFE systems
Abstract
We give upper bounds for the solving degree and the last fall degree of the polynomial system associated to the HFE (Hidden Field Equations) cryptosystem. Our bounds improve the known bounds for this type of systems. We also present ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 114, Issue C

Jan 2023

376 pages

ISSN:0747-7171

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 January 2023

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Øygarden MFelke PRaddum H(2024)Analysis of Multivariate Encryption Schemes: Application to Dob and Journal of Cryptology10.1007/s00145-024-09501-w37:3Online publication date: 18-Apr-2024
https://dl.acm.org/doi/10.1007/s00145-024-09501-w
Steiner M(2024)The Complexity of Algebraic Algorithms for LWEAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58734-4_13(375-403)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58734-4_13
Luengo IAvendaño MCoscojuela P(2023)DME: A Full Encryption, Signature and KEM Multivariate Public Key CryptosystemPost-Quantum Cryptography10.1007/978-3-031-40003-2_14(379-402)Online publication date: 16-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-40003-2_14

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents