nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Post-Quantum Cryptography

7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings

herausgegeben von: Tsuyoshi Takagi

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 7th International Workshop on Post-Quantum Cryptography, PQCrypto 2016, held in Fukuoka, Japan, in February 2016.

The 16 revised full papers presented were carefully reviewed and selected from 42 submissions. The papers cover all technical aspects of multivariate polynomial cryptography, code-based cryptography, lattice-based cryptography, quantum algorithms, post-quantum protocols, and implementations.

Inhaltsverzeichnis

Frontmatter

IND-CCA Secure Hybrid Encryption from QC-MDPC Niederreiter

Abstract

QC-MDPC McEliece attracted significant attention as promising alternative public-key encryption scheme believed to be resistant against quantum computing attacks. Compared to binary Goppa codes, it achieves practical key sizes and was shown to perform well on constrained platforms such as embedded microcontrollers and FPGAs.

However, so far none of the published QC-MDPC McEliece/Niederreiter implementations provide indistinguishability under chosen plaintext or chosen ciphertext attacks. Common ways for the McEliece and Niederreiter encryption schemes to achieve IND-CPA/IND-CCA security are surrounding constructions that convert them into secured schemes. In this work we take a slightly different approach presenting (1) an efficient implementation of QC-MDPC Niederreiter for ARM Cortex-M4 microcontrollers and (2) the first implementation of Persichetti’s IND-CCA hybrid encryption scheme from PQCrypto’13 instantiated with QC-MDPC Niederreiter for key encapsulation and AES-CBC/AES-CMAC for data encapsulation. Both implementations achieve practical performance for embedded microcontrollers, at 80-bit security hybrid encryption takes 16.5 ms, decryption 111 ms and key-generation 386.4 ms.

Ingo von Maurich, Lukas Heberle, Tim Güneysu

RankSynd a PRNG Based on Rank Metric

Abstract

In this paper, we consider a pseudo-random generator based on the difficulty of the syndrome decoding problem for rank metric codes. We also study the resistance of this problem against a quantum computer. Our results show that with rank metric it is possible to obtain fast PRNG with small public data, without considering additional structure for public matrices like quasi-cyclicity for Hamming distance.

Philippe Gaborit, Adrien Hauteville, Jean-Pierre Tillich

Applying Grover’s Algorithm to AES: Quantum Resource Estimates

Abstract

We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford\(+T\) gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover’s quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.

Markus Grassl, Brandon Langenberg, Martin Roetteler, Rainer Steinwandt

Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation

Abstract

We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition). We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption. And we give proofs that CBC and CFB mode are secure if we assume a quantum secure PRF (secure under queries in superposition).

Mayuresh Vivekanand Anand, Ehsan Ebrahimi Targhi, Gelo Noel Tabia, Dominique Unruh

Post-Quantum Security Models for Authenticated Encryption

Abstract

We propose a security model for evaluating the security of authenticated encryption schemes in the post-quantum setting. Our security model is based on a combination of the classical Bellare-Namprempre security model for authenticated encryption together with modifications from Boneh and Zhandry to handle message authentication against quantum adversaries. We give a generic construction based on the Bellare-Namprempre model for producing an authenticated encryption protocol from any quantum-resistant symmetric-key encryption scheme together with any authentication scheme (digital signature scheme or MAC) admitting a classical security reduction to a quantum-computationally hard problem. We give examples of suitable authentication schemes under the quantum random oracle model using the Boneh-Zhandry transformation. We also provide tables of communication overhead calculations and comparisons for various choices of component primitives in our construction.

Vladimir Soukharev, David Jao, Srinath Seshadri

Quantum Collision-Resistance of Non-uniformly Distributed Functions

Abstract

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that \(\varOmega (2^{k/9})\) quantum queries are necessary to find a collision for function f. This is needed in some security proofs in the quantum random oracle model (e.g. Fujisaki-Okamoto transform).

Ehsan Ebrahimi Targhi, Gelo Noel Tabia, Dominique Unruh

An Efficient Attack on a Code-Based Signature Scheme

Abstract

