## CryptoDB

### Daniele Micciancio

#### ORCID: 0000-0003-3323-9985

#### Publications

**Year**

**Venue**

**Title**

2024

PKC

SoK: Learning With Errors, Circular Security, and Fully Homomorphic Encryption
Abstract

All known constructions of fully homomorphic encryption (FHE) schemes from the learning with errors (LWE) assumption require the encryption schemes to be circular secure.
A long-standing open problem in the study of FHE schemes is to demonstrate evidence for their circular security. In this work, we systematize the flavors of circular security required for a number of FHE constructions, formulate circular security conjectures, show search-to-decision reductions for them, and pose several open problems.

2024

PKC

Faster Amortized FHEW bootstrapping using Ring Automorphisms
Abstract

Amortized bootstrapping offers a way to simultaneously refresh many
ciphertexts of a fully homomorphic encryption scheme,
at a total cost comparable to that of refreshing a single ciphertext.
An amortization method for FHEW-style cryptosystems
was first proposed by (Micciancio and Sorrell, ICALP 2018),
who showed that the amortized cost of bootstrapping $n$ FHEW-style
ciphertexts can be reduced from $\tilde O(n)$ basic cryptographic operations
to just $\tilde O(n^{\epsilon})$, for any constant $\epsilon>0$.
However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the
asymptotic notation.
In this work, we propose an alternative amortized boostrapping method with
much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost,
but with a hidden constant that is only linear in $1/\epsilon$, and with reduced
noise growth.
This is achieved following the general strategy of (Micciancio and Sorrell),
but replacing their use of the Nussbaumer transform, with a much more practical
Number Theoretic Transform, with multiplication by twiddle factors implemented
using ring automorphisms.
A key technical ingredient to do this is a new ``scheme switching''
technique proposed in this paper which may be of independent interest.

2024

CRYPTO

Hintless Single-Server Private Information Retrieval
Abstract

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-dependent information.
Our first construction (HintlessPIR) eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the ``hint'' related computation to the server, leveraging a new concept of \emph{homomorphic encryption with composable preprocessing}.
We realize this concept with RLWE encryption schemes, and by leveraging the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse them across multiple protocol executions.
As a concrete application, we propose highly efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 6.37GB/s without requiring transmission of any client or server state.
We additionally formalize the matrix vector multiplication protocol as a novel primitive that we call LinPIR, which may be of independent interest.
In our second construction (TensorPIR) we reduce the communication of HintlessPIR from square root to cubic root in the database size.
We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications.
This allows the server to do more complex processing using a more compact query under LWE.
We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest.
We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or the database updates frequently.
The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022).
In the setting of anonymous queries we also improve on Spiral's communication.

2024

TCC

Bit Security: optimal adversaries, equivalence results, and a toolbox for computational/statistical security analysis
Abstract

