Paper 2023/731
Fast Exhaustive Search for Polynomial Systems over F3
, Academia SinicaAbstract
Solving multivariate polynomial systems over finite fields is an important problem in cryptography. For random F2 low-degree systems with equally many variables and equations, enumeration is more efficient than advanced solvers for all practical problem sizes. Whether there are others remained an open problem. We here study and propose an exhaustive-search algorithm for low degrees systems over F3 which is suitable for parallelization. We implemented it on Graphic Processing Units (GPUs) and commodity CPUs. Its optimizations and differences from the F2 case are also analyzed. We can solve 30+ quadratic equations in 30 variables on an NVIDIA GeForce GTX 980 Ti in 14 minutes; a cubic system takes 36 minutes. This well outperforms existing solvers. Using these results, we compare Gröbner Bases vs. enumeration for polynomial systems over small fields as the sizes go up.
Note: Tech report which reflects the work done for Mr. Wei-Jeng Wang’s masters thesis at National Taiwan University, 2016 and intended for submission but never appear elsewhere, the author's emails are their current ones, the affiliations those at the time of the work.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- multivariatequadraticenumerationfinite field
- Contact author(s)
-
by @ crypto tw
willwang8129 @ hotmail com tw
nick yang @ chelpis com
mcs @ cht com tw
cheng @ btq li - History
- 2023-05-25: approved
- 2023-05-22: received
- See all versions
- Short URL
- https://ia.cr/2023/731
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/731,
author = {Bo-Yin Yang and Wei-Jeng Wang and Shang-Yi Yang and Char-Shin Miou and Chen-Mou Cheng},
title = {Fast Exhaustive Search for Polynomial Systems over F3},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/731},
year = {2023},
url = {https://eprint.iacr.org/2023/731}
}
