FPGA-based Key Generator for the Niederreiter Cryptosystem Using Binary Goppa Codes
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
- PDF / 450,283 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 150 Views
2
Yale University, New Haven, CT, USA {wen.wang.ww349,jakub.szefer}@yale.edu Fraunhofer Institute SIT, Darmstadt, Germany [email protected]
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 · 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(2m ). 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 213 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. Keywords: Post-Quantum Cryptography · Code-based cryptography Niederreiter key generation · FPGA · Hardware implementation
1
·
Introduction
Once sufficiently large and efficient quantum computers can be built, they will be able to break many cryptosystems used today: Shor’s algorithm [22,23] can solve the integer-factorization problem and the discrete-logarithm problem in polynomial time, which fully breaks cryptosystems built upon the hardness of Permanent ID of this document: 503b6c5d84a7a196a4fd4ce7034b06ba. Date: 2017.06.26. c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 253–274, 2017. DOI: 10.1007/978-3-319-66787-4 13
254
Wang, Szefer, Niederhagen
these problems, e.g., RSA, ECC, and Diffie-Hellman. In addition, Grover’s algorithm [10] gives a square-root speedup on search problems and improves bruteforce attacks that check every possible key, which threatens, e.g., symmetric key ciphers like AES. However, a “simple” doubling of the key size can be used as mitigation for attacks using Grover’s algorithm. In order to provide alternatives for the cryptographic systems that are threatened by Shor’s algorithm, the cryptographic community is investigating cryptosystems that are secure against attacks by quantum computers using both Shor’s and Grover’s algorithm in a field called Post-Quantum Cryptography (PQC). Currently, there are five popular classes of PQC algorithms: ha
Data Loading...
