## CryptoDB

### Damien Stehlé

#### Affiliation: ENS Lyon, France

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Approx-SVP in Ideal Lattices with Pre-processing
📺
Abstract

We describe an algorithm to solve the approximate Shortest Vector Problem for lattices corresponding to ideals of the ring of integers of an arbitrary number field K. This algorithm has a pre-processing phase, whose run-time is exponential in
$$\log |\varDelta |$$
log|Δ| with
$$\varDelta $$
Δ the discriminant of K. Importantly, this pre-processing phase depends only on K. The pre-processing phase outputs an “advice”, whose bit-size is no more than the run-time of the query phase. Given this advice, the query phase of the algorithm takes as input any ideal I of the ring of integers, and outputs an element of I which is at most
$$\exp (\widetilde{O}((\log |\varDelta |)^{\alpha +1}/n))$$
exp(O~((log|Δ|)α+1/n)) times longer than a shortest non-zero element of I (with respect to the Euclidean norm of its canonical embedding). This query phase runs in time and space
$$\exp (\widetilde{O}( (\log |\varDelta |)^{\max (2/3, 1-2\alpha )}))$$
exp(O~((log|Δ|)max(2/3,1-2α))) in the classical setting, and
$$\exp (\widetilde{O}((\log |\varDelta |)^{1-2\alpha }))$$
exp(O~((log|Δ|)1-2α)) in the quantum setting. The parameter
$$\alpha $$
α can be chosen arbitrarily in [0, 1 / 2]. Both correctness and cost analyses rely on heuristic assumptions, whose validity is consistent with experiments.The algorithm builds upon the algorithms from Cramer et al. [EUROCRYPT 2016] and Cramer et al. [EUROCRYPT 2017]. It relies on the framework from Buchmann [Séminaire de théorie des nombres 1990], which allows to merge them and to extend their applicability from prime-power cyclotomic fields to all number fields. The cost improvements are obtained by allowing precomputations that depend on the field only.

2019

JOFC

Cryptanalysis of the CLT13 Multilinear Map
Abstract

In this paper, we describe a polynomial time cryptanalysis of the (approximate) multilinear map proposed by Coron, Lepoint, and Tibouchi in Crypto13 (CLT13). This scheme includes a zero-testing functionality that determines whether the message of a given encoding is zero or not. This functionality is useful for designing several of its applications, but it leaks unexpected values, such as linear combinations of the secret elements. By collecting the outputs of the zero-testing algorithm, we construct a matrix containing the hidden information as eigenvalues, and then recover all the secret elements of the CLT13 scheme via diagonalization of the matrix. In addition, we provide polynomial time algorithms to directly break the security assumptions of many applications based on the CLT13 scheme. These algorithms include solving subgroup membership, decision linear, and graded external Diffie–Hellman problems. These algorithms mainly rely on the computation of the determinants of the matrices and their greatest common divisor, instead of performing their diagonalization.

2018

PKC

Learning with Errors and Extrapolated Dihedral Cosets
Abstract

The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal.We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev’s famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS 02). We also discuss a connection between eDCP and Childs and Van Dam’s algorithm for generalized hidden shift problems (SODA 07).Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.

2018

TCHES

CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Abstract

In this paper, we present the lattice-based signature scheme Dilithium, which is a component of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite that was submitted to NIST’s call for post-quantum cryptographic standards. The design of the scheme avoids all uses of discrete Gaussian sampling and is easily implementable in constant-time. For the same security levels, our scheme has a public key that is 2.5X smaller than the previously most efficient lattice-based schemes that did not use Gaussians, while having essentially the same signature size. In addition to the new design, we significantly improve the running time of the main component of many lattice-based constructions – the number theoretic transform. Our AVX2-based implementation results in a speed-up of roughly a factor of 2 over the previously best algorithms that appear in the literature. The techniques for obtaining this speed-up also have applications to other lattice-based schemes.

2018

TCC

Adaptively Secure Distributed PRFs from $\mathsf {LWE}$
Abstract

