## CryptoDB

### Daniele Micciancio

#### Affiliation: University of California, San Diego

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

On the Security of Homomorphic Encryption on Approximate Numbers
Abstract

We present passive attacks against CKKS, the homomorphic encryption
scheme for arithmetic on approximate numbers presented at
Asiacrypt 2017. The attack is both theoretically efficient
(running in expected polynomial time)
and very practical, leading to complete key recovery with high probability
and very modest running times.
We implemented and tested the attack against major open source
homomorphic encryption libraries, including HEAAN, SEAL, HElib and
PALISADE, and when computing several functions that often arise in applications of the
CKKS scheme to machine learning on encrypted data, like mean and variance computations,
and approximation of logistic and exponential functions using their Maclaurin series.
The attack shows that the traditional formulation of IND-CPA security
(or indistinguishability against chosen plaintext attacks)
achieved by CKKS does not adequately captures security against passive
adversaries when applied to approximate encryption schemes,
and that a different, stronger definition is required to evaluate
the security of such schemes.
We provide a solid theoretical basis for the security evaluation of homomorphic
encryption on approximate numbers (against passive attacks)
by proposing new definitions, that
naturally extend the traditional notion of IND-CPA security to the approximate
computation setting.
We propose both indistinguishability-based and simulation-based variants,
as well as restricted versions of the definitions that limit the order and number
of adversarial queries (as may be enforced by some applications).
We prove implications and separations among different definitional variants,
and discuss possible modifications to CKKS that may serve as a countermeasure to our
attacks.

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.

2020

ASIACRYPT

Simpler Statistically Sender Private Oblivious Transfer from Ideals of Cyclotomic Integers
📺
Abstract

We present a two-message oblivious transfer protocol achieving statistical sender privacy and computational receiver privacy based on the RLWE assumption for cyclotomic number fields. This work improves upon prior lattice-based statistically sender-private oblivious transfer protocols by reducing the total communication between parties by a factor O(nlogq) for transfer of length O(n) messages.
Prior work of Brakerski and Dottling uses transference theorems to show that either a lattice or its dual must have short vectors, the existence of which guarantees lossy encryption for encodings with respect to that lattice, and therefore statistical sender privacy. In the case of ideal lattices from embeddings of cyclotomic integers, the existence of one short vector implies the existence of many, and therefore encryption with respect to either a lattice or its dual is guaranteed to ``lose" more information about the message than can be ensured in the case of general lattices. This additional structure of ideals of cyclotomic integers allows for efficiency improvements beyond those that are typical when moving from the generic to ideal lattice setting, resulting in smaller message sizes for sender and receiver, as well as a protocol that is simpler to describe and analyze.

2019

EUROCRYPT

Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More
📺
Abstract

Many advanced lattice cryptography applications require efficient algorithms for inverting the so-called “gadget” matrices, which are used to formally describe a digit decomposition problem that produces an output with specific (statistical) properties. The common gadget inversion problems are the classical (often binary) digit decomposition, subgaussian decomposition, Learning with Errors (LWE) decoding, and discrete Gaussian sampling. In this work, we build and implement an efficient lattice gadget toolkit that provides a general treatment of gadget matrices and algorithms for their inversion/sampling. The main contribution of our work is a set of new gadget matrices and algorithms for efficient subgaussian sampling that have a number of major theoretical and practical advantages over previously known algorithms. Another contribution deals with efficient algorithms for LWE decoding and discrete Gaussian sampling in the Residue Number System (RNS) representation.We implement the gadget toolkit in PALISADE and evaluate the performance of our algorithms both in terms of runtime and noise growth. We illustrate the improvements due to our algorithms by implementing a concrete complex application, key-policy attribute-based encryption (KP-ABE), which was previously considered impractical for CPU systems (except for a very small number of attributes). Our runtime improvements for the main bottleneck operation based on subgaussian sampling range from 18x (for 2 attributes) to 289x (for 16 attributes; the maximum number supported by a previous implementation). Our results are applicable to a wide range of other advanced applications in lattice cryptography, such as GSW-based homomorphic encryption schemes, leveled fully homomorphic signatures, other forms of ABE, some program obfuscation constructions, and more.

2019

EUROCRYPT

Symbolic Encryption with Pseudorandom Keys
📺
Abstract

