## CryptoDB

### Chris Peikert

#### Affiliation: University of Michigan--Ann Arbor

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors
📺
Abstract

We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al. [EUROCRYPT’18], Holmgren and Lombardi [FOCS’18], and Canetti et al. [STOC’19] for soundly applying the Fiat–Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on “exotic” assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness.Our main technical contribution is a hash family that is correlation intractable for arbitrary size-S circuits, for any polynomially bounded S, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a “bootstrapping” transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible “modes,” yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

2019

TCC

Algebraically Structured LWE, Revisited
Abstract

In recent years, there has been a proliferation of algebraically structured Learning With Errors (LWE) variants, including Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, and Middle-Product LWE, and a web of reductions to support their hardness, both among these problems themselves and from related worst-case problems on structured lattices. However, these reductions are often difficult to interpret and use, due to the complexity of their parameters and analysis, and most especially their (frequently large) blowup and distortion of the error distributions.In this paper we unify and simplify this line of work. First, we give a general framework that encompasses all proposed LWE variants (over commutative base rings), and in particular unifies all prior “algebraic” LWE variants defined over number fields. We then use this framework to give much simpler, more general, and tighter reductions from Ring-LWE to other algebraic LWE variants, including Module-LWE, Order-LWE, and Middle-Product LWE. In particular, all of our reductions have easy-to-analyze and frequently small error expansion; in some cases they even leave the error unchanged. A main message of our work is that it is straightforward to use the hardness of the original Ring-LWE problem as a foundation for the hardness of all other algebraic LWE problems defined over number fields, via simple and rather tight reductions.

2018

PKC

New (and Old) Proof Systems for Lattice Problems
Abstract

We continue the study of statistical zero-knowledge (SZK) proofs, both interactive and noninteractive, for computational problems on point lattices. We are particularly interested in the problem $$\textsf {GapSPP}$$GapSPP of approximating the $$\varepsilon $$ε-smoothing parameter (for some $$\varepsilon < 1/2$$ε<1/2) of an n-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and $$\textsf {GapSPP}$$GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that $$\textsf {GapSPP}$$GapSPP admits SZK proofs for remarkably low approximation factors, improving on prior work by up to roughly $$\sqrt{n}$$n. Specifically:There is a noninteractive SZK proof for $$O(\log (n) \sqrt{\log (1/\varepsilon )})$$O(log(n)log(1/ε))-approximate $$\textsf {GapSPP}$$GapSPP. Moreover, for any negligible $$\varepsilon $$ε and a larger approximation factor $$\widetilde{O}(\sqrt{n \log (1/\varepsilon )})$$O~(nlog(1/ε)), there is such a proof with an efficient prover.There is an (interactive) SZK proof with an efficient prover for $$O(\log n + \sqrt{\log (1/\varepsilon )/\log n})$$O(logn+log(1/ε)/logn)-approximate coGapSPP. We show this by proving that $$O(\log n)$$O(logn)-approximate $$\textsf {GapSPP}$$GapSPP is in $$\mathsf {coNP} $$coNP.
In addition, we give an (interactive) SZK proof with an efficient prover for approximating the lattice covering radius to within an $$O(\sqrt{n})$$O(n) factor, improving upon the prior best factor of $$\omega (\sqrt{n \log n})$$ω(nlogn).

2018

PKC

Privately Constraining and Programming PRFs, the LWE Way
Abstract

Constrained pseudorandom functions allow for delegating “constrained” secret keys that let one compute the function at certain authorized inputs—as specified by a constraining predicate—while keeping the function value at unauthorized inputs pseudorandom. In the constraint-hiding variant, the constrained key hides the predicate. On top of this, programmable variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs.Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors (LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC’17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC’17].In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $$\exp (n^{\varepsilon })$$exp(nε) approximation factors. Our constructions follow straightforwardly from a new notion we call a shift-hiding shiftable function, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.

2015

JOFC

2012

JOFC

Bonsai Trees, or How to Delegate a Lattice Basis
Abstract

We introduce a new lattice-based cryptographic structure called a bonsai tree, and use it to resolve some important open problems in the area. Applications of bonsai trees include an efficient, stateless ‘hash-and-sign’ signature scheme in the standard model (i.e., no random oracles), and the first hierarchical identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.

2010

EPRINT

An Efficient and Parallel Gaussian Sampler for Lattices
Abstract

