nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Post-Quantum Cryptography

5th International Workshop, PQCrypto 2013, Limoges, France, June 4-7, 2013. Proceedings

herausgegeben von: Philippe Gaborit

Verlag: Springer Berlin Heidelberg

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 5th International Workshop on Post-Quantum Cryptography, PQCrypto 2013, held in Limoges, France, in June 2013. The 17 revised full papers presented were carefully reviewed and selected from 24 submissions. The papers cover all technical aspects of cryptographic research related to the future world with large quantum computers such as code-based cryptography, lattice-based cryptography, multivariate cryptography, cryptanalysis or implementations.

Inhaltsverzeichnis

Frontmatter

Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures

Abstract

In this paper, we address the problem of achieving efficient code-based digital signatures with small public keys. The solution we propose exploits sparse syndromes and randomly designed low-density generator matrix codes. Based on our evaluations, the proposed scheme is able to outperform existing solutions, permitting to achieve considerable security levels with very small public keys.

Marco Baldi, Marco Bianchi, Franco Chiaraluce, Joachim Rosenthal, Davide Schipani

Quantum Algorithms for the Subset-Sum Problem

Abstract

This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25. The new algorithm combines the 2010 Howgrave-Graham–Joux subset-sum algorithm with a new streamlined data structure for quantum walks on Johnson graphs.

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, Alexander Meurer

Improved Lattice-Based Threshold Ring Signature Scheme

Abstract

We present in this paper an improvement of the lattice-based threshold ring signature proposed by Cayrel, Lindner, Rückert and Silva (CLRS) [LATINCRYPT ’10]. We generalize the same identification scheme CLRS to obtain a more efficient threshold ring signature. The security of our scheme relies on standard lattice problems. The improvement is a significant reduction of the size of the signature. Our result is a t-out-of-N threshold ring signature which can be seen as t different ring signatures instead of N for the other schemes. We describe the ring signature induced by the particular case of only one signer. To the best of our knowledge, the resulted signatures are the most efficient lattice-based ring signature and threshold signature.

Slim Bettaieb, Julien Schrek

Degree of Regularity for HFEv and HFEv-

Abstract

In this paper, we first prove an explicit formula which bounds the degree of regularity of the family of HFEv (“HFE with vinegar”) and HFEv- (“HFE with vinegar and minus”) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFEv- system is less than or equal to

$$ {{(q-1)(r+v+a-1)} \over{2}}+2 ~\text{if $q$ is even and $r+a$ is odd,} $$

$$ {{(q-1)(r+v+a-1)} \over{2}} +2 ~{\rm otherwise}, $$

where the parameters v, D, q, and a are parameters of the cryptosystem denoting respectively the number of vinegar variables, the degree of the HFE polynomial, the base field size, and the number of removed equations, and r is the “rank” paramter which in the general case is determined by D and q as $r=\lfloor \log_q(D-1)\rfloor +1$. In particular, setting a = 0 gives us the case of HFEv where the degree of regularity is bound by

$$ {{(q - 1)(r + v - 1)} \over{2}} +2 ~\text{if $q$ is even and $r$ is odd,} $$

$$ {{(q-1)(r+v)} \over{2}} +2 ~\text{otherwise.} $$

This formula provides the first solid theoretical estimate of the complexity of algebraic cryptanalysis of the HFEv- signature scheme, and as a corollary bounds on the complexity of a direct attack against the QUARTZ digital signature scheme. Based on some experimental evidence, we evaluate the complexity of solving QUARTZ directly using F₄/F₅ or similar Gröbner methods to be around 2⁹².

Jintai Ding, Bo-Yin Yang

Software Speed Records for Lattice-Based Signatures

Abstract

Novel public-key cryptosystems beyond RSA and ECC are urgently required to ensure long-term security in the era of quantum computing. The most critical issue on the construction of such cryptosystems is to achieve security and practicability at the same time. Recently, lattice-based constructions were proposed that combine both properties, such as the lattice-based digital signature scheme presented at CHES 2012. In this work, we present a first highly-optimized SIMD-based software implementation of that signature scheme targeting Intel’s Sandy Bridge and Ivy Bridge microarchitectures. This software computes a signature in only 634988 cycles on average on an Intel Core i5-3210M (Ivy Bridge) processor. Signature verification takes only 45036 cycles. This performance is achieved with full protection against timing attacks.

Tim Güneysu, Tobias Oder, Thomas Pöppelmann, Peter Schwabe

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

Abstract

By applying Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 2^{1.799n + o(n)}, improving upon the classical time complexity of 2^{2.465n + o(n)} of Pujol and Stehlé and the 2^{2n + o(n)} of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 2^{0.312n + o(n)}, improving upon the classical time complexity of 2^{0.384n + o(n)} of Wang et al. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Thijs Laarhoven, Michele Mosca, Joop van de Pol

