On the last fall degree of zero-dimensional Weil descent systems

In this article we will discuss a mostly theoretical framework for solving zero-dimensional polynomial systems. Complexity bounds are obtained for solving such systems using a new parameter, called the last fall degree, which does not depend on the choice of a monomial order. The method is similar t...

Full description

Saved in:
Bibliographic Details
Main Authors: Huang, Ming-Deh A., Kosters, Michiel, Yang, Yun, Yeo, Sze Ling
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2020
Subjects:
Online Access:https://hdl.handle.net/10356/142369
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-142369
record_format dspace
spelling sg-ntu-dr.10356-1423692020-06-19T07:37:48Z On the last fall degree of zero-dimensional Weil descent systems Huang, Ming-Deh A. Kosters, Michiel Yang, Yun Yeo, Sze Ling School of Physical and Mathematical Sciences Science::Mathematics Polynomial System Gröbner Basis In this article we will discuss a mostly theoretical framework for solving zero-dimensional polynomial systems. Complexity bounds are obtained for solving such systems using a new parameter, called the last fall degree, which does not depend on the choice of a monomial order. The method is similar to certain MutantXL algorithms, but our abstract formulation has advantages. For example, we can prove that the cryptographic systems multi-HFE and HFE are insecure. More generally, let k be a finite field of cardinality qn and let k′ be the subfield of cardinality q. Let F⊂k[X0,…,Xm−1] be a finite subset generating a zero-dimensional ideal. We give an upper bound of the last fall degree of the Weil descent system of F from k to k′, which depends on q, m, the last fall degree of F, the degree of F and the number of solutions of F, but not on n. This shows that such Weil descent systems can be solved efficiently if n grows and the other parameters are fixed. In particular, one can apply these results to show a weakness in the cryptographic protocols HFE and multi-HFE. 2020-06-19T07:37:48Z 2020-06-19T07:37:48Z 2017 Journal Article Huang, M.-D. A., Kosters, M. Yang, Y., & Yeo, S. L. (2018). On the last fall degree of zero-dimensional Weil descent systems. Journal of Symbolic Computation, 87, 207-226. doi:10.1016/j.jsc.2017.08.002 0747-7171 https://hdl.handle.net/10356/142369 10.1016/j.jsc.2017.08.002 2-s2.0-85028303781 87 207 226 en Journal of Symbolic Computation © 2017 Elsevier Ltd. All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Science::Mathematics
Polynomial System
Gröbner Basis
spellingShingle Science::Mathematics
Polynomial System
Gröbner Basis
Huang, Ming-Deh A.
Kosters, Michiel
Yang, Yun
Yeo, Sze Ling
On the last fall degree of zero-dimensional Weil descent systems
description In this article we will discuss a mostly theoretical framework for solving zero-dimensional polynomial systems. Complexity bounds are obtained for solving such systems using a new parameter, called the last fall degree, which does not depend on the choice of a monomial order. The method is similar to certain MutantXL algorithms, but our abstract formulation has advantages. For example, we can prove that the cryptographic systems multi-HFE and HFE are insecure. More generally, let k be a finite field of cardinality qn and let k′ be the subfield of cardinality q. Let F⊂k[X0,…,Xm−1] be a finite subset generating a zero-dimensional ideal. We give an upper bound of the last fall degree of the Weil descent system of F from k to k′, which depends on q, m, the last fall degree of F, the degree of F and the number of solutions of F, but not on n. This shows that such Weil descent systems can be solved efficiently if n grows and the other parameters are fixed. In particular, one can apply these results to show a weakness in the cryptographic protocols HFE and multi-HFE.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Huang, Ming-Deh A.
Kosters, Michiel
Yang, Yun
Yeo, Sze Ling
format Article
author Huang, Ming-Deh A.
Kosters, Michiel
Yang, Yun
Yeo, Sze Ling
author_sort Huang, Ming-Deh A.
title On the last fall degree of zero-dimensional Weil descent systems
title_short On the last fall degree of zero-dimensional Weil descent systems
title_full On the last fall degree of zero-dimensional Weil descent systems
title_fullStr On the last fall degree of zero-dimensional Weil descent systems
title_full_unstemmed On the last fall degree of zero-dimensional Weil descent systems
title_sort on the last fall degree of zero-dimensional weil descent systems
publishDate 2020
url https://hdl.handle.net/10356/142369
_version_ 1681057521460051968