Abstract
Our invited presentation will give an introduction to major hardware building blocks needed to implement code-based cryptographic systems. We will present details of a modern, FPGA-based, constant-time implementation of the Niederreiter cryptosystem using binary Goppa codes, including modules for encryption, decryption, and key generation. The presentation will also include a brief summary of other existing implementations of code-based cryptographic systems and it will present research challenges for implementing such systems efficiently.
Currently, there are five promising classes of post-quantum cryptographic algorithms: hash-based, code-based, lattice-based, multivariate, and isogeny-based cryptography. Our work focuses on code-base cryptography, specifically the Niederreiter cryptosystem using binary Goppa codes. The main design challenge within code-based cryptosystems is the tension between cryptographic parameters (i.e., security level) and practical aspects, e.g., the size of keys and computation speed, resulting from the chosen parameters.
The core of the presentation will focus on the FPGA implementation of our binary Goppa code-based Niederreiter cryptosystem, including modules for encryption, decryption, and key generation [2, 3]. We will show how to make the design constant-time in order to protect against timing side-channel analysis and how to make the design fully parameterized in order to support a wide range of parameter choices for security, including binary field size, the degree of the Goppa polynomial, and the code length. The parameterized design also allows users to choose design parameters for time-area trade-offs in order to support a large variety of applications ranging from smart cards to server accelerators. For parameters that are considered to provide "128-bit post-quantum security" (i.e., the cost of an attack on a quantum computer is assumed to be at least 2 128 quantum operations), our time-optimized implementation requires 966,400 cycles for the generation of both public and private portions of a key and 14,291 cycles to decrypt a ciphertext. The time-optimized design uses only 121,806 ALMs (52% of the available logic) and 961 RAM blocks (38% of the available Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from
[email protected] '18, May 23-25, 2018, Chicago, IL, USA ©2018 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery. ACM ISBN 978-1-4503-5724-1/18/05... $15.00 https://doi.org/10.1145/3194554.3194617 memory), and results in a design that runs at about 250 MHz on a medium-size Stratix V FPGA (5SGXEA7N).
To achieve this efficient design, a number of building blocks were needed: Gaussian systemizers for matrix systemizations [1], Gao-Mateer additive FFT for polynomial evaluations, a merge-sort module for generating uniformly distributed permutations, and a constant-time Berlekamp-Massey module for decoding [2, 3]. Reasons for making these design choices will be covered in the presentation as well.
Given the increasing interest in code-based cryptography, a number of projects have been focusing on the hardware implementation of the Niederreiter cryptosystem. We will present the performance of our entire Niederreiter cryptosystem with "128-bit post-quantum security" and compare our design with other existing FPGA-based implementations. Prior works have not reached the security level of our design, and this presentation will highlight design choices which allow for achieving a high-security design, while maintaining efficiency. Our current work is the fastest design to date, beating prior FPGA work and optimized CPU-based implementations on recent processors. Based on insights from our work, the presentation will show how to design flexible hardware cores that can be easily configured for different security levels and performance targets.
