Toward Practical Code-Based Cryptography
Paulo Barreto
Code-based crypto is one of the main families of proposed post-quantum schemes. This introductory-level talk will provide a simple survey of the core concepts underlying code-based crypto, with a focus on recent efforts to make the essential security services it supports practical (and secure).
LEDAkem and LEDApkc: key encapsulation and public-key cryptography based on QC-LDPC codes
Paolo Santini
Decoding QC-MDPC Codes
Valentin Vasseur
Quasi-cyclic moderate density parity check codes were introduced in cryptography. They allow the design of a McEliece-like public-key encryption scheme with compact keys and a security which provably reduces to hard decoding problems for quasi-cyclic codes. In particular, QC-MDPC are among the most promising code-based key encapsulation mechanisms (KEM) that are proposed to the NIST call for standardization of quantum safe cryptography. Current schemes use a bit flipping decoder as for LDPC codes, which suffers from a small, but not negligible, decoding failure rate (DFR in the order of 10^7). This allows a key recovery attack which exploits a small correlation between the faulty error patterns and the secret key of the scheme. This limits the usage of the scheme to KEMs using ephemeral public keys. This is enough for the interactive establishment of secure communications (e.g. TLS), but makes dangerous the use static public keys for asynchronous applications (e.g. email). Understanding and improving the decoding of QC-MDPC is thus of interest for cryptographic applications. In particular, reducing the failure rate would allow static keys and increase the applicability of the mentioned cryptosystems. Here we make a first attempt in that direction. The bit flipping decoding is iterative by essence. Its purpose is to reduce the error pattern weight by flipping one bit at a time, with the hope to take more good decisions than bad ones. We introduce two new ways to apply the bit flipping: the step-by-step decoding and the use of grey positions. The former is very efficient, but only when the error weight is small, the latter allows to efficiently initiate the decoding process. Combining the two techniques outperforms the traditional bit flipping algorithm by several orders of magnitude. We also provide an analysis of the new techniques which allows us to give partial results on the failure rate of this new algorithm.
A new framework for code-based encryption and more
Jean-Cristophe Deneuville
Most code-based public key encryption schemes are secure under the assumption that the family of codes being used is indistinguishable from random linear codes. This line of work (initiated by McEliece in 1978) has often lead to practical attacks recovering the hidden structure of the public key. Additionally, this approach encrypts messages by adding random noise of controlled weighted, but this can lead to decryption failure whose probability is hard to estimate. Such failures might be turned into practical attacks too.In this talk, I will present a new framework for building efficient code-based public key encryption schemes. Such a scheme features a decryption algorithm that does not rely on the knowledge of an efficient decoding algorithm that would use the inner structure of the family of codes being used. The scheme is based on the difficulty of decoding random quasi-cyclic codes, and can be tuned to feature arbitrarily small decryption failure probability (or even null probability for Rank metric!). For Hamming metric, I will present an instantiation named HQC and its applications to key-exchange based on QC-MDPC.
IND-CCA Secure Hybrid Encryption in the Quantum Random Oracle Model Using KEMs
Angela Robinson
Hybrid encryption schemes provide fast symmetric encryption under a shared key that is generated using public key encryption techniques. Key encapsulation mechanisms (KEMs) are a more general approach to generating a shared key for use in hybrid encryption. With the advent of quantum computing, the quantum random oracle model is a feasible security model for analyzing post-quantum security. In this model, we assume all operations are classical, but we allow the adversary to make quantum queries to any random oracles used in the scheme.
Hybrid encryption in the quantum random oracle model (QROM) has been recently explored. In this paper, we combine a weakly secure KEM with a symmetric encryption scheme by using two hash functions to achieve a hybrid encryption scheme. We show this scheme is IND-CCA secure in the QROM, offering a more generalized approach to post-quantum hybrid encryption. We provide two post-quantum constructions to illustrate the practicality of this scheme.
A Reaction Attack on LEDApkc
Tomas Fabsic
We propose a new reaction attack on the public-key cryptosystem LEDApkc, which was recently submitted to NIST's Post-Quantum Cryptography Standardization Process. The adversary uses the decoding failure rate (DFR) analysis to learn information about the secret masking matrix Q. Provided the adversary learns information about Q within 10^4 x DFR^-1 decryptions (as prescribed by LEDApkc design to thwart previously known attacks), the adversary builds a small set of candidates for Q. Using these candidates, the adversary obtains candidates for a generator matrix of the secret LDPC code. Afterwards, the adversary applies Stern's algorithm to recover the secret matrix H, thus recovering the full private key. Provided the adversary can learn information about the matrix Q, the complexity of the attack is below 2^99 for a parameter set for 128-bit security. In order to study whether the adversary can learn information about Q from 10^4 x DFR^-1 decryptions, we conducted experiments with a modified parameter set. The parameter set was modified only in order to increase the DFR, and thus make experiments less computationally expensive. We show that with the modified parameter set it is indeed possible to learn the required information about the matrix Q.
Attack on the Edon-K Key Encapsulation Mechanism
Matthieu Lequesne
The key encapsulation mechanism Edon-K was proposed in response to the call for post-quantum cryptography standardization issued by the National Institute of Standards and Technologies (NIST). This scheme is inspired by the McEliece scheme but uses another family of codes defined over F_{2^128} instead of F_2 and is not based on the Hamming metric. It allows significantly shorter public keys than the McEliece scheme. In this paper, we give a polynomial time algorithm that recovers the encapsulated secret. This attack makes the scheme insecure for the intended use. We obtain this result by observing that recovering the error in the McEliece scheme corresponding to Edon-K can be viewed as a decoding problem for the rank-metric. We show that the code used in Edon-K is in fact a super-code of a Low Rank Parity Check (LRPC) code of very small rank (1 or 2). A suitable parity-check matrix for the super-code of such low rank can be easily derived from for the public key. We then use this parity-check matrix in a decoding algorithm that was devised for LRPC codes to recover the error. Finally we explain how we decapsulate the secret once we have found the error.
A QC-LDPC code-based public-key cryptosystem resistant to reaction attacks
Paolo Santini
Code-Based Zero-Knowledge Proofs, Signatures and More
Kirill Morozov
We will review some recent results concerning code-based cryptographic protocols. First, we will look at the randomized variants of the McEliece and the Niederriter cryptosystems, observe that Jain-Krenn-Pietrzak-Tentesí and Sternís zero-knowledge identification schemes can be applied as proof of plaintext knowledge for the above systems, respectively, and then look into further applications. Next, we will discuss code-based commitments by Jain et al. and their relation to the above systems. Finally, we will review recent results on code-based digital signatures: the security of the Courtois-Finiasz-Sendrier scheme and the RACOSS scheme.
LCD codes from Cartesian codes
Hiram López
Batch Codes from Hamming and Reed-Muller Codes
Felice Manganiello
Batch codes, introduced by Ishai et al., have applications in distributed storage and queueing theory. Their main property is to encode information into an m-tuple of strings, called buckets. We first focus on batch properties of binary Hamming codes and show their optimality. We then switch to the larger family of Reed-Müller codes and show that also binary first order Reed-Müller codes are optimal batch codes when the number of users is 4. Time permitting we will generalize the results to binary Reed- Müller codes which have order less than half their length. These results were proven during the 2016 REU summer program on Coding Theory, Cryptography and Number Theory at Clemson.
Hardware Implementation of Code-based Key Encapsulation using Dyadic GS Codes (DAGS)
Viet Ba Dang
Since their invention in the late 1970s, code-based cryptosystems have been well studied for the past four decades and became one of the main branches of Post-Quantum Cryptography (PQC). In this presentation, we introduce a highspeed hardware implementation of the code-based key encapsulation mechanism (KEM) using Dyadic Generalized Srivastava Codes, DAGS, supporting the 96-bit post-quantum security and 192-bit classical security levels. This KEM achieves indistinguishability under chosen ciphertext attack (IND-CCA), and features compact public keys and quite efficient encapsulation and decapsulation algorithms. The presentation will focus on block diagrams of a single design that supports both encapsulation and decapsulation. Key generation is assumed to be done in software. The main building blocks of our design are composite field operations, a dyadic matrix expander, an error generator, and an alternant decoder. We also present tentative timing analysis and resource utilization for the Field Programmable Gate Array (FPGA) implementation using Xilinx Kintex-7 UltraScale XCKU035-FFVA1156 device. This hardware implementation is fully compliant with the PQC Hardware Application Programming Interface (API), proposed by the Cryptographic Engineering Research Group at George Mason University, as a basis for the fair and comprehensive benchmarking of all candidates in the NIST PQC Standardization Process. Our VHDL code will soon be made available as open-source in order to support the transparency of the evaluation process and to speed-up any further design-space exploration and benchmarking on multiple hardware platforms.
Implementation of Hybrid Mode Quantum-safe Key Exchange over Optical Communication Systems
Joo Yeon Cho
Recent progress on quantum computing is increasingly putting the security of current networks at stake. Many networks require long-term security to ensure that information that is transferred in networks today is protected for many years to come, even if large scale quantum computers become a reality. The Niederreiter cryptosystem is one of the public-key cryptosystems that do not have known vulnerabilities to attacks using quantum computers. However, the Niederreiter cryptosystem has not been widely used for practical applications due to the large key size. The optical network is one of the applications that would not suffer much from the use of large public keys due to the high-speed data transmission. We implemented an authenticated key exchange protocol based on the Niederreiter cryptosystem using Goppa code. We show that the Niederreiter-based key exchange is well suited for the G.709 Optical Transport Network (OTN) framework and satisfies a typical key refreshing rate used in industry. The key exchange protocol addresses known weaknesses of the Niederreiter cryptosystem under a framework of the PACE protocol. We extend our system to, so-called, a hybrid mode key exchange. In reality, it is preferred to implement a combination of a quantum-safe cryptographic protocol with existing cryptographic protocols (which may not be post-quantum) in order to offer the compatibility with existing protocols, networks and applications. We built a hybrid mode key exchange scheme combining classical key exchange (Diffie-Hellman) and post-quantum key exchange (Niederreiter-based). We perform the hybrid mode key exchange for an encrypted 100G optical communication link. The key exchange protocol is implemented in software and demonstrated in a commercial optical communication system. To our knowledge, this is the first demonstration of this kind and shows that quantum-safe optical communication is possible today.
