Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / NIST, PQC, HFE, Gui, Quartz, Roots, Factorization, Traces

Date: received 9 Jan 2020, last revised 10 Jan 2020

Contact author: alexander maximov at ericsson com

Available format(s): PDF | BibTeX Citation

Version: 20200110:121112 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]