## CryptoDB

### Vadim Lyubashevsky

#### Affiliation: IBM Research - Zurich

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts
Abstract

In applications of fully-homomorphic encryption (FHE) that involve computation on encryptions produced by several users, it is important that each user proves that her input is indeed well-formed. This may simply mean that the inputs are valid FHE ciphertexts or, more generally, that the plaintexts m additionally satisfy
$$f(m)=1$$
for some public function f. The most efficient FHE schemes are based on the hardness of the Ring-LWE problem and so a natural solution would be to use lattice-based zero-knowledge proofs for proving properties about the ciphertext. Such methods, however, require larger-than-necessary parameters and result in rather long proofs, especially when proving general relationships.In this paper, we show that one can get much shorter proofs (roughly 1.25 KB) by first creating a Pedersen commitment from the vector corresponding to the randomness and plaintext of the FHE ciphertext. To prove validity of the ciphertext, one can then prove that this commitment is indeed to the message and randomness and these values are in the correct range. Our protocol utilizes a connection between polynomial operations in the lattice scheme and inner product proofs for Pedersen commitments of Bünz et al. (S&P 2018). Furthermore, our proof of equality between the ciphertext and the commitment is very amenable to amortization – proving the equivalence of k ciphertext/commitment pairs only requires an additive factor of
$$O(\log {k})$$
extra space than for one such proof. For proving additional properties of the plaintext(s), one can then directly use the logarithmic-space proofs of Bootle et al. (Eurocrypt 2016) and Bünz et al. (IEEE S&P 2018) for proving arbitrary relations of discrete log commitment.Our technique is not restricted to FHE ciphertexts and can be applied to proving many other relations that arise in lattice-based cryptography. For example, we can create very efficient verifiable encryption/decryption schemes with short proofs in which confidentiality is based on the hardness of Ring-LWE while the soundness is based on the discrete logarithm problem. While such proofs are not fully post-quantum, they are adequate in scenarios where secrecy needs to be future-proofed, but one only needs to be convinced of the validity of the proof in the pre-quantum era. We furthermore show that our zero-knowledge protocol can be easily modified to have the property that breaking soundness implies solving discrete log in a short amount of time. Since building quantum computers capable of solving discrete logarithm in seconds requires overcoming many more fundamental challenges, such proofs may even remain valid in the post-quantum era.

2019

TCHES

NTTRU: Truly Fast NTRU Using NTT
📺
Abstract

We present NTTRU – an IND-CCA2 secure NTRU-based key encapsulation scheme that uses the number theoretic transform (NTT) over the cyclotomic ring Z7681[X]/(X768−X384+1) and produces public keys and ciphertexts of approximately 1.25 KB at the 128-bit security level. The number of cycles on a Skylake CPU of our constant-time AVX2 implementation of the scheme for key generation, encapsulation and decapsulation is approximately 6.4K, 6.1K, and 7.9K, which is more than 30X, 5X, and 8X faster than these respective procedures in the NTRU schemes that were submitted to the NIST post-quantum standardization process. These running times are also, by a large margin, smaller than those for all the other schemes in the NIST process as well as the KEMs based on elliptic curve Diffie-Hellman. We additionally give a simple transformation that allows one to provably deal with small decryption errors in OW-CPA encryption schemes (such as NTRU) when using them to construct an IND-CCA2 key encapsulation.

2019

EUROCRYPT

Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing
📺
Abstract

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The caveat is that this worst case problem is only mildly hard and in particular admits a quasi-polynomial time algorithm, whereas the LPN variant used in the reduction requires extremely high noise rate of
$$1/2-1/\mathrm{poly}(n)$$
. Thus we can only show that “very hard” LPN is harder than some “very mildly hard” worst case problem. We note that LPN with noise
$$1/2-1/\mathrm{poly}(n)$$
already implies symmetric cryptography.Specifically, we consider the (n, m, w)-nearest codeword problem ((n, m, w)-NCP) which takes as input a generating matrix for a binary linear code in m dimensions and rank n, and a target vector which is very close to the code (Hamming distance at most w), and asks to find the codeword nearest to the target vector. We show that for balanced (unbiased) codes and for relative error
$$w/m \approx {\log ^2 n}/{n}$$
, (n, m, w)-NCP can be solved given oracle access to an LPN distinguisher with noise ratio
$$1/2-1/\mathrm{poly}(n)$$
.Our proof relies on a smoothing lemma for codes which we show to have further implications: We show that (n, m, w)-NCP with the aforementioned parameters lies in the complexity class
$$\mathrm {{Search}\hbox {-}\mathcal {BPP}}^\mathcal {SZK}$$
(i.e. reducible to a problem that has a statistical zero knowledge protocol) implying that it is unlikely to be
$$\mathcal {NP}$$
-hard. We then show that the hardness of LPN with very low noise rate
$$\log ^2(n)/n$$
implies the existence of collision resistant hash functions (our aforementioned result implies that in this parameter regime LPN is also in
$$\mathcal {BPP}^\mathcal {SZK}$$
).