Baldi et al. have introduced in [BBC+13] a very novel code based signature scheme. However we will prove here that some of the bits of the signatures are correlated in this scheme and this allows an attack that recovers enough of the underlying secret structure to forge new signatures. This cryptanalysis was performed on the parameters which were devised for 80 bits of security and broke them with 100, 000 signatures originating from the same secret key.

Aurélie Phesso, Jean-Pierre Tillich

Vulnerabilities of “McEliece in the World of Escher”

Abstract

Recently, Gligoroski et al. proposed code-based encryption and signature schemes using list decoding, blockwise triangular private keys, and a nonuniform error pattern based on “generalized error sets.” The general approach was referred to as McEliece in the World of Escher. This paper demonstrates attacks which are significantly cheaper than the claimed security level of the parameters given by Gligoroski et al. We implemented an attack on the proposed 80-bit parameters which was able to recover private keys for both encryption and signatures in approximately 2 hours on a single laptop. We further find that increasing the parameters to avoid our attack will require parameters to grow by (at least) two orders of magnitude for encryption, and may not be achievable at all for signatures.

Dustin Moody, Ray Perlner

Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes

Abstract

Polar codes discovered by Arikan form a very powerful family of codes attaining many information theoretic limits in the fields of error correction and source coding. They have in particular much better decoding capabilities than Goppa codes which places them as a serious alternative in the design of both a public-key encryption scheme à la McEliece and a very efficient signature scheme. Shrestha and Kim proposed in 2014 to use them in order to come up with a new code-based public key cryptosystem. We present a key-recovery attack that makes it possible to recover a description of the permuted polar code providing all the information required for decrypting any message.

Magali Bardet, Julia Chaulet, Vlad Dragoi, Ayoub Otmani, Jean-Pierre Tillich

Analysis of Information Set Decoding for a Sub-linear Error Weight

Abstract

The security of code-based cryptography is strongly related to the hardness of generic decoding of linear codes. The best known generic decoding algorithms all derive from the Information Set Decoding algorithm proposed by Prange in 1962. The ISD algorithm was later improved by Stern in 1989 (and Dumer in 1991). Those last few years, some significant improvements have occurred. First by May, Meurer, and Thomae at Asiacrypt 2011, then by Becker, Joux, May, and Meurer at Eurocrypt 2012, and finally by May and Ozerov at Eurocrypt 2015. With those methods, correcting w errors in a binary linear code of length n and dimension k has a cost \(2^{cw(1+\mathbf {o}(1))}\) when the length n grows, where c is a constant, depending of the code rate k / n and of the error rate w / n. The above ISD variants have all improved that constant c when they appeared.

When the number of errors w is sub-linear, \(w=\mathbf {o}(n)\), the cost of all ISD variants still has the form \(2^{cw(1+\mathbf {o}(1))}\). We prove here that the constant c only depends of the code rate k / n and is the same for all the known ISD variants mentioned above, including the fifty years old Prange algorithm. The most promising variants of McEliece encryption scheme use either Goppa codes, with \(w=\mathbf {O}(n/\log (n))\), or MDPC codes, with \(w=\mathbf {O}(\sqrt{n})\). Our result means that, in those cases, when we scale up the system parameters, the improvement of the latest variants of ISD become less and less significant. This fact has been observed already, we give here a formal proof of it. Moreover, our proof seems to indicate that any foreseeable variant of ISD should have the same asymptotic behavior.

Rodolfo Canto Torres, Nicolas Sendrier

On the Differential Security of the HFEv- Signature Primitive

Abstract

Multivariate Public Key Cryptography (MPKC) is one of the most attractive post-quantum options for digital signatures in a wide array of applications. The history of multivariate signature schemes is tumultuous, however, and solid security arguments are required to inspire faith in the schemes and to verify their security against yet undiscovered attacks. The effectiveness of “differential attacks” on various field-based systems has prompted the investigation of the resistance of schemes against differential adversaries. Due to its prominence in the area and the recent optimization of its parameters, we prove the security of \(HFEv^-\) against differential adversaries. We investigate the newly suggested parameters and conclude that the proposed scheme is secure against all known attacks and against any differential adversary.

Ryann Cartor, Ryan Gipson, Daniel Smith-Tone, Jeremy Vates

Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems

Abstract

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.

Alan Szepieniec, Jintai Ding, Bart Preneel

Security Analysis and Key Modification for ZHFE