We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions, and facilitating their use.
Specific contributions of this paper include:
(1) identifying the optimal adversaries achieving the highest possible MW advantage, showing that they are deterministic and have a very simple threshold structure;
(2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and
(3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments and probability replacement theorems.
On the technical side, our results are obtained by introducing a new notion of "fuzzy" distinguisher (which we prove equivalent to the "aborting" distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam metric, a standard quantity used in statistics.

2023

EUROCRYPT

Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption
Abstract

There are two competing approaches to bootstrap the FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) and its variants: the original AP/FHEW method, which supports arbitrary secret key distributions, and the improved GINX/TFHE method, which uses much smaller evaluation keys, but is directly applicable only to binary secret keys, restricting the scheme's applicability.
In this paper, we present a new bootstrapping procedure for FHEW-like encryption schemes that achieves the best features of both methods: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys. (Support for arbitrary secret keys is critical in a number of important applications, like threshold and some multi-key homomorphic encryption schemes.) As an added benefit, our new bootstrapping procedure results in smaller noise growth than both AP and GINX, regardless of the key distribution.
Our improvements are both theoretically significant (offering asymptotic savings, up to a $O(log n)$ multiplicative factor, either on the running time or public evaluation key size), and practically relevant. For example, for a concrete 128-bit target security level, we show how to decrease the evaluation key size of the best previously known scheme by more than 30\%, while also slightly reducing the running time. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE/OpenFHE open-source homomorphic encryption library. We provide optimized parameter sets and implementation results showing that the proposed algorithm has the best performance among all known FHEW bootstrapping methods in terms of runtime and key size. We illustrate the benefits of our method by sketching a simple construction of threshold homomorphic encryption based on FHEW.

2023

CRYPTO

Reductions from module lattices to free module lattices, and application to dequantizing module-LLL
Abstract

In this article, we give evidences that free modules (i.e., modules
which admit a basis) are no weaker than arbitrary modules, when
it comes to solving cryptographic algorithmic problems (and when the
rank of the module is at least 2). More precisely, we show that for three
algorithmic problems used in cryptography, namely the shortest vector
problem, the Hermite shortest vector problem and a variant of the closest
vector problem, there is a reduction from solving the problem in any
module of rank n ≥ 2 to solving the problem in any free module of the
same rank n. As an application, we show that this can be used to dequantize the LLL algorithm for module lattices presented by Lee et al. (Asiacrypt 2019).

2023

CRYPTO

Error Correction and Ciphertext Quantization in Lattice Cryptography
Abstract

Recent work in the design of rate $1 - o(1)$ lattice-based cryptosystems have used two distinct design paradigms, namely replacing the noise-tolerant encoding $m \mapsto (q/2)m$ present in many lattice-based cryptosystems with a more efficient encoding, and post-processing traditional lattice-based ciphertexts with a lossy compression algorithm, using a technique very similar to the technique of ``vector quantization'' within coding theory.
We introduce a framework for the design of lattice-based encryption that captures both of these paradigms, and prove information-theoretic rate bounds within this framework.
These bounds separate the settings of trivial and non-trivial quantization, and show the impossibility of rate $1 - o(1)$ encryption using both trivial quantization and polynomial modulus.
They furthermore put strong limits on the rate of constructions that utilize lattices built by tensoring a lattice of small dimension with $\Zset^k$, which is ubiquitous in the literature.
We additionally introduce a new cryptosystem, that matches the rate of the highest-rate currently known scheme, while encoding messages with a ``gadget'', which may be useful for constructions of Fully Homomorphic Encryption.

2022

CRYPTO

Securing Approximate Homomorphic Encryption using Differential Privacy
📺
Abstract

Recent work of Li and Micciancio (Eurocrypt 2021) has shown that the traditional formulation of indistinguishabiity under chosen plaintext attack (IND-CPA) is not adequate to capture the security of approximate homomorphic encryption against passive adversaries, and identified a stronger IND-CPA^D security definition
(IND-CPA with decryption oracles) as the appropriate security target for approximate encryption schemes. We show how to transform any approximate homomorphic encryption scheme achieving the weak IND-CPA security definition, into one which is provably IND-CPA^D secure, offering strong guarantees against realistic passive attacks. The method works by postprocessing the output of the decryption function with a mechanism satisfying an appropriate notion of differentially privacy (DP), adding an amount of noise tailored to the worst-case error growth of the homomorphic computation.
We apply these results to the approximate homomorphic encryption scheme of Cheon, Kim, Kim, and Song (CKKS, Asiacrypt 2017), proving that adding Gaussian noise to the output of CKKS decryption suffices to achieve IND-CPA^D security. We precisely quantify how much Gaussian noise must be added by proving nearly matching upper and lower bounds, showing that one cannot hope to significantly reduce the amount of noise added in this post-processing step. Based on our upper and lower bounds, we propose parameters for the counter-measures recently adopted by open-source libraries implementing CKKS.
Lastly, we investigate the plausible claim that smaller DP noise parameters might suffice to achieve IND-CPA^D-security for schemes supporting more accurate (dynamic, key dependent) estimates of ciphertext noise during decryption. Perhaps surprisingly, we show that this claim is false, and that DP mechanisms with noise parameters tailored to the error present in a given ciphertext, rather than worst-case error, are vulnerable to IND-CPA^D attacks.

2022

ASIACRYPT

Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping
📺
Abstract

A comparison of two encrypted numbers is an important operation needed in many machine learning applications, for example, decision tree or neural network inference/training. An efficient instantiation of this operation in the context of fully homomorphic encryption (FHE) can be challenging, especially when a relatively high precision is sought. The conventional FHE way of evaluating the comparison operation, which is based on the sign function evaluation using FHEW/TFHE bootstrapping (often referred in literature as programmable bootstrapping), can only support very small precision (practically limited to 4-5 bits or so). For higher precision, the runtime complexity scales linearly with the ciphertext (plaintext) modulus (i.e., exponentially with the modulus bit size). We propose sign function evaluation algorithms that scale logarithmically with the ciphertext (plaintext) modulus, enabling the support of large-precision comparison in practice. Our sign evaluation algorithms are based on an iterative use of homomorphic floor function algorithms, which are also derived in our work. Further, we generalize our procedures for floor function evaluation to arbitrary function evaluation, which can be used to support both small plaintext moduli (directly) and larger plaintext moduli (by using a homomorphic digit decomposition algorithm, also suggested in our work). We implement all these algorithms using the PALISADE lattice cryptography library, introducing several implementation-specific optimizations along the way, and discuss our experimental results.

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

- Asiacrypt 2024
- 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)
- Rakyong Choi (1)
- Maxim Deryabin (1)
- Léo Ducas (2)
- Jieun Eom (1)
- Nicholas Genise (4)
- Rosario Gennaro (1)
- Craig Gentry (1)
- Shafi Goldwasser (1)
- Shai Halevi (1)
- Alejandro Hevia (1)
- Andrey Kim (1)
- Duhyeong Kim (1)
- Yongwoo Lee (1)
- Zeyu Li (1)
- Baiyu Li (6)
- Vadim Lyubashevsky (4)
- Tal Malkin (1)
- Daniele Micciancio (49)
- Gabrielle De Micheli (2)
- Sara K. Miner (1)
- Petros Mol (1)
- Shien Jin Ong (1)
- Saurabh Panjwani (2)
- Chris Peikert (4)
- Alice Pellet-Mary (1)
- Erez Petrank (1)
- Yuriy Polyakov (2)
- Mariana Raykova (1)
- Alon Rosen (1)
- Amit Sahai (1)
- Mark Schultz (2)
- David Schultz (1)
- Mark Schultz-Wu (1)
- Jessica Sorrell (2)
- Adam Suhl (1)
- Nam Tran (1)
- Salil P. Vadhan (2)
- Vinod Vaikuntanathan (1)
- Michael Walter (4)
- Bogdan Warinschi (2)
- Scott Yilek (1)
- Donghoon Yoo (1)