Optimizing BIKE for the Intel Haswell and ARM Cortex-M4

Ming-Syan Chen⋆, Tung Chou, Markus KrauszIACR 2021 · DOI

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 bikel1 compared to the BIKE team's AVX2 implementation.
  • 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 bikel1 and bikel3 parameter sets and does not implement the largest bikel5 set. However, the authors expect their techniques to be applicable to bikel5 and 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

Abstract

BIKE is a key encapsulation mechanism that entered the third round of the NIST post-quantum cryptography standardization process. This paper presents two constant-time implementations for BIKE, one tailored for the Intel Haswell and one tailored for the ARM Cortex-M4. Our Haswell implementation is much faster than the avx2 implementation written by the BIKE team: for bikel1, the level-1 parameter set, we achieve a 1.39x speedup for decapsulation (which is the slowest operation) and a 1.33x speedup for the sum of all operations. For bikel3, the level-3 parameter set, we achieve a 1.5x speedup for decapsulation and a 1.46x speedup for the sum of all operations. Our M4 implementation is more than two times faster than the non-constant-time implementation portable written by the BIKE team. The speedups are achieved by both algorithm-level and instruction-level optimizations.
BibTeX
@inproceedings{chen2021optimizing,
  author = {Ming-Syan Chen⋆ and Tung Chou and Markus Krausz},
  title = {{Optimizing BIKE for the Intel Haswell and ARM Cortex-M4}},
  booktitle = {IACR},
  year = {2021},
  doi = {10.46586/tches.v2021.i3.97-124},
}

Loading related content...

Figure