2019

CRYPTO

Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs
📺
Abstract

A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector
$$\vec {s}$$
with small coefficients satisfying
$$A\vec {s}=\vec {u}\bmod \,q$$
. While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of
$$\vec {s}'$$
and c satisfying
$$A\vec {s}'=\vec {u}c$$
where
$$\Vert \vec {s}'\Vert \gg \Vert \vec {s}\Vert $$
and c is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern’s protocol (Crypto ’93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a
$$\varSigma $$
-protocol, each of whose iterations has soundness error
$$2{/}3$$
, and thus requires over 200 repetitions to obtain soundness error of
$$2^{-128}$$
, which is the main culprit behind the large size of the proofs produced.
In this paper, we propose the first lattice-based proof system that significantly outperforms Stern-type proofs for proving knowledge of a short
$$\vec {s}$$
satisfying
$$A\vec {s}=\vec {u}\bmod \,q$$
. Unlike Stern’s proof, which is combinatorial in nature, our proof is more algebraic and uses various relaxed zero-knowledge proofs as sub-routines. The main savings in our proof system comes from the fact that each round has soundness error of
$$1{/}n$$
, where n is the number of columns of A. For typical applications, n is a few thousand, and therefore our proof needs to be repeated around 10 times to achieve a soundness error of
$$2^{-128}$$
. For concrete parameters, it produces proofs that are around an order of magnitude smaller than those produced using Stern’s approach.

2018

EUROCRYPT

2018

CRYPTO

Sub-linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
📺
Abstract

We propose the first zero-knowledge argument with sub-linear communication complexity for arithmetic circuit satisfiability over a prime
$${p}$$
whose security is based on the hardness of the short integer solution (SIS) problem. For a circuit with
$${N}$$
gates, the communication complexity of our protocol is
$$O\left( \sqrt{{N}{\lambda }\log ^3{{N}}}\right) $$
, where
$${\lambda }$$
is the security parameter. A key component of our construction is a surprisingly simple zero-knowledge proof for pre-images of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. (CRYPTO 2012), Baum et al. (CRYPTO 2016), Cramer et al. (EUROCRYPT 2017) and del Pino and Lyubashevsky (CRYPTO 2017), and we believe it to be of independent interest.

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.

2015

EUROCRYPT

2014

ASIACRYPT

#### Program Committees

- Crypto 2020
- Crypto 2019
- Crypto 2017
- PKC 2017
- Eurocrypt 2016
- PKC 2014
- Crypto 2013
- Eurocrypt 2013
- TCC 2012
- PKC 2012
- Eurocrypt 2011
- TCC 2011
- PKC 2010
- Asiacrypt 2010

#### Coauthors

- Michel Abdalla (3)
- Carsten Baum (1)
- Fabrice Benhamouda (1)
- Jonathan Bootle (2)
- Zvika Brakerski (1)
- Jan Camenisch (1)
- Andrea Cerulli (1)
- Rafael del Pino (2)
- Léo Ducas (3)
- Alain Durmus (1)
- Dario Fiore (1)
- Pierre-Alain Fouque (2)
- Jens Groth (1)
- Tim Güneysu (1)
- Stefan Heyse (1)
- Eike Kiltz (3)
- Stephan Krenn (1)
- Tancrède Lepoint (2)
- Daniel Masny (1)
- Daniele Micciancio (4)
- Gregory Neven (2)
- Christof Paar (1)
- Adriana Palacio (1)
- Chris Peikert (3)
- Krzysztof Pietrzak (1)
- Rafaël Del Pino (1)
- Thomas Pöppelmann (1)
- Thomas Prest (3)
- Oded Regev (2)
- Alon Rosen (1)
- Christian Schaffner (1)
- Peter Schwabe (1)
- Gil Segev (1)
- Gregor Seiler (5)
- Damien Stehlé (1)
- Mehdi Tibouchi (2)
- Vinod Vaikuntanathan (1)
- Daniel Wichs (2)