Paper 2021/1045
An improvement of algorithms to solve under-defined systems of multivariate quadratic equations
, University of the RyukyusAbstract
The problem of solving a system of multivariate quadratic equations over a finite field is known to be hard in general. However, there have been several algorithms of solving the system of quadratic equations efficiently when the number of variables is sufficiently larger than the number of equations (e.g., Kipnis et al., Eurocrypt 1999, Thomae-Wolf, PKC 2012, Cheng et al., PQCrypto 2014 and Furue et al., PQCrypto 2021). In the present paper, we propose a new algorithm which is available if the number of variables is smaller than that required in the previously given algorithms. We also analyze the security of MAYO, a variant of UOV, proposed in SAC 2021 and submitted to NIST's standardization project of additional digital signature schemes for Post-Quantum Cryptography.
Note: 9 pages
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. JSIAM Letters, Vol. 15 (2023)
- Keywords
- multivariate public key cryptosystem
- Contact author(s)
- hashimoto @ math u-ryukyu ac jp
- History
- 2023-07-19: revised
- 2021-08-16: received
- See all versions
- Short URL
- https://ia.cr/2021/1045
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1045,
author = {Yasufumi Hashimoto},
title = {An improvement of algorithms to solve under-defined systems of multivariate quadratic equations},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1045},
year = {2021},
url = {https://eprint.iacr.org/2021/1045}
}
