LWE crypto in HLS on FPGA

Credits

• Timo ZIJLSTRA (CNRS, Lab-STICC, UBS - Université Bretagne Sud )
• Karim BIGOU (UBO - Université Bretagne Occidentale, Lab-STICC)
• Arnaud TISSERAND (CNRS, Lab-STICC)

General Description

In the context of the Post-Quantum Cryptography (PQC) standardisation effort launched by NIST in 2016, we implemented and optimized various hardware architectures for round-2 KEM candidates based on lattices: LWE, RLWE, MLWE using parameter sets from Frodo/NewHope/Kyber. Several variants of our architectures are available: multiple levels of parallelism for various speed/area trade-offs, various choices for the PRNG (Trivium, Shake or both), CPA and CCA secure solutions. Our FPGA implementations (on Xilinx Virtex-7 devices) have been described in C language and implemented using high-level synthesis (HLS) tools (Xilinx Vivado v2018.1). They provide better performances than most of those found in literature based on VHDL/Verilog implementations. Our codes and synthesis configuration scripts are distributed as open-source hardware under CeCILL-B license in the LWE-HLS-FPGA repository.

Supported Cryptosystems

• LWE
  • Tested for parameters including matrix sizes $k = 640, 768$ and $1344$ and moduli $q = 2^{15}$ and $2^{16}$.
  • CCA2 secure and CPA-only secure implementations.
  • Sequential and parallel architectures.
  • Using Trivium and/or SHAKE as PRNG.
• RLWE
  • For polynomial degree $n = 1024$ and modulus $q = 12289$.
  • CCA2 secure and CPA-only secure implementations.
  • Using both Trivium and SHAKE as PRNG.
• MLWE
  • For matrix sizes $k = 2, 3$ and $4$, modulus $q = 7681$ and polynomial degree $n = 256$ ($=3329$ and quadratic extension for field arithmetic is available in version 1.1).
  • CCA2 secure and CPA-only secure implementations.
  • Sequential and parallel architectures.
  • Using Trivium and both SHAKE and Trivium as PRNG.

For using our implementations, please refer to the internal documentation provided in the README file from the LWE-HLS-FPGA repository, it includes details on the commands to be used and tool configuration. Our C codes are quite generic and it should be easy to adapt or extend them to other parameters as well as to port them on other FPGAs and HLS tools. All our implementations have been intensively tested using functional simulation against mathematical values computed by Sage mathematical software.

In the case of the RLWE cryptosystem, we also provide a set of protections against side-channel attacks from the state-of-the-art, new ones and combinations: masking, blinding, shuffling, shifting. For more details, please refer to the specific folder in the global archive and reference 2).

References

The motivations, analysis of the state of the art, algorithms, security aspects, proposed architectures and implementations results are detailed in the papers:

1. Lattice-based Cryptosystems on FPGA: Parallelization and Comparison using HLS.
   By T. Zijlstra, K. Bigou, and A. Tisserand.
   IEEE Transactions on Computers, 2021.
   DOI: 10.1109/TC.2021.3112052
   PDF access

2. FPGA Implementation and Comparison of Protections against SCAs for RLWE.
   By T. Zijlstra, K. Bigou, and A. Tisserand.
   Proc. International Conference on Cryptology in India (IndoCrypt), Dec. 2019,
   DOI: 10.1007/978-3-030-35423-7_27
   PDF access

In the LWE-HLS-FPGA repository, we provide a complete bibliographic file (in bibtex format) for all references used during this work or suggested by Reviewers of our publications when space limits where too strong to add related references.

Acknowledgments

This work was partially funded by a PhD grant from PEC - DGA - Région Bretagne. We sincerely thank Xilinx for University Program donations.