CryptoDB
FPGA-based Key Generator for the Niederreiter Cryptosystem Using Binary Goppa Codes
| Authors: | |
|---|---|
| Download: | |
| Conference: | CHES 2017 |
| 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 $$\text {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. |
BibTeX
@inproceedings{ches-2017-28920,
title={FPGA-based Key Generator for the Niederreiter Cryptosystem Using Binary Goppa Codes},
booktitle={Cryptographic Hardware and Embedded Systems – CHES 2017},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10529},
pages={253-274},
doi={10.1007/978-3-319-66787-4_13},
author={Wen Wang and Jakub Szefer and Ruben Niederhagen},
year=2017
}