International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Racing BIKE: Improved Polynomial Multiplication and Inversion in Hardware

Authors:
Jan Richter-Brockmann , Ruhr-Universität Bochum, Horst-Görtz Institute for IT-Security, Bochum, Germany; Security and Privacy Research, Intel Labs, Intel Coorperation, Hillsboro, Oregon
Ming-Shing Chen , Ruhr-Universität Bochum, Horst-Görtz Institute for IT-Security, Bochum, Germany
Santosh Ghosh , Security and Privacy Research, Intel Labs, Intel Coorperation, Hillsboro, Oregon
Tim Güneysu , Ruhr-Universität Bochum, Horst-Görtz Institute for IT-Security, Bochum, Germany; DFKI, Bremen, Germany
Download:
DOI: 10.46586/tches.v2022.i1.557-588
URL: https://tches.iacr.org/index.php/TCHES/article/view/9307
Search ePrint
Search Google
Abstract: BIKE is a Key Encapsulation Mechanism selected as an alternate candidate in NIST’s PQC standardization process, in which performance plays a significant role in the third round. This paper presents FPGA implementations of BIKE with the best area-time performance reported in literature. We optimize two key arithmetic operations, which are the sparse polynomial multiplication and the polynomial inversion. Our sparse multiplier achieves time-constancy for sparse polynomials of indefinite Hamming weight used in BIKE’s encapsulation. The polynomial inversion is based on the extended Euclidean algorithm, which is unprecedented in current BIKE implementations. Our optimized design results in a 5.5 times faster key generation compared to previous implementations based on Fermat’s little theorem.Besides the arithmetic optimizations, we present a united hardware design of BIKE with shared resources and shared sub-modules among KEM functionalities. On Xilinx Artix-7 FPGAs, our light-weight implementation consumes only 3 777 slices and performs a key generation, encapsulation, and decapsulation in 3 797 μs, 443 μs, and 6 896 μs, respectively. Our high-speed design requires 7 332 slices and performs the three KEM operations in 1 672 μs, 132 μs, and 1 892 μs, respectively.
BibTeX
@article{tches-2021-31660,
  title={Racing BIKE: Improved Polynomial Multiplication and Inversion in Hardware},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 1},
  pages={557-588},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9307},
  doi={10.46586/tches.v2022.i1.557-588},
  author={Jan Richter-Brockmann and Ming-Shing Chen and Santosh Ghosh and Tim Güneysu},
  year=2021
}