TL;DR
This paper presents optimized, constant-time software implementations of the BIKE post-quantum cryptography candidate for Intel Haswell and ARM Cortex-M4 processors. The new implementations achieve significant speedups over existing versions, making BIKE more practical for a wider range of devices, including embedded systems.
What Problem Does This Paper Address?
BIKE is a promising candidate for post-quantum cryptography, but its performance, particularly on resource-constrained embedded systems, has been a concern. While existing optimizations exist for high-performance CPUs, there was a lack of efficient, constant-time implementations for architectures like ARM Cortex-M4, which lack specialized instructions for cryptographic acceleration. This paper aims to bridge this gap by developing and evaluating optimized BIKE implementations for both high-end (Intel Haswell) and embedded (ARM Cortex-M4) platforms.
Methods
The authors introduce several optimization techniques, categorized by their impact on different parts of the BIKE algorithm:
- For polynomial multiplication in R₂ (used in the decoder):
- Matrix Transposition for Circular Shifts (Haswell): A novel approach that avoids the need for a dedicated "Barrel shifter" by using matrix transpositions to rearrange data, allowing efficient circular shifts.
- Barrel Shifter with Conditional Execution (Cortex-M4): Leverages the M4's conditional execution and multiply-accumulate instructions for efficient shifting.
- Full Adders for Hamming Weight Computation: Replaces the BIKE team's half-adder approach with full adders for computing the sum of polynomial products, significantly reducing operations.
- For polynomial multiplication in R (used in key generation, encapsulation, and decapsulation):
- Bernstein's 5-way Recursive Algorithm (Haswell): Implements a more efficient recursive multiplication algorithm at the top level, combined with Karatsuba for lower levels and specialized instructions (pclmulqdq) for small degrees.
- Frobenius Additive FFT (FAFFT) (Cortex-M4): Utilizes a specialized FFT variant that fits well with bit-slicing, enabling efficient polynomial multiplication without requiring carryless multiplication instructions.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Novel Matrix Transposition for Shifts: The observation that circular shifts can be efficiently performed by rearranging data into a matrix and then shifting rows is a key algorithmic contribution, particularly for the Haswell implementation.
- Platform-Specific Optimizations: The paper demonstrates the effectiveness of tailoring optimization techniques to the specific instruction sets and architectural features of different platforms (e.g., AVX2 on Haswell vs. conditional execution on Cortex-M4).
- Performance Bottlenecks Identified: The work highlights that polynomial multiplications and circular shifts are critical performance bottlenecks in BIKE.
- Embedded Systems are Viable: The significant speedups achieved on the ARM Cortex-M4 demonstrate that BIKE can be practically implemented on embedded devices, opening up new possibilities for its deployment.
Key Results
- Haswell Implementation:
- Achieved a 1.39x speedup for decapsulation and 1.33x for overall operations on
bikel1compared to the BIKE team's AVX2 implementation.
- Achieved a 1.39x speedup for decapsulation and 1.33x for overall operations on
- Achieved a 1.5x speedup for decapsulation and 1.46x for overall operations on
bikel3. - ARM Cortex-M4 Implementation:
- Achieved more than a 2x speedup for all operations compared to the BIKE team's non-constant-time portable implementation.
- Constant-Time Guarantee: Both implementations are proven to be constant-time, crucial for security against side-channel attacks.
Limitations and Future Work
- Parameter Sets: The paper focuses on
bikel1andbikel3parameter sets and does not implement the largestbikel5set. However, the authors expect their techniques to be applicable tobikel5and newer microarchitectures. - Future Work: The authors suggest that their optimization techniques for polynomial multiplications in R could be useful for other code-based candidates like HQC. They also anticipate that the Haswell implementation techniques will be beneficial for optimizing BIKE on newer Intel architectures.
Summary updated