## CryptoDB

### Chris Peikert

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Vector and Functional Commitments from Lattices
📺
Abstract

Vector commitment (VC) schemes allow one to commit concisely to an
ordered sequence of values, so that the values at desired positions
can later be proved concisely. In addition, a VC can be statelessly
updatable, meaning that commitments and proofs can be updated to
reflect changes to individual entries, using knowledge of just those
changes (and not the entire vector). VCs have found important
applications in verifiable outsourced databases, cryptographic
accumulators, and cryptocurrencies. However, to date there have been
relatively few post-quantum constructions, i.e., ones that are
plausibly secure against quantum attacks.
More generally, functional commitment (FC) schemes allow one to
concisely and verifiably reveal various functions of committed data,
such as linear functions (i.e., inner products, including evaluations
of a committed polynomial). Under falsifiable assumptions, all known
functional commitments schemes have been limited to ``linearizable''
functions, and there are no known post-quantum FC schemes beyond
ordinary VCs.
In this work we give post-quantum constructions of vector and
functional commitments based on the standard Short Integer Solution
lattice problem (appropriately parameterized):
\begin{itemize}
\item First, we present new statelessly updatable VCs with
significantly shorter proofs than (and efficiency otherwise similar
to) the only prior post-quantum, statelessly updatable construction
(Papamanthou \etal, EUROCRYPT 13). Our constructions use private-key
setup, in which an authority generates public parameters and then
goes offline.
\item Second, we construct functional commitments for \emph{arbitrary
(bounded) Boolean circuits} and branching programs. Under
falsifiable assumptions, this is the first post-quantum FC scheme
beyond ordinary VCs, and the first FC scheme of any kind that goes
beyond linearizable functions. Our construction works in a new model
involving an authority that generates the public parameters and
remains online to provide public, reusable ``opening keys'' for
desired functions of committed messages.
\end{itemize}

2020

EUROCRYPT

He Gives C-Sieves on the CSIDH
📺
Abstract

Recently, Castryck, Lange, Martindale, Panny, and Renes proposed
\emph{CSIDH} (pronounced ``sea-side'') as a candidate post-quantum
``commutative group action.'' It has attracted much attention and
interest, in part because it enables noninteractive
Diffie--Hellman-like key exchange with quite small
communication. Subsequently, CSIDH has also been used as a foundation
for digital signatures.
In 2003--04, Kuperberg and then Regev gave asymptotically
subexponential quantum algorithms for ``hidden shift'' problems, which
can be used to recover the CSIDH secret key from a public key. In
late 2011, Kuperberg gave a follow-up quantum algorithm called the
\emph{collimation sieve} (``c-sieve'' for short), which improves the
prior ones, in particular by using exponentially less quantum memory
and offering more parameter tradeoffs. While recent works have
analyzed the concrete cost of the original algorithms (and variants)
against CSIDH, nothing of this nature was previously available for the
c-sieve.
This work fills that gap. Specifically, we generalize Kuperberg's
collimation sieve to work for arbitrary finite cyclic groups, provide
some practical efficiency improvements, give a classical (i.e.,
non-quantum) simulator, run experiments for a wide range of parameters
up to the actual CSIDH-512 group order, and concretely quantify the
complexity of the c-sieve against CSIDH.
Our main conclusion is that the proposed CSIDH parameters provide
relatively little quantum security beyond what is given by the cost of
quantumly evaluating the CSIDH group action itself (on a uniform
superposition). For example, the cost of CSIDH-512 key recovery is
only about~$2^{16}$ quantum evaluations using~$2^{40}$ bits of
quantumly accessible \emph{classical} memory (plus relatively small
other resources). This improves upon a prior estimate of~$2^{32.5}$
evaluations and~$2^{31}$ qubits of \emph{quantum} memory, for a
variant of Kuperberg's original sieve.
Under the plausible assumption that quantum evaluation does not cost
much more than what is given by a recent ``best case'' analysis,
CSIDH-512 can therefore be broken using significantly less
than~$2^{64}$ quantum T-gates. This strongly invalidates its claimed
NIST level~1 quantum security, especially when accounting for the
MAXDEPTH restriction. Moreover, under analogous assumptions for
CSIDH-1024 and -1792, which target higher NIST security levels, except
near the high end of the MAXDEPTH range even these instantiations fall
short of level~1.

2020

PKC

Constraining and Watermarking PRFs from Milder Assumptions
📺
Abstract

Constrained pseudorandom functions (C-PRFs) let the possessor of a secret key delegate the ability to evaluate the function on certain authorized inputs, while keeping the remaining function values pseudorandom. A constraint-hiding constrained PRF (CHC-PRF) additionally conceals the predicate that determines which inputs are authorized. These primitives have a wealth of applications, including watermarking schemes, symmetric deniable encryption, and updatable garbled circuits. Recent works have constructed (CH)C-PRFs from rather aggressive parameterizations of Learning With Errors (LWE) with subexponential modulus-noise ratios, even for relatively simple “puncturing” or $$ ext {NC}^{1}$$ circuit constraints. This corresponds to strong lattice assumptions and inefficient constructions, and stands in contrast to LWE-based unconstrained PRFs and fully homomorphic encryption schemes, which can be based on quasi-polynomial or even (nearly) polynomial modulus-noise ratios. In this work we considerably improve the LWE assumptions needed for building (constraint-hiding) constrained PRFs and watermarking schemes. In particular, for CHC-PRFs and related watermarking schemes we improve the modulus-noise ratio to $$lambda ^{O((d+log lambda ) log lambda )}$$ for depth- d circuit constraints, which is merely quasi-polynomial for $$ ext {NC}^{1}$$ circuits and closely related watermarking schemes. For (constraint-revealing) C-PRFs for $$ ext {NC}^{1}$$ we do even better, obtaining a nearly polynomial $$lambda ^{omega (1)}$$ ratio. These improvements are partly enabled by slightly modifying the definition of C-PRFs, in a way that is still compatible with many of their applications. Finally, as a contribution of independent interest we build CHC-PRFs for special constraint classes from generic , weaker assumptions: we obtain bit-fixing constraints based on the minimal assumption of one-way functions, and hyperplane-membership constraints based on key-homomorphic PRFs.

2020

PKC

Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
📺
Abstract

Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend. In this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach. As a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems.

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 2020
- Crypto 2019
- TCC 2018
- TCC 2017
- Eurocrypt 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)
- Nicholas Genise (1)
- 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 (4)
- Adam O'Neill (1)
- Zachary Pepin (2)
- Krzysztof Pietrzak (2)
- Oded Regev (4)
- Alon Rosen (6)
- Amit Sahai (2)
- Chad Sharp (1)
- Sina Shiehian (4)
- Adam Smith (1)
- Noah Stephens-Davidowitz (1)
- Sophie Stevens (2)
- Madhu Sudan (1)
- Vinod Vaikuntanathan (5)
- Michael Walter (1)
- Brent Waters (5)
- David A. Wilson (1)