Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations

Yasufumi HASHIMOTO

doi:10.1587/transfun.E94.A.1257

Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations

Yasufumi HASHIMOTO

Full Text Views

0

Cite this

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) m²-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(2^m) or O(3^m) 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

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) m²-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(2^m) or O(3^m) 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) m²-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(2^m) or O(3^m) 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) m²-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(2^m) or O(3^m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.
ER -