Abstract

ZHFE, designed by Porras et al., is one of the few promising candidates for a multivariate public-key encryption algorithm. In this article we extend and expound upon the existing security analysis on this scheme. We prove security against differential adversaries, complementing a more accurate and robust discussion of resistance to rank and algebraic attacks. We further suggest a modification, \(ZHFE^-\), a multivariate encryption scheme which retains the security and performance properties of ZHFE while optimizing key size in this theoretical framework.

Ray Perlner, Daniel Smith-Tone

Efficient ZHFE Key Generation

Abstract

In this paper we present a new algorithm to construct the keys of the multivariate public key encryption scheme ZHFE. Constructing ZHFE’s trapdoor involves finding a low degree polynomial of q-Hamming-weight-three, as an aid to invert a pair of q-Hamming-weight-two polynomials of high degree and high rank. This is done by solving a large sparse linear system of equations. We unveil the combinatorial structure of the system in order to reveal the hidden structure of the matrix associated with it. When the system’s variables and equations are organized accordingly, an almost block diagonal shape emerges. We then exploit this shape to solve the system much faster than when ZHFE was first proposed. The paper presents the theoretical details explaining the structure of the matrix. We also present experimental data that confirms the notable improvement of the key generation complexity, which makes ZHFE more suitable for practical implementations.

John B. Baena, Daniel Cabarcas, Daniel E. Escudero, Jaiberth Porras-Barrera, Javier A. Verbel

Additively Homomorphic Ring-LWE Masking

Abstract

In this paper, we present a new masking scheme for ring-LWE decryption. Our scheme exploits the additively-homomorphic property of the existing ring-LWE encryption schemes and computes an additive-mask as an encryption of a random message. Our solution differs in several aspects from the recent masked ring-LWE implementation by Reparaz et al. presented at CHES 2015; most notably we do not require a masked decoder but work with a conventional, unmasked decoder. As such, we can secure a ring-LWE implementation using additive masking with minimal changes. Our masking scheme is also very generic in the sense that it can be applied to other additively-homomorphic encryption schemes.

Oscar Reparaz, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid Verbauwhede

A Homomorphic LWE Based E-voting Scheme

Abstract

In this paper we present a new post-quantum electronic-voting protocol. Our construction is based on LWE fully homomorphic encryption and the protocol is inspired by existing e-voting schemes, in particular Helios. The strengths of our scheme are its simplicity and transparency, since it relies on public homomorphic operations. Furthermore, the use of lattice-based primitives greatly simplifies the proofs of correctness, privacy and verifiability, as no zero-knowledge proof are needed to prove the validity of individual ballots or the correctness of the final election result. The security of our scheme is based on classical SIS/LWE assumptions, which are asymptotically as hard as worst-case lattice problems and relies on the random oracle heuristic. We also propose a new procedure to distribute the decryption task, where each trustee provides an independent proof of correct decryption in the form of a publicly verifiable ciphertext trapdoor. In particular, our protocol requires only two trustees, unlike classical proposals using threshold decryption via Shamir’s secret sharing.

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène

Backmatter

Titel: Post-Quantum Cryptography
herausgegeben von: Tsuyoshi Takagi
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-29360-8
Print ISBN: 978-3-319-29359-2
DOI: https://doi.org/10.1007/978-3-319-29360-8

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

IND-CCA Secure Hybrid Encryption from QC-MDPC Niederreiter

RankSynd a PRNG Based on Rank Metric

Applying Grover’s Algorithm to AES: Quantum Resource Estimates

Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation

Post-Quantum Security Models for Authenticated Encryption

Quantum Collision-Resistance of Non-uniformly Distributed Functions

An Efficient Attack on a Code-Based Signature Scheme

Vulnerabilities of “McEliece in the World of Escher”

Cryptanalysis of the McEliece Public Key Cryptosystem Based on Polar Codes

Analysis of Information Set Decoding for a Sub-linear Error Weight

On the Differential Security of the HFEv- Signature Primitive

Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems

Security Analysis and Key Modification for ZHFE

Efficient ZHFE Key Generation

Additively Homomorphic Ring-LWE Masking

A Homomorphic LWE Based E-voting Scheme

Backmatter

Premium Partner