An Efficient Attack of a McEliece Cryptosystem Variant Based on Convolutional Codes

Abstract

Löndahl and Johansson proposed last year a variant of the McEliece cryptosystem which replaces Goppa codes by convolutional codes. This modification is supposed to make structural attacks more difficult since the public generator matrix of this scheme contains large parts that are generated completely at random. They proposed two schemes of this kind, one of them consists in taking a Goppa code and extending it by adding a generator matrix of a time varying convolutional code. We show here that this scheme can be successfully attacked by looking for low-weight codewords in the public code of this scheme and using it to unravel the convolutional part. It remains to break the Goppa part of this scheme which can be done in less than a day of computation in the case at hand.

Grégory Landais, Jean-Pierre Tillich

Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations

Abstract

It is well known that solving randomly chosen Multivariate Quadratic equations over a finite field (MQ-Problem) is NP-hard, and the security of Multivariate Public Key Cryptosystems (MPKCs) is based on the MQ-Problem. However, this problem can be solved efficiently when the number of unknowns n is sufficiently greater than that of equations m (This is called “Underdefined”). Indeed, the algorithm by Kipnis et al. (Eurocrypt’99) can solve the MQ-Problem over a finite field of even characteristic in a polynomial-time of n when n ≥ m(m + 1). Therefore, it is important to estimate the hardness of the MQ-Problem to evaluate the security of Multivariate Public Key Cryptosystems. We propose an algorithm in this paper that can solve the MQ-Problem in a polynomial-time of n when n ≥ m(m + 3)/2, which has a wider applicable range than that by Kipnis et al. We will also compare our proposed algorithm with other known algorithms. Moreover, we implemented this algorithm with Magma and solved the MQ-Problem of m = 28 and n = 504, and it takes 78.7 seconds on a common PC.

Hiroyuki Miura, Yasufumi Hashimoto, Tsuyoshi Takagi

Quantum Key Distribution in the Classical Authenticated Key Exchange Framework

Abstract

Key establishment is a crucial primitive for building secure channels in a multi-party setting. Without quantum mechanics, key establishment can only be done under the assumption that some computational problem is hard. Since digital communication can be easily eavesdropped and recorded, it is important to consider the secrecy of information anticipating future algorithmic and computational discoveries which could break the secrecy of past keys, violating the secrecy of the confidential channel.

Quantum key distribution (QKD) can be used generate secret keys that are secure against any future algorithmic or computational improvements. QKD protocols still require authentication of classical communication, although existing security proofs of QKD typically assume idealized authentication. It is generally considered folklore that QKD when used with computationally secure authentication is still secure against an unbounded adversary, provided the adversary did not break the authentication during the run of the protocol.

We describe a security model for quantum key distribution extending classical authenticated key exchange (AKE) security models. Using our model, we characterize the long-term security of the BB84 QKD protocol with computationally secure authentication against an eventually unbounded adversary. By basing our model on traditional AKE models, we can more readily compare the relative merits of various forms of QKD and existing classical AKE protocols. This comparison illustrates in which types of adversarial environments different quantum and classical key agreement protocols can be secure.

Michele Mosca, Douglas Stebila, Berkant Ustaoğlu

Cryptanalysis of Hash-Based Tamed Transformation and Minus Signature Scheme

Abstract

In 2011, wang et al. proposed a security enhancement method of Multivariate Public Key Cryptosystems (MPKCs), named Extended Multivariate public key Cryptosystems (EMC). They introduced more variables in an original MPKC by a so-called Hash-based Tamed (HT) transformation in order to resist existing attack on the original MPKC. They proposed Hash-based Tamed Transformation and Minus (HTTM) signature scheme which combined EMC method with minus method. Through our analysis, the HTTM is not secure as they declared. If we can forge a valid signature of the original MPKC-minus signature scheme, we could forge a valid signature of HTTM scheme successfully.

Xuyun Nie, Zhaohu Xu, Johannes Buchmann

A Classification of Differential Invariants for Multivariate Post-quantum Cryptosystems

Abstract

Multivariate Public Key Cryptography(MPKC) has become one of a few options for security in the quantum model of computing. Though a few multivariate systems have resisted years of effort from the cryptanalytic community, many such systems have fallen to a surprisingly small pool of techniques. There have been several recent attempts at formalizing more robust security arguments in this venue with varying degrees of applicability. We present an extension of one such recent measure of security against a differential adversary which has the benefit of being immediately applicable in a general setting on unmodified multivariate schemes.

Ray Perlner, Daniel Smith-Tone

Secure and Anonymous Hybrid Encryption from Coding Theory

Abstract

