Paper 2020/027
On Roots Factorization for PQC Algorithms
Alexander Maximov
Abstract
In this paper we consider several methods for an efficient extraction of roots of a polynomial over large finite fields. The problem of computing such roots is often the performance bottleneck for some multivariate quantum-immune cryptosystems, such as HFEv-based Quartz, Gui, etc. We also discuss a number of techniques for fast computation of traces as part of the factorization process. These optimization methods could significantly improve the performance of cryptosystems where roots factorization is a part thereof.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- NISTPQCHFEGuiQuartzRootsFactorizationTraces
- Contact author(s)
- alexander maximov @ ericsson com
- History
- 2020-01-10: revised
- 2020-01-09: received
- See all versions
- Short URL
- https://ia.cr/2020/027
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/027,
author = {Alexander Maximov},
title = {On Roots Factorization for {PQC} Algorithms},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/027},
year = {2020},
url = {https://eprint.iacr.org/2020/027}
}