At the heart of many recent lattice-based cryptographic schemes is a
polynomial-time algorithm that, given a `high-quality' basis,
generates a lattice point according to a Gaussian-like distribution.
Unlike most other operations in lattice-based cryptography, however,
the known algorithm for this task (due to Gentry, Peikert, and
Vaikuntanathan; STOC 2008) is rather inefficient, and is inherently
sequential.
We present a new Gaussian sampling algorithm for lattices that is
\emph{efficient} and \emph{highly parallelizable}. We also show that
in most cryptographic applications, the algorithm's efficiency comes
at almost no cost in asymptotic security. At a high level, our
algorithm resembles the ``perturbation'' heuristic proposed as part of
NTRUSign (Hoffstein \etal, CT-RSA 2003), though the details are quite
different. To our knowledge, this is the first algorithm and rigorous
analysis demonstrating the security of a perturbation-like technique.

2009

CRYPTO

2008

EPRINT

Generating Shorter Bases for Hard Random Lattices
Abstract

We revisit the problem of generating a ``hard'' random lattice
together with a basis of relatively short vectors. This problem has
gained in importance lately due to new cryptographic schemes that use
such a procedure for generating public/secret key pairs. In these
applications, a shorter basis directly corresponds to milder
underlying complexity assumptions and smaller key sizes.
The contributions of this work are twofold. First, using the
\emph{Hermite normal form} as an organizing principle, we simplify and
generalize an approach due to Ajtai (ICALP 1999). Second, we improve
the construction and its analysis in several ways, most notably by
tightening the length of the output basis essentially to the optimum
value.

2008

EPRINT

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Abstract

We construct public-key cryptosystems that are secure assuming the
\emph{worst-case} hardness of approximating the length of a shortest
nonzero vector in an $n$-dimensional lattice to within a small
$\poly(n)$ factor. Prior cryptosystems with worst-case connections
were based either on the shortest vector problem for a \emph{special
class} of lattices (Ajtai and Dwork, STOC 1997; Regev, J.~ACM 2004),
or on the conjectured hardness of lattice problems for \emph{quantum}
algorithms (Regev, STOC 2005).
Our main technical innovation is a reduction from certain variants of
the shortest vector problem to corresponding versions of the
``learning with errors'' ($\lwe$) problem; previously, only a
\emph{quantum} reduction of this kind was known. In addition, we
construct new cryptosystems based on the \emph{search} version of
$\lwe$, including a very natural \emph{chosen ciphertext-secure}
system that has a much simpler description and tighter underlying
worst-case approximation factor than prior constructions.

2007

EPRINT

Lossy Trapdoor Functions and Their Applications
Abstract

We propose a new general primitive called lossy trapdoor
functions (lossy TDFs), and realize it under a variety of different
number theoretic assumptions, including hardness of the decisional
Diffie-Hellman (DDH) problem and the worst-case hardness of
standard lattice problems.
Using lossy TDFs, we develop a new approach for constructing many
important cryptographic primitives, including standard trapdoor
functions, CCA-secure cryptosystems, collision-resistant hash
functions, and more. All of our constructions are simple, efficient,
and black-box.
Taken all together, these results resolve some long-standing open
problems in cryptography. They give the first known (injective)
trapdoor functions based on problems not directly related to integer
factorization, and provide the first known CCA-secure cryptosystem
based solely on worst-case lattice assumptions.

2007

EPRINT

A Framework for Efficient and Composable Oblivious Transfer
Abstract

We propose and simple, general, and unified framework for constructing
oblivious transfer (OT) protocols that are \emph{efficient},
\emph{universally composable}, and \emph{generally realizable} from a
variety of standard number-theoretic assumptions, such as the
decisional Diffie-Hellman assumption and the Quadratic Residuosity
assumption. Most interestingly, we can also instantiate our framework
with \emph{worst-case} complexity assumptions relating to
\emph{lattices}.
Our OT protocols are round-optimal (one message each way), efficient
in the parties' communication and local computation, and use only one
reference string for an unbounded number of executions. Furthermore,
the protocols can provide \emph{unconditional} security to either the
sender or receiver, simply by changing the distribution of the
reference string. (For several versions of the protocol, even a
common \emph{random} string suffices.)
One of our key technical contributions is a simple and novel
abstraction that we call a \emph{dual-mode} cryptosystem. We
implement dual-mode cryptosystems by taking a unified view of several
cryptosystems in the literature that have what we call
``message-lossy'' public keys, whose defining property is that a
ciphertext produced under such a key carries \emph{no information}
(even statistically) about the encrypted message.
As a contribution of independent interest, we also provide a multi-bit
version of Regev's lattice-based cryptosystem (STOC 2005) whose time
and space efficiency are improved by a linear factor. In particular,
the amortized runtime per message bit is only $\tilde{O}(n)$ bit
operations, and the ciphertext expansion can be made as small as a
constant.

2007

EPRINT

Trapdoors for Hard Lattices and New Cryptographic Constructions
Abstract

We show how to construct a variety of ``trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient ``hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, and identity-based
encryption.
A core technical component of our constructions is an efficient
algorithm that, given a basis of an arbitrary lattice, samples lattice
points from a Gaussian-like probability distribution whose standard
deviation is essentially the length of the longest vector in the
basis. In particular, the crucial security property is that the
output distribution of the algorithm is oblivious to the particular
geometry of the given basis.

2006

EPRINT

Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors
Abstract

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)
= O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.
To obtain our results, we focus on families of lattices having
special algebraic structure. Specifically, we consider lattices
that correspond to \emph{ideals} in the ring of integers of an
algebraic number field. The worst-case assumption we rely on is
that in some $\ell_p$ length, it is hard to find approximate
shortest vectors in these lattices, under an appropriate form of
preprocessing of the number field. Our results build upon prior
works by Micciancio (FOCS 2002), Peikert and Rosen (TCC 2006), and
Lyubashevsky and Micciancio (ICALP 2006).
For the connection factors $\gamma(n)$ we achieve, the corresponding
\emph{decisional} promise problems on ideal lattices are \emph{not}
known to be NP-hard; in fact, they are in P. However, the
\emph{search} approximation problems still appear to be very hard.
Indeed, ideal lattices are well-studied objects in computational
number theory, and the best known algorithms for them seem to
perform \emph{no better} than the best known algorithms for general
lattices.
To obtain the best possible connection factor, we instantiate our
constructions with infinite families of number fields having
constant \emph{root discriminant}. Such families are known to exist
and are computable, though no efficient construction is yet known.
Our work motivates the search for such constructions. Even
constructions of number fields having root discriminant up to
$O(n^{2/3-\epsilon})$ would yield connection factors better than the
current best of~$\tilde{O}(n)$.

2005

EPRINT

On Error Correction in the Exponent
Abstract

Given a corrupted word $\w = (w_1, \ldots, w_n)$ from a Reed-Solomon
code of distance $d$, there are many ways to efficiently find and
correct its errors. But what if we are instead given $(g^{w_1},
\ldots, g^{w_n})$ where $g$ generates some large cyclic group ---
can the errors still be corrected efficiently? This problem is
called \emph{error correction in the exponent}, and though it arises
naturally in many areas of cryptography, it has received little
attention.
We first show that \emph{unique decoding} and \emph{list
decoding} in the exponent are no harder than the computational
Diffie-Hellman (CDH) problem in the same group. The remainder of
our results are negative:
* Under mild assumptions on the parameters, we show that
\emph{bounded-distance decoding} in the exponent, under
$e=d-k^{1-\epsilon}$ errors for any $\epsilon > 0$, is as hard as
the discrete logarithm problem in the same group.
* For \emph{generic} algorithms (as defined by Shoup, Eurocrypt
1997) that treat the group as a ``black-box,'' we show lower
bounds for decoding that exactly match known algorithms.
Our generic lower bounds also extend to decisional variants of the
decoding problem, and to groups in which the decisional
Diffie-Hellman (DDH) problem is easy. This suggests that hardness
of decoding in the exponent is a qualitatively new assumption that
lies ``between'' the DDH and CDH assumptions.

#### Program Committees

- Crypto 2019
- TCC 2018
- Eurocrypt 2017
- TCC 2017
- TCC 2015
- PKC 2015
- Crypto 2014
- TCC 2014
- PKC 2013
- Crypto 2012
- TCC 2011
- Asiacrypt 2011
- Eurocrypt 2011
- Crypto 2009
- TCC 2008

#### Coauthors

- Navid Alamati (2)
- Jacob Alperin-Sheriff (4)
- Joël Alwen (1)
- Benny Applebaum (1)
- Abhishek Banerjee (6)
- Mihir Bellare (1)
- Hai Brenner (1)
- David Cash (3)
- Ronald Cramer (2)
- Yevgeniy Dodis (1)
- Léo Ducas (2)
- Georg Fuchsbauer (2)
- Craig Gentry (2)
- Shafi Goldwasser (1)
- Jens Groth (1)
- Dennis Hofheinz (2)
- Yuval Ishai (1)
- Yael Tauman Kalai (1)
- Eike Kiltz (3)
- Gaëtan Leurent (1)
- Anna Lysyanskaya (1)
- Vadim Lyubashevsky (3)
- Silvio Micali (1)
- Daniele Micciancio (3)
- Adam O'Neill (1)
- Zachary Pepin (1)
- Krzysztof Pietrzak (2)
- Oded Regev (4)
- Alon Rosen (6)
- Amit Sahai (2)
- Sina Shiehian (3)
- Adam Smith (1)
- Noah Stephens-Davidowitz (1)
- Sophie Stevens (2)
- Madhu Sudan (1)
- Vinod Vaikuntanathan (5)
- Brent Waters (5)
- David A. Wilson (1)