Cryptographic schemes based on coding theory are one of the most accredited choices for cryptography in a post-quantum scenario. In this work, we present a hybrid construction based on the Niederreiter framework that provides IND-CCA security in the random oracle model. In addition, the construction satisfies the IK-CCA notion of anonymity whose importance is ever growing in the cryptographic community.

Edoardo Persichetti

Fast Verification for Improved Versions of the UOV and Rainbow Signature Schemes

Abstract

Multivariate cryptography is one of the main candidates to guarantee the security of communication in the post-quantum era. While multivariate signature schemes are fast and require only modest computational resources, the key sizes of such schemes are quite large. In [14] Petzoldt et al. proposed a way to reduce the public key size of certain multivariate signature schemes like UOV and Rainbow by a large factor. In this paper we show that by using this idea it is possible to speed up the verification process of these schemes, too. For example, we are able to speed up the verification process of UOV by a factor of 5.

Albrecht Petzoldt, Stanislav Bulygin, Johannes Buchmann

The Hardness of Code Equivalence over $\mathbb{F}_q$ and Its Application to Code-Based Cryptography

Abstract

The code equivalence problem is to decide whether two linear codes over $\mathbb{F}_{q}$ are identical up to a linear isometry of the Hamming space. In this paper, we review the hardness of code equivalence over $\mathbb{F}_q$ due to some recent negative results and argue on the possible implications in code-based cryptography. In particular, we present an improved version of the three-pass identification scheme of Girault and discuss on a connection between code equivalence and the hidden subgroup problem.

Nicolas Sendrier, Dimitris E. Simos

Timing Attacks against the Syndrome Inversion in Code-Based Cryptosystems

Abstract

In this work we present the first practical key-aimed timing attack against code-based cryptosystems. It arises from vulnerabilities that are present in the inversion of the error syndrome through the Extended Euclidean Algorithm that is part of the decryption operation of these schemes. Three types of timing vulnerabilities are combined to a successful attack. Each is used to gain information about the secret support, which is part of code-based decryption keys: The first allows recovery of the zero-element, the second is a refinement of a previously described vulnerability yielding linear equations, and the third enables to retrieve cubic equations.

Falko Strenzke

Simple Matrix Scheme for Encryption

Abstract

There are several attempts to build asymmetric pubic key encryption schemes based on multivariate polynomials of degree two over a finite field. However, most of them are insecure. The common defect in many of them comes from the fact that certain quadratic forms associated with their central maps have low rank, which makes them vulnerable to the MinRank attack. We propose a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplication, which does not have such a low rank property. The new scheme will be called Simple Matrix Scheme or ABC in short. We also propose some parameters for practical and secure implementation.

Chengdong Tao, Adama Diene, Shaohua Tang, Jintai Ding

Multivariate Signature Scheme Using Quadratic Forms

Abstract

Multivariate Public Key Cryptosystems (MPKC) are candidates for post-quantum cryptography. MPKC has an advantage in that its encryption and decryption are relatively efficient. In this paper, we propose a multivariate signature scheme using quadratic forms. For a finite dimensional vector space V, it is known that there are exactly two equivalence classes of non-degenerate quadratic forms over V. We utilize the method to transform any non-degenerate quadratic form into the normal form of either of the two equivalence classes in order to construct a new signature scheme in MPKC. The signature generation of our scheme is between eight and nine times more efficient more than the multivariate signature scheme Rainbow at the level of 88-bit security. We show that the public keys of our scheme can not be represented by the public keys of other MPKC signature schemes and this means our scheme is immune to many attacks that depend on the form of the central map used by these schemes.

Takanori Yasuda, Tsuyoshi Takagi, Kouichi Sakurai

Backmatter

Titel: Post-Quantum Cryptography
herausgegeben von: Philippe Gaborit
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-38616-9
Print ISBN: 978-3-642-38615-2
DOI: https://doi.org/10.1007/978-3-642-38616-9

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures

Quantum Algorithms for the Subset-Sum Problem

Improved Lattice-Based Threshold Ring Signature Scheme

Degree of Regularity for HFEv and HFEv-

Software Speed Records for Lattice-Based Signatures

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

An Efficient Attack of a McEliece Cryptosystem Variant Based on Convolutional Codes

Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations

Quantum Key Distribution in the Classical Authenticated Key Exchange Framework

Cryptanalysis of Hash-Based Tamed Transformation and Minus Signature Scheme

A Classification of Differential Invariants for Multivariate Post-quantum Cryptosystems

Secure and Anonymous Hybrid Encryption from Coding Theory

Fast Verification for Improved Versions of the UOV and Rainbow Signature Schemes

The Hardness of Code Equivalence over $\mathbb{F}_q$ and Its Application to Code-Based Cryptography

Timing Attacks against the Syndrome Inversion in Code-Based Cryptosystems

Simple Matrix Scheme for Encryption

Multivariate Signature Scheme Using Quadratic Forms

Backmatter

Premium Partner