## CryptoDB

### Prabhanjan Ananth

#### Affiliation: UCLA and MIT, USA

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

Two Round Information-Theoretic MPC with Malicious Security
📺
Abstract

We provide the first constructions of two round information-theoretic (IT) secure multiparty computation (MPC) protocols in the plain model that tolerate any $$t<n/2$$t<n/2 malicious corruptions. Our protocols satisfy the strongest achievable standard notions of security in two rounds in different communication models.Previously, IT-MPC protocols in the plain model either required a larger number of rounds, or a smaller minority of corruptions.

2019

CRYPTO

Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification
📺
Abstract

The existence of secure indistinguishability obfuscators (
$$i\mathcal {O}$$
) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing
$$i\mathcal {O}$$
rely on d-linear maps. While secure bilinear maps are well established in cryptographic literature, the security of candidates for
$$d>2$$
is poorly understood.We propose a new approach to constructing
$$i\mathcal {O}$$
for general circuits. Unlike all previously known realizations of
$$i\mathcal {O}$$
, we avoid the use of d-linear maps of degree
$$d \ge 3$$
.At the heart of our approach is the assumption that a new weak pseudorandom object exists. We consider two related variants of these objects, which we call perturbation resilient generator (
$$\varDelta $$
RG) and pseudo flawed-smudging generator (
$$\mathrm {PFG}$$
), respectively. At a high level, both objects are polynomially expanding functions whose outputs partially hide (or smudge) small noise vectors when added to them. We further require that they are computable by a family of degree-3 polynomials over
$$\mathbb {Z}$$
. We show how they can be used to construct functional encryption schemes with weak security guarantees. Finally, we use novel amplification techniques to obtain full security.As a result, we obtain
$$i\mathcal {O}$$
for general circuits assuming:Subexponentially secure LWEBilinear Maps
$$\mathrm {poly}(\lambda )$$
-secure 3-block-local PRGs
$$\varDelta $$
RGs or
$$\mathrm {PFG}$$
s

2019

TCC

Optimal Bounded-Collusion Secure Functional Encryption
Abstract

We construct private-key and public-key functional encryption schemes in the bounded-key setting; that is, secure against adversaries that obtain an a-priori bounded number of functional keys (also known as the collusion bound).An important metric considered in the literature on bounded-key functional encryption schemes is the dependence of the running time of the encryption algorithm on the collusion bound
$$Q=Q(\lambda )$$
(where
$$\lambda $$
is the security parameter). It is known that bounded-key functional encryption schemes with encryption complexity growing with
$$Q^{1-\varepsilon }$$
, for any constant
$$\varepsilon > 0$$
, implies indistinguishability obfuscation. On the other hand, in the public-key setting, it was previously unknown whether we could achieve encryption complexity growing linear with Q, also known as optimal bounded-key FE, based on well-studied assumptions.In this work, we give the first construction of an optimal bounded-key public-key functional encryption scheme under the minimal assumption of the existence of any public-key encryption scheme. Moreover, our scheme supports the class of all polynomial-size circuits.Our techniques also extend to the private-key setting. We achieve a construction of an optimal bounded-key functional encryption in the private-key setting based on the minimal assumption of one-way functions, instead of learning with errors as achieved in prior works.

2019

TCC

From FE Combiners to Secure MPC and Back
Abstract

Cryptographic combiners allow one to combine many candidates for a cryptographic primitive, possibly based on different computational assumptions, into another candidate with the guarantee that the resulting candidate is secure as long as at least one of the original candidates is secure. While the original motivation of cryptographic combiners was to reduce trust on existing candidates, in this work, we study a rather surprising implication of combiners to constructing secure multiparty computation protocols. Specifically, we initiate the study of functional encryption combiners and show its connection to secure multiparty computation.Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure.Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results.
A two-round semi-honest MPC protocol in the plain model secure against up to $$n-1$$ corruptions with communication complexity proportional only to the depth of the circuit being computed assuming learning with errors (LWE). Prior two round protocols based on standard assumptions that achieved this communication complexity required trust assumptions, namely, a common reference string.A functional encryption combiner based on pseudorandom generators (PRGs) in $$\mathsf {NC}^1$$. This is a weak assumption as such PRGs are implied by many concrete intractability problems commonly used in cryptography, such as ones related to factoring, discrete logarithm, and lattice problems [11]. Previous constructions of FE combiners, implicit in [7], were known only from LWE. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption based only on the assumptions that functional encryption exists and PRGs in $$\mathsf {NC}^1$$.

