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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/027}},
      url = {https://eprint.iacr.org/2020/027}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.