IEICE TRANSACTIONS on Fundamentals
Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations
Summary :
It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about) m2-2m 3/2+2m and the other is for the case of n ≥ m(m+1)/2+1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.6 pp.1257-1262
- Publication Date
- 2011/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E94.A.1257
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yasufumi HASHIMOTO, "Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 6, pp. 1257-1262, June 2011, doi: 10.1587/transfun.E94.A.1257.
Abstract: It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about) m2-2m 3/2+2m and the other is for the case of n ≥ m(m+1)/2+1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1257/_p
Copy
@ARTICLE{e94-a_6_1257,
author={Yasufumi HASHIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations},
year={2011},
volume={E94-A},
number={6},
pages={1257-1262},
abstract={It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about) m2-2m 3/2+2m and the other is for the case of n ≥ m(m+1)/2+1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.},
keywords={},
doi={10.1587/transfun.E94.A.1257},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1257
EP - 1262
AU - Yasufumi HASHIMOTO
PY - 2011
DO - 10.1587/transfun.E94.A.1257
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2011
AB - It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about) m2-2m 3/2+2m and the other is for the case of n ≥ m(m+1)/2+1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.
ER -
English