2019

TCC

Fully Homomorphic NIZK and NIWI Proofs
Abstract

In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. We focus on the NP complete language L, where, for a boolean circuit C and a bit b, the pair $$(C,b)\in L$$ if there exists an input $$\mathbf {w}$$ such that $$C(\mathbf {w})=b$$. For this language, we call a non-interactive proof system fully homomorphic if, given instances $$(C_i,b_i)\in L$$ along with their proofs $$\varPi _i$$, for $$i\in \{1,\ldots ,k\}$$, and given any circuit $$D:\{0,1\}^k\rightarrow \{0,1\}$$, one can efficiently compute a proof $$\varPi $$ for $$(C^*,b)\in L$$, where $$C^*(\mathbf {w}^{(1)},\ldots ,\mathbf {w}^{(k)})=D(C_1(\mathbf {w}^{(1)}),\ldots ,C_k(\mathbf {w}^{(k)}))$$ and $$D(b_1,\ldots ,b_k)=b$$. The key security property is unlinkability: the resulting proof $$\varPi $$ is indistinguishable from a fresh proof of the same statement. Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.

2019

ASIACRYPT

Towards Attribute-Based Encryption for RAMs from LWE: Sub-linear Decryption, and More
Abstract

Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key is represented by a random access machine (RAM) and a database, with the runtime of the RAM program being sublinear in the database size. In this work we study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (Crypto 2013). We present a construction of attribute based encryption for RAMs satisfying sublinear decryption complexity assuming learning with errors; this is the first construction based on standard assumptions. Previously, Goldwasser et al. achieved this result based on non-falsifiable knowledge assumptions. We also consider a dual notion of ABE for RAMs, where the database is in the ciphertext and we show how to achieve this dual notion, albeit with large attribute keys, also based on learning with errors.

2018

CRYPTO

Private Circuits: A Modular Approach
📺
Abstract

We consider the problem of protecting general computations against constant-rate random leakage. That is, the computation is performed by a randomized boolean circuit that maps a randomly encoded input to a randomly encoded output, such that even if the value of every wire is independently leaked with some constant probability
$$p > 0$$
p>0, the leakage reveals essentially nothing about the input.In this work we provide a conceptually simple, modular approach for solving the above problem, providing a simpler and self-contained alternative to previous constructions of Ajtai (STOC 2011) and Andrychowicz et al. (Eurocrypt 2016). We also obtain several extensions and generalizations of this result. In particular, we show that for every leakage probability
$$p<1$$
p<1, there is a finite basis
$$\mathbb {B}$$
B such that leakage-resilient computation with leakage probability p can be realized using circuits over the basis
$$\mathbb {B}$$
B. We obtain similar positive results for the stronger notion of leakage tolerance, where the input is not encoded, but the leakage from the entire computation can be simulated given random
$$p'$$
p′-leakage of input values alone, for any
$$p<p'<1$$
p<p′<1. Finally, we complement this by a negative result, showing that for every basis
$$\mathbb {B}$$
B there is some leakage probability
$$p<1$$
p<1 such that for any
$$p'<1$$
p′<1, leakage tolerance as above cannot be achieved in general.We show that our modular approach is also useful for protecting computations against worst case leakage. In this model, we require that leakage of any
$$\mathbf{t}$$
t (adversarially chosen) wires reveal nothing about the input. By combining our construction with a previous derandomization technique of Ishai et al. (ICALP 2013), we show that security in this setting can be achieved with
$$O(\mathbf{t}^{1+\varepsilon })$$
O(t1+ε) random bits, for every constant
$$\varepsilon > 0$$
ε>0. This (near-optimal) bound significantly improves upon previous constructions that required more than
$$\mathbf{t}^{3}$$
t3 random bits.

