## CryptoDB

### Chris Peikert

#### ORCID: 0000-0003-0419-7501

#### Publications

**Year**

**Venue**

**Title**

2024

CRYPTO

Cryptanalysis of Lattice-Based Sequentiality Assumptions and Proofs of Sequential Work
Abstract

This work \emph{completely breaks} the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023.
In addition, it breaks an essentially identical variant of the PoSW, which differs from the original in only an arbitrary choice that is immaterial to the design and security proof (under the falsified assumption).
This suggests that whatever security the original PoSW may have is fragile, and further motivates the search for a construction based on a sound lattice-based assumption.
Specifically, for sequentiality parameter~$T$ and SIS parameters $n,q,m = n \log q$, the attack on the sequentiality assumption finds a solution of quasipolynomial norm $m^{\lceil{\log T}\rceil}$ (or norm $O(\sqrt{m})^{\lceil{\log T}\rceil}$ with high probability) in only \emph{logarithmic} $\tilde{O}_{n,q}(\log T)$ depth; this strongly falsifies the assumption that finding such a solution requires depth \emph{linear} in~$T$.
(The $\tilde{O}$ notation hides polylogarithmic factors in the variables appearing in its subscript.)
Alternatively, the attack finds a solution of polynomial norm $m^{1/\varepsilon}$ in depth $\tilde{O}_{n,q}(T^{\varepsilon})$, for any constant $\varepsilon > 0$.
Similarly, the attack on the (slightly modified) PoSW constructs a valid proof in \emph{polylogarithmic} $\tilde{O}_{n,q}(\log^2 T)$ depth, thus strongly falsifying the expectation that doing so requires linear sequential work.

2023

EUROCRYPT

Functional Commitments for All Functions, with Transparent Setup and from SIS
Abstract

A *functional commitment* scheme enables a user to concisely
commit to a function from a specified family, then later concisely
and verifiably reveal values of the function at desired inputs. Useful
special cases, which have seen applications across cryptography,
include vector commitments and polynomial commitments.
To date, functional commitments have been constructed (under
falsifiable assumptions) only for functions that are essentially
*linear*, with one recent exception that works for arbitrarily
complex functions. However, that scheme operates in a strong and
non-standard model, requiring an online, trusted authority to generate
special keys for any opened function inputs.
In this work, we give the first functional commitment scheme for
nonlinear functions---indeed, for *all functions* of any bounded
complexity---under a standard setup and a falsifiable assumption.
Specifically, the setup is ``transparent,'' requiring only public
randomness (and not any trusted entity), and the assumption is the
hardness of the standard Short Integer Solution~(SIS) lattice problem.
Our construction also has other attractive features, including:
*stateless updates* via generic composability; excellent
*asymptotic efficiency* for the verifier, and also for the
committer in important special cases like vector and polynomial
commitments, via preprocessing; and *post-quantum security*, since it is based on SIS.

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.

2009

CRYPTO

#### Program Committees

- Eurocrypt 2023
- Crypto 2021 (Program chair)
- Crypto 2021
- Crypto 2020
- Crypto 2019
- TCC 2018
- Eurocrypt 2017
- TCC 2017
- PKC 2015
- TCC 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 (3)
- Benny Applebaum (1)
- Abhishek Banerjee (4)
- Mihir Bellare (1)
- Hai Brenner (1)
- David Cash (3)
- Ronald Cramer (1)
- Leo de Castro (1)
- Yevgeniy Dodis (1)
- Léo Ducas (1)
- Georg Fuchsbauer (1)
- Nicholas Genise (1)
- Craig Gentry (1)
- 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)
- Chris Peikert (43)
- Zachary Pepin (3)
- Krzysztof Pietrzak (1)
- Oded Regev (3)
- Alon Rosen (5)
- Amit Sahai (2)
- Chad Sharp (1)
- Sina Shiehian (4)
- Adam Smith (1)
- Noah Stephens-Davidowitz (1)
- Sophie Stevens (1)
- Madhu Sudan (1)
- Yi Tang (1)
- Vinod Vaikuntanathan (3)
- Michael Walter (1)
- Brent Waters (3)
- David A. Wilson (1)