Paper 2021/1344

Racing BIKE: Improved Polynomial Multiplication and Inversion in Hardware

Jan Richter-Brockmann, Ming-Shing Chen, Santosh Ghosh, and Tim Güneysu

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in Tches 2022
Keywords
BIKEQC-MDPCPQCReconfigurable Devices FPGA
Contact author(s)
jan richter-brockmann @ rub de
History
2021-10-14: revised
2021-10-07: received
See all versions
Short URL
https://ia.cr/2021/1344
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1344,
      author = {Jan Richter-Brockmann and Ming-Shing Chen and Santosh Ghosh and Tim Güneysu},
      title = {Racing BIKE: Improved Polynomial Multiplication and Inversion in Hardware},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1344},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1344}},
      url = {https://eprint.iacr.org/2021/1344}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.