## CryptoDB

### Manoj Prabhakaran

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration
📺
Abstract

Can a sender encode a pair of messages (m_0,m_1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?
Garg et al. (Crypto 2015) showed that this is information-theoretically impossible.
We show how to circumvent this impossibility by assuming that the receiver is computationally bounded, settling for an inverse-polynomial security error (which is provably necessary), and relying on ideal obfuscation.
Our solution creates a ``computational anti-correlation'' between the events of receiving m_0 and receiving m_1 by exploiting the anti-concentration of the binomial distribution.
The ideal obfuscation primitive in our construction can either be directly realized using (stateless) tamper-proof hardware, yielding an unconditional result, or heuristically instantiated using existing indistinguishability obfuscation schemes. We put forward a new notion of obfuscation that suffices to securely instantiate our construction.
As a corollary, we get similar feasibility results for general secure computation of sender-receiver functionalities by leveraging the completeness of the above ``random oblivious transfer'' functionality.

2021

TCC

On Communication Models and Best-Achievable Security in Two-Round MPC
📺
Abstract

Recently, a sequence of works have made strong advances in two-round (i.e., round-optimal) secure multi-party computation (MPC). In the {\em honest-majority} setting -- the focus of this work -- Ananth et al. [CRYPTO'18, EC'19], Applebaum et al. [TCC'18, EC'19] and Garg et al. [TCC'18] have established the feasibility of general two-round MPC in standard communication models involving broadcast ($\BC$) and private point-to-point ($\PTP$) channels.
In this work, we set out to understand what features of the communication model are necessary for these results, and more broadly the design of two-round MPC. Focusing our study on the plain model -- the most natural model for honest-majority MPC -- we obtain the following results:
1. {\bf Dishonest majority from Honest majority:}
In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often {\em equivalent}. This follows from our results that the former implies 2-message oblivious transfer, in many settings. (i) We show that without private point-to-point ($\PTP$) channels, i.e., when we use only broadcast ($\BC$) channels, {\em honest-majority MPC implies 2-message oblivious transfer}. (ii) Furthermore, this implication holds even when we use both $\PTP$ and $\BC$, provided that the MPC protocol is robust against ``fail-stop'' adversaries.
2. {\bf Best-Achievable Security:} While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the ``next best'' security notion, namely, security with identifiable abort (\IA). We show that \IA\ is also {\em impossible} to achieve with honest-majority even if we use both $\PTP$ and $\BC$ channels. However, if we replace $\PTP$ channels with a ``bare'' (i.e., untrusted) public-key infrastructure ($\PKI$), then even security with guaranteed output delivery (and hence $\IA$) is possible to achieve.
\end{itemize}
These results ``explain'' that the reliance on $\PTP$ channels (together with $\BC$) in the recent two-round protocols in the plain model was in fact {\em necessary}, and that these protocols {\em couldn't} have achieved a stronger security guarantee, namely, $\IA$. Overall, our results (put together with prior works) fully determine the best-achievable security for honest-majority MPC in different communication models in two rounds. As a consequence, they yield the following hierarchy of communication models:
$\BC < \PTP < \BC+\PTP < \BC+\PKI$.
This shows that $\BC$ channel is the {\em weakest} communication model, and that $\BC+\PKI$ model is strictly stronger than $\BC+\PTP$ model.

2020

PKC

Witness Maps and Applications
📺
Abstract

We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an $$mathbf {NP}$$ statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable” mode to a CWM. Our main construction is a DMWM for all $$mathbf {NP}$$ relations, assuming sub-exponentially secure indistinguishability obfuscation ( $${imathcal {O}}$$ ), along with standard cryptographic assumptions. The DMWM construction relies on a CWM and a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF), both of which are in turn instantiated based on $${imathcal {O}}$$ and other primitives. Our instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct, from standard assumptions, Puncturable Digital Signatures and a new primitive called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure $${imathcal {O}}$$ and sub-exponentially secure OWF. As an application of our constructions, we show how to use a DMWM to construct the first leakage and tamper-resilient signatures with a deterministic signer , thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of $$1 - o(1)$$ .

2020

TCC

Zero-Communication Reductions
📺
Abstract

We introduce a new primitive in information-theoretic cryptography, namely zero-communication reductions (ZCR), with different levels of security. We relate ZCR to several other important primitives, and obtain new results on upper and lower bounds.
In particular, we obtain new upper bounds for PSM, CDS and OT complexity of functions, which are exponential in the information complexity of the functions. These upper bounds complement the results of Beimel et al. (2014) which broke the circuit-complexity barrier for ``high complexity'' functions; our results break the barrier of input size for ``low complexity'' functions.
We also show that lower bounds on secure ZCR can be used to establish lower bounds for OT-complexity. We recover the known (linear) lower bounds on OT-complexity by Beimal and Malkin (2004) via this new route. We also formulate the lower bound problem for secure ZCR in purely linear-algebraic terms, by defining the invertible rank of a matrix.
We present an Invertible Rank Conjecture, proving which will establish super-linear lower bounds for OT-complexity (and if accompanied by an explicit construction, will provide explicit functions with super-linear circuit lower bounds).

2020

ASIACRYPT

Cryptography from One-Way Communication: On Completeness of Finite Channels
📺
Abstract

Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of {\em finite} channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results:
Completeness of Bit-ROT with Inverse Polynomial Error: We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error.
No Finite Channel is Complete with Negligible Error: To complement the above, we show that {\it no} finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al.
Characterization of Finite Channels Enabling Zero-Knowledge Proofs: An important instance of secure computation is zero-knowledge proofs.
Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.

2019

EUROCRYPT

Uncovering Algebraic Structures in the MPC Landscape
📺
Abstract

A fundamental problem in the theory of secure multi-party computation (MPC) is to characterize functions with more than 2 parties which admit MPC protocols with information-theoretic security against passive corruption. This question has seen little progress since the work of Chor and Ishai (1996), which demonstrated difficulties in resolving it. In this work, we make significant progress towards resolving this question in the important case of aggregating functionalities, in which m parties
$$P_1,\dots ,P_m$$
P1,⋯,Pm hold inputs
$$x_1,\dots ,x_m$$
x1,⋯,xm and an aggregating party
$$P_0$$
P0 must learn
$$f(x_1,\dots ,x_m)$$
f(x1,⋯,xm).We uncover a rich class of algebraic structures that are closely related to secure computability, namely, “Commuting Permutations Systems” (CPS) and its variants. We present an extensive set of results relating these algebraic structures among themselves and to MPC, including new protocols, impossibility results and separations. Our results include a necessary algebraic condition and slightly stronger sufficient algebraic condition for a function to admit information-theoretically secure MPC protocols.We also introduce and study new models of minimally interactive MPC (called UNIMPC and
), which not only help in understanding our positive and negative results better, but also open up new avenues for studying the cryptographic complexity landscape of multi-party functionalities. Our positive results include novel protocols in these models, which may be of independent practical interest.Finally, we extend our results to a definition that requires UC security as well as semi-honest security (which we term strong security). In this model we are able to carry out the characterization of all computable functions, except for a gap in the case of aggregating functionalities.

2018

PKC

Towards Characterizing Securely Computable Two-Party Randomized Functions
Abstract

A basic question of cryptographic complexity is to combinatorially characterize all randomized functions which have information-theoretic semi-honest secure 2-party computation protocols. The corresponding question for deterministic functions was answered almost three decades back, by Kushilevitz [Kus89]. In this work, we make progress towards understanding securely computable randomized functions. We bring tools developed in the study of completeness to bear on this problem. In particular, our characterizations are obtained by considering only symmetric functions with a combinatorial property called simplicity [MPR12].Our main result is a complete combinatorial characterization of randomized functions with ternary output kernels, that have information-theoretic semi-honest secure 2-party computation protocols. In particular, we show that there exist simple randomized functions with ternary output that do not have secure computation protocols. (For deterministic functions, the smallest output alphabet size of such a function is 5, due to an example given by Beaver [Bea89].)Also, we give a complete combinatorial characterization of randomized functions that have 2-round information-theoretic semi-honest secure 2-party computation protocols.We also give a counter-example to a natural conjecture for the full characterization, namely, that all securely computable simple functions have secure protocols with a unique transcript for each output value. This conjecture is in fact true for deterministic functions, and – as our results above show – for ternary functions and for functions with 2-round secure protocols.

2016

TCC

2015

TCC

2015

TCC

2012

CRYPTO

2008

CRYPTO

#### Program Committees

- Crypto 2016
- Eurocrypt 2015
- Asiacrypt 2013
- Crypto 2013
- TCC 2011
- Asiacrypt 2009
- TCC 2009
- Asiacrypt 2008
- Crypto 2008
- TCC 2006

#### Coauthors

- Navneet Agarwal (1)
- Divesh Aggarwal (1)
- Shweta Agrawal (5)
- Shashank Agrawal (8)
- Sanat Anand (1)
- Prabhanjan Ananth (1)
- Saikrishna Badrinarayanan (1)
- Suvradip Chakraborty (1)
- Deepesh Data (2)
- Juan A. Garay (2)
- Vipul Goyal (2)
- Divya Gupta (3)
- Yuval Ishai (8)
- Abhishek Jain (2)
- Dakshita Khurana (1)
- Daniel Kraschewski (2)
- Abishek Kumarasubramanian (1)
- Eyal Kushilevitz (5)
- Ben Lynn (1)
- Philip D. MacKenzie (2)
- Mohammad Mahmoody (1)
- Hemanta K. Maji (9)
- Varun Narayanan (3)
- Rafail Ostrovsky (2)
- Pichayoot Ouppaphan (1)
- Omkant Pandey (4)
- Vinod Prabhakaran (2)
- Vinod M. Prabhakaran (2)
- Aarushi Goel Rajeev Raghunath (1)
- Rajeev Raghunath (1)
- Alon Rosen (3)
- Mike Rosulek (7)
- Amit Sahai (13)
- David Wagner (1)
- Daniel Wichs (1)
- Jürg Wullschleger (1)
- Ke Yang (2)
- Ching-Hua Yu (2)