We give an efficient decision procedure that, on input two (acyclic) expressions making arbitrary use of common cryptographic primitives (namely, encryption and pseudorandom generators), determines (in polynomial time) if the two expressions produce computationally indistinguishable distributions for any cryptographic instantiation satisfying the standard security notions of pseudorandomness and indistinguishability under chosen plaintext attack. The procedure works by mapping each expression to a symbolic pattern that captures, in a fully abstract way, the information revealed by the expression to a computationally bounded observer. Our main result shows that if two expressions are mapped to different symbolic patterns, then there are secure pseudorandom generators and encryption schemes for which the two distributions can be distinguished with overwhelming advantage. At the same time if any two (acyclic) expressions are mapped to the same pattern, then the associated distributions are indistinguishable.

2019

ASIACRYPT

Homomorphic Encryption for Finite Automata
Abstract

We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme from LWE, instead we reduce it from a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

2018

PKC

Equational Security Proofs of Oblivious Transfer Protocols
Abstract

We exemplify and evaluate the use of the equational framework of Micciancio and Tessaro (ITCS 2013) by analyzing a number of concrete Oblivious Transfer protocols: a classic OT transformation to increase the message size, and the recent (so called “simplest”) OT protocol in the random oracle model of Chou and Orlandi (Latincrypt 2015), together with some simple variants. Our analysis uncovers subtle timing bugs or shortcomings in both protocols, or the OT definition typically employed when using them. In the case of the OT length extension transformation, we show that the protocol can be formally proved secure using a revised OT definition and a simple protocol modification. In the case of the “simplest” OT protocol, we show that it cannot be proved secure according to either the original or revised OT definition, in the sense that for any candidate simulator (expressible in the equational framework) there is an environment that distinguishes the real from the ideal system.

2005

EPRINT

Concurrent Zero Knowledge without Complexity Assumptions
Abstract

We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices.
For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have \tilde{O}(log n) rounds, which is known to be essentially optimal for black-box simulation.
To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

2004

