## CryptoDB

### Daniele Micciancio

#### 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.

2003

EUROCRYPT

2002

ASIACRYPT

#### Program Committees

- Crypto 2022
- Crypto 2020 (Program chair)
- Crypto 2019 (Program chair)
- Crypto 2018
- Crypto 2015
- Eurocrypt 2013
- Crypto 2012
- TCC 2012
- Crypto 2011
- TCC 2010 (Program chair)
- TCC 2009
- Crypto 2006
- TCC 2006
- TCC 2004
- Eurocrypt 2004
- Crypto 2004

#### Coauthors

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