TL;DR
This paper introduces MQsoft, a C library designed to accelerate HFE-based multivariate signature schemes, crucial for post-quantum cryptography. By optimizing core operations like polynomial arithmetic and root finding using modern CPU instructions (AVX2), MQsoft achieves significant speedups (up to 19x for key generation) over existing implementations, making these promising cryptographic candidates more practical.
What Problem Does This Paper Address?
The advent of quantum computers poses a threat to current public-key cryptography. The National Institute of Standards and Technology (NIST) is leading a process to standardize post-quantum cryptography (PQC) algorithms. Among the candidates, multivariate cryptography, particularly HFE-based schemes, is well-represented in the signature category. However, the efficiency of these schemes heavily relies on their software implementations. Existing libraries often lack optimizations for sparse polynomials or constant-time execution, making them vulnerable to timing attacks and slower than necessary. This paper addresses the need for efficient, secure, and practical software implementations of these PQC signature schemes.
Methods
The core contribution is the MQsoft library, implemented in C and targeting Intel 64-bit processors with AVX2 instructions. Key optimizations include:
- Constant-time Arithmetic in F₂ⁿ: MQsoft provides optimized arithmetic operations (multiplication, squaring, modular reduction, inversion) in finite fields F₂ⁿ. It leverages Intel's PCLMULQDQ instruction for fast multiplication and vector instructions (SSE2, AVX2) for accelerated modular reduction. The library allows for specialized field implementations by choosing the irreducible polynomial at compile time.
- Optimized Root Finding: The signature generation in HFE schemes requires finding roots of a specific type of polynomial. MQsoft improves Berlekamp's algorithm by exploiting the sparse structure of HFE polynomials, leading to a significant speedup.
- Efficient Evaluation of Multivariate Quadratic Systems: For signature verification, evaluating these systems is critical. MQsoft uses a "monomial representation" and vectorized instructions (AVX2) to achieve new speed records for both constant-time and variable-time evaluations.
- Protection Against Timing Attacks: A significant portion of the MQsoft implementation is designed to be constant-time, mitigating vulnerabilities to timing attacks.
Datasets
Not discussed in the paper. The paper focuses on algorithmic optimizations and performance benchmarks rather than training on datasets.
Key Insights and Ideas
- Vectorization is Key for PQC Performance: The paper strongly demonstrates that leveraging modern CPU vector instructions (AVX2, PCLMULQDQ) is crucial for achieving practical performance in post-quantum cryptography, especially for finite field arithmetic.
- Exploiting Sparsity for HFE Schemes: The sparse nature of HFE polynomials, particularly in root-finding and modular reduction, is a critical property that can be exploited for significant performance gains, going beyond generic polynomial arithmetic.
- Constant-Time Implementation is Achievable and Necessary: MQsoft shows that it's possible to implement complex cryptographic operations in constant-time, which is essential for security against side-channel attacks, without sacrificing too much performance.
- Trade-offs in Parameter Choices: The paper highlights how different parameter choices (e.g., degree of polynomials, number of equations) in schemes like Gui and GeMSS impact performance, influencing the choice between trinomials and pentanomials for field representation.
Key Results
MQsoft achieves substantial speedups compared to existing implementations and NIST submissions:
- Key Generation: Speedups of 2x to 19x for GeMSS and Gui.
- Signature Generation: Speedups of 1.2x to 2.5x for GeMSS and Gui.
- Signature Verification: Speedups of 1.6x to 2x for GeMSS and Gui.
- F₂ⁿ Arithmetic: MQsoft's arithmetic in F₂ⁿ is up to 4 times faster than the NTL library.
- DualModeMS: MQsoft provides a 1.33x to 1.43x speedup for DualModeMS on Haswell and Skylake processors, respectively.
Limitations and Future Work
The authors acknowledge several limitations and suggest future work:
- Keypair Generation Not Fully Vectorized: The multiplication by the matrix S in keypair generation is not yet vectorized.
- GCD is Variable-Time: The GCD computation is implemented in variable-time due to the variable number of iterations.
- Security Analysis of Sparsity Exploitation: While exploiting sparsity in HFE polynomials for performance is shown, the security implications of removing certain terms need further in-depth study.
- Constant-Time Gaussian Elimination: The library does not yet implement constant-time Gaussian elimination for generating random invertible matrices, which is needed for full protection against timing attacks.
- Further Optimization: The paper suggests that MQsoft can be further improved by optimizing the generation of keypair generation and exploring trade-offs between security and performance.
Summary updated