EPRINT

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions
Abstract

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 + ... + a_m*x_m = b. We consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when R = Z is the ring of the integers) can be easily solved in polynomial time even in the worst case. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = omega(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n^{1+epsilon} almost linear in the dimension of the lattice.
Our results yield very efficient and provably secure one-way functions (based on worst-case complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.

2003

EUROCRYPT

2002

ASIACRYPT

2002

EPRINT

Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol
Abstract

We show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verifier via
black box simulation. By efficient we mean that our transformation incurs only an additive overhead, both in terms of the number of rounds and the computational and communication complexity of each round, independently of the complexity of the original protocol. Moreover, the transformation preserves (up to negligible additive terms) the soundness and completeness error probabilities. The new proof system is proved secure based on the Decisional Diffie-Hellman (DDH) assumption, in the standard model of computation, i.e., no random oracles, shared random strings, or public key infrastructure is assumed. In addition to the introduction of a practical protocol, this construction provides yet another example of ideas in plausibility results that turn into ideas in the construction of practical protocols.
We prove our main result by developing a mechanism for simulatable commitments that may be of independent interest. In particular, it allows a weaker result that is interesting as well. We present
an efficient transformation of any honest verifier public-coin
computational zero-knowledge proof into a (public coin) computational zero-knowledge proof secure against any verifier. The overhead of this second transformation is minimal: we only increase the number of rounds by 3, and increase the computational cost by 2 public key operations for each round of the original protocol. The cost of the more general transformation leading to concurrent zero knowledge is also close to optimal (for black box simulation), requiring only omega(log n) additional rounds (where n is a security parameter and omega(log n) can be any superlogarithmic function of n (e.g.,
log(n)log^*(n)), and omega(log n) additional public key operations for each round of the original protocol.

2001

EPRINT

Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures
Abstract

Forward-secure digital signatures, initially proposed by Anderson in
CCS 97 and formalized by Bellare and Miner in Crypto 99, are signature
schemes which enjoy the additional guarantee that a compromise of the
secret key at some point in time does not help forge signatures
allegedly signed in an earlier time period. Consequently, if the
secret key is lost, then the key can be safely revoked without
invalidating previously-issued signatures. Since the introduction of
the concept, several forward-secure signature schemes have been
proposed, with varying performance both in terms of space and time.
Which scheme is most useful in practice typically depends on the
requirements of the specific application.
In this paper we propose and study some general composition operations
that can be used to combine existing signature schemes (whether
forward-secure or not) into new forward-secure signature schemes. Our
schemes offer interesting trade-offs between the various efficiency
parameters, achieving a greater flexibility in accommodating the
requirements of different applications. As an extension of our
techniques, we also construct the first efficient forward-secure
signature scheme where the total number of time periods for which the
public key is used does not have to be fixed in advance. The scheme
can be used for practically unbounded time, and the performance
depends (minimally) only on the time elapsed so far.
Our scheme achieves excellent performance overall, is very competitive
with previous schemes with respect to all parameters, and outperforms
each of the previous schemes in at least one parameter. Moreover, the
scheme can be based on any underlying digital signature scheme, and
does not rely on specific assumptions. Its forward security is proven
in the standard model, without using a random oracle.

1999

EPRINT

Lattice Based Cryptography: A Global Improvement
Abstract

We describe a general technique to simplify as well as to improve
several lattice based cryptographic protocols.
The technique is rather straightforward and is easily applied to
the protocols, and gives both a simpler analysis and better
performance than the original protocols. The improvement is global:
the modified protocols are simpler, faster, require less storage,
use less bandwidth and need less random bits than the originals.
Moreover, the improvement is achieved without any loss in security:
we formally prove that the modified protocols are at least as secure
as the original ones. In fact, the modified protocols might even
be more secure as the adversary gets less information. We exemplify
our technique on the Goldreich-Goldwasser zero-knowledge proof systems
for lattice problems and the GGH public key cryptosystem.

1998

EPRINT

An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products
Abstract

We present efficient zero-knowledge proof systems for quasi-safe
prime products and other related languages. Quasi-safe primes are a
relaxation of safe primes, a class of prime numbers useful in many
cryptographic applications.
Our proof systems achieve higher security and better
efficiency than all previously known ones.
In particular, all our proof systems are perfect or statistical
zero-knowledge, meaning that even a computationally
unbounded adversary cannot extract any information
from the proofs.
Moreover, our proof systems are extremely efficient because they do
not use general reductions to NP-complete problems, can be easily
parallelized preserving zero-knowledge, and are non-interactive for
computationally unbounded provers. The prover can also be efficiently
implemented given some trapdoor information and using very little
interaction.
We demonstrate the applicability of quasi-safe primes
by showing how they can be effectively used in the
context of RSA based undeniable signatures to enforce
the use of ``good'' public keys, i.e.,
keys such that if a signer can convince a recipient
of the validity of a signature, then he won't be able to
subsequently deny the same signature in case of a dispute.

1997

EPRINT

A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost
Abstract

We present a simple, new paradigm for the design of collision-free hash
functions. Any function emanating from this paradigm is <i>incremental.</i>
(This means that if a message x which I have previously hashed is modified to
x' then rather than having to re-compute the hash of x' from scratch, I
can quickly ``update'' the old hash value to the new one, in time proportional
to the amount of modification made in x to get x'.) Also any function
emanating from this paradigm is parallelizable, useful for hardware
implementation.

#### Program Committees

- Crypto 2020
- Crypto 2019
- Crypto 2018
- Crypto 2015
- Eurocrypt 2013
- Crypto 2012
- TCC 2012
- Crypto 2011
- TCC 2010
- TCC 2009
- Crypto 2006
- TCC 2006
- TCC 2004
- Eurocrypt 2004
- Crypto 2004

#### Coauthors

- Mihir Bellare (4)
- Léo Ducas (3)
- Nicholas Genise (4)
- Rosario Gennaro (2)
- Craig Gentry (1)
- Shafi Goldwasser (1)
- Shai Halevi (1)
- Alejandro Hevia (1)
- Baiyu Li (4)
- Vadim Lyubashevsky (4)
- Tal Malkin (2)
- Sara K. Miner (2)
- Petros Mol (1)
- Shien Jin Ong (2)
- Saurabh Panjwani (2)
- Chris Peikert (4)
- Erez Petrank (2)
- Yuriy Polyakov (1)
- Tal Rabin (1)
- Alon Rosen (1)
- Amit Sahai (2)
- Jessica Sorrell (1)
- Salil P. Vadhan (3)
- Michael Walter (5)
- Bogdan Warinschi (2)
- Scott Yilek (1)