Paper 2017/595

FPGA-based Key Generator for the Niederreiter Cryptosystem using Binary Goppa Codes

Wen Wang, Jakub Szefer, and Ruben Niederhagen

Abstract

This paper presents a post-quantum secure, efficient, and tunable FPGA implementation of the key-generation algorithm for the Niederreiter cryptosystem using binary Goppa codes. Our key-generator implementation requires as few as 896,052 cycles to produce both public and private portions of a key, and can achieve an estimated frequency Fmax of over 240 MHz when synthesized for Stratix V FPGAs. To the best of our knowledge, this work is the first hardware-based implementation that works with parameters equivalent to, or exceeding, the recommended 128-bit ``post-quantum security'' level. The key generator can produce a key pair for parameters $m=13$, $t=119$, and $n=6960$ in only $3.7$ ms when no systemization failure occurs, and in $3.5 \cdot 3.7$ ms on average. To achieve such performance, we implemented an optimized and parameterized Gaussian systemizer for matrix systemization, which works for any large-sized matrix over any binary field GF$(2^m)$. Our work also presents an FPGA-based implementation of the Gao-Mateer additive FFT, which only takes about 1000 clock cycles to finish the evaluation of a degree-119 polynomial at $2^{13}$ data points. The Verilog HDL code of our key generator is parameterized and partly code-generated using Python and Sage. It can be synthesized for different parameters, not just the ones shown in this paper. We tested the design using a Sage reference implementation, iVerilog simulation, and on real FPGA hardware.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CHES 2017
Keywords
post-quantum cryptographycode-based cryptographyNiederreiter key generationFPGAhardware implementation.
Contact author(s)
wen wang ww349 @ yale edu
History
2017-10-19: last of 7 revisions
2017-06-21: received
See all versions
Short URL
https://ia.cr/2017/595
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/595,
      author = {Wen Wang and Jakub Szefer and Ruben Niederhagen},
      title = {FPGA-based Key Generator for the Niederreiter Cryptosystem using Binary Goppa Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/595},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/595}},
      url = {https://eprint.iacr.org/2017/595}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.