In distributed pseudorandom functions (DPRFs), a PRF secret key SK is secret shared among N servers so that each server can locally compute a partial evaluation of the PRF on some input X. A combiner that collects t partial evaluations can then reconstruct the evaluation F(SK, X) of the PRF under the initial secret key. So far, all non-interactive constructions in the standard model are based on lattice assumptions. One caveat is that they are only known to be secure in the static corruption setting, where the adversary chooses the servers to corrupt at the very beginning of the game, before any evaluation query. In this work, we construct the first fully non-interactive adaptively secure DPRF in the standard model. Our construction is proved secure under the $$\mathsf {LWE}$$ assumption against adversaries that may adaptively decide which servers they want to corrupt. We also extend our construction in order to achieve robustness against malicious adversaries.

2018

ASIACRYPT

Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ
Abstract

The Blockwise-Korkine-Zolotarev (BKZ) lattice reduction algorithm is central in cryptanalysis, in particular for lattice-based cryptography. A precise understanding of its practical behavior in terms of run-time and output quality is necessary for parameter selection in cryptographic design. As the provable worst-case bounds poorly reflect the practical behavior, cryptanalysts rely instead on the heuristic BKZ simulator of Chen and Nguyen (Asiacrypt’11). It fits better with practical experiments, but not entirely. In particular, it over-estimates the norm of the first few vectors in the output basis. Put differently, BKZ performs better than its Chen–Nguyen simulation.In this work, we first report experiments providing more insight on this shorter-than-expected phenomenon. We then propose a refined BKZ simulator by taking the distribution of short vectors in random lattices into consideration. We report experiments suggesting that this refined simulator more accurately predicts the concrete behavior of BKZ. Furthermore, we design a new BKZ variant that exploits the shorter-than-expected phenomenon. For the same cost assigned to the underlying SVP-solver, the new BKZ variant produces bases of better quality. We further illustrate its potential impact by testing it on the SVP-120 instance of the Darmstadt lattice challenge.

2017

CRYPTO

2015

ASIACRYPT

2010

EPRINT

Faster Fully Homomorphic Encryption
Abstract

We describe two improvements to Gentry's fully homomorphic scheme
based on ideal lattices and its analysis: we provide a refined
analysis of one of the hardness assumptions (the one related to the
Sparse Subset Sum Problem) and we introduce a probabilistic decryption
algorithm that can be implemented with an algebraic circuit of low
multiplicative degree. Combined together, these improvements lead to a
faster fully homomorphic scheme, with a~$\softO(\lambda^{3})$ bit
complexity per elementary binary add/mult gate, where~$\lambda$ is the
security parameter. These improvements also apply to the fully
homomorphic schemes of Smart and Vercauteren [PKC'2010] and van Dijk
et al. [Eurocrypt'2010].

#### Program Committees

- Crypto 2019
- Eurocrypt 2018
- Asiacrypt 2017
- Eurocrypt 2017
- Asiacrypt 2016
- PKC 2016
- Asiacrypt 2015
- PKC 2015
- Asiacrypt 2013
- Crypto 2012

#### Coauthors

- Shweta Agrawal (1)
- Shi Bai (4)
- Zvika Brakerski (1)
- Jung Hee Cheon (3)
- Léo Ducas (2)
- Kyoohyung Han (2)
- Guillaume Hanrot (3)
- Eike Kiltz (1)
- Elena Kirshanova (1)
- Fabien Laguillaumie (1)
- Adeline Langlois (5)
- Changmin Lee (2)
- Tancrède Lepoint (4)
- Benoît Libert (5)
- San Ling (3)
- Vadim Lyubashevsky (1)
- Phong Q. Nguyen (1)
- Khoa Nguyen (1)
- Alice Pellet-Mary (2)
- Duong Hieu Phan (2)
- Xavier Pujol (2)
- Miruna Rosca (2)
- Adeline Roux-Langlois (1)
- Hansol Ryu (2)
- Amin Sakzad (3)
- Peter Schwabe (1)
- Gregor Seiler (1)
- Ron Steinfeld (13)
- Keisuke Tanaka (1)
- Radu Titiu (1)
- Alexandre Wallet (1)
- Huaxiong Wang (1)
- Weiqiang Wen (2)
- Keita Xagawa (1)