2018

CRYPTO

Round-Optimal Secure Multiparty Computation with Honest Majority
📺
Abstract

We study the exact round complexity of secure multiparty computation (MPC) in the honest majority setting. We construct several round-optimaln-party protocols, tolerating any $$t<\frac{n}{2}$$ corruptions.
1.Security with abort: We give the first construction of two round MPC for general functions that achieves security with abort against malicious adversaries in the plain model. The security of our protocol only relies on one-way functions.2.Guaranteed output delivery: We also construct protocols that achieve security with guaranteed output delivery: (i) Against fail-stop adversaries, we construct two round MPC either in the (bare) public-key infrastructure model with no additional assumptions, or in the plain model assuming two-round semi-honest oblivious transfer. In three rounds, however, we can achieve security assuming only one-way functions. (ii) Against malicious adversaries, we construct three round MPC in the plain model, assuming public-key encryption and Zaps.Previously, such protocols were only known based on specific learning assumptions and required the use of common reference strings.
All of our results are obtained via general compilers that may be of independent interest.

2018

TCC

Succinct Garbling Schemes from Functional Encryption Through a Local Simulation Paradigm
Abstract

We study a simulation paradigm, referred to as local simulation, in garbling schemes. This paradigm captures simulation proof strategies in which the simulator consists of many local simulators that generate different blocks of the garbled circuit. A useful property of such a simulation strategy is that only a few of these local simulators depend on the input, whereas the rest of the local simulators only depend on the circuit.We formalize this notion by defining locally simulatable garbling schemes. By suitably realizing this notion, we give a new construction of succinct garbling schemes for Turing machines assuming the polynomial hardness of compact functional encryption and standard assumptions (such as either CDH or LWE). Prior constructions of succinct garbling schemes either assumed sub-exponential hardness of compact functional encryption or were designed only for small-space Turing machines.We also show that a variant of locally simulatable garbling schemes can be used to generically obtain adaptively secure garbling schemes for circuits. All prior constructions of adaptively secure garbling that use somewhere equivocal encryption can be seen as instantiations of our construction.

2017

EUROCRYPT

2017

EUROCRYPT

2017

CRYPTO

2016

CRYPTO

2015

EPRINT

#### Program Committees

- PKC 2018
- Asiacrypt 2018

#### Coauthors

- Shashank Agrawal (1)
- Saikrishna Badrinarayanan (1)
- Raghav Bhaskar (1)
- Zvika Brakerski (1)
- Nishanth Chandran (1)
- Yu-Chi Chen (1)
- Arka Rai Choudhuri (3)
- Kai-Min Chung (1)
- Aloni Cohen (1)
- Apoorvaa Deshpande (1)
- Xiong Fan (1)
- Aarushi Goel (2)
- Vipul Goyal (4)
- Divya Gupta (1)
- Yuval Ishai (2)
- Abhishek Jain (11)
- Aayush Jain (4)
- Yael Tauman Kalai (1)
- Bhavana Kanukurthi (1)
- Wei-Kai Lin (1)
- Huijia Lin (2)
- Alex Lombardi (1)
- Anna Lysyanskaya (1)
- Nathan Manohar (1)
- Christian Matt (1)
- Moni Naor (1)
- Rafail Ostrovsky (1)
- Omkant Pandey (1)
- Manoj Prabhakaran (1)
- Vanishree Rao (1)
- Alon Rosen (1)
- Amit Sahai (12)
- Gil Segev (1)
- Elaine Shi (1)
- Vinod Vaikuntanathan (2)
- Eylon Yogev (1)