International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: High-speed Instruction-set Coprocessor for Lattice-based Key Encapsulation Mechanism: Saber in Hardware

Authors:
Sujoy Sinha Roy , University of Birmingham, United Kingdom
Andrea Basso , University of Birmingham, United Kingdom
Download:
DOI: 10.13154/tches.v2020.i4.443-466
URL: https://tches.iacr.org/index.php/TCHES/article/view/8690
Search ePrint
Search Google
Presentation: Slides
Abstract: In this paper, we present an instruction set coprocessor architecture for lattice-based cryptography and implement the module lattice-based post-quantum key encapsulation mechanism (KEM) Saber as a case study. To achieve fast computation time, the architecture is fully implemented in hardware, including CCA transformations. Since polynomial multiplication plays a performance-critical role in the module and ideal lattice-based public-key cryptography, a parallel polynomial multiplier architecture is proposed that overcomes memory access bottlenecks and results in a highly parallel yet simple and easy-to-scale design. Such multipliers can compute a full multiplication in 256 cycles, but are designed to target any area/performance trade-offs. Besides optimizing polynomial multiplication, we make important design decisions and perform architectural optimizations to reduce the overall cycle counts as well as improve resource utilization. For the module dimension 3 (security comparable to AES-192), the coprocessor computes CCA key generation, encapsulation, and decapsulation in only 5,453, 6,618 and 8,034 cycles respectively, making it the fastest hardware implementation of Saber to our knowledge. On a Xilinx UltraScale+ XCZU9EG-2FFVB1156 FPGA, the entire instruction set coprocessor architecture runs at 250 MHz clock frequency and consumes 23,686 LUTs, 9,805 FFs, and 2 BRAM tiles (including 5,113 LUTs and 3,068 FFs for the Keccak core).
Video from TCHES 2020
BibTeX
@article{tches-2020-30561,
  title={High-speed Instruction-set Coprocessor for Lattice-based Key Encapsulation Mechanism: Saber in Hardware},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2020, Issue 4},
  pages={443-466},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8690},
  doi={10.13154/tches.v2020.i4.443-466},
  author={Sujoy Sinha Roy and Andrea Basso},
  year=2020
}