International Association
for Cryptologic Research

In recent breakthrough results, novel use of grabled circuits yielded constructions for several primitives like Identity-Based Encryption (IBE) and 2-round secure multi-party computation, based on standard assumptions in public-key cryptography. While the techniques in these different results have many common elements, these works did not offer a modular abstraction that could be used across them. Our main contribution is to introduce a novel notion of obfuscation, called Reach-Restricted Reactive-Program Obfuscation (R3PO) that captures the essence of these constructions, and exposes additional capabilities. We provide a powerful composition theorem whose proof fully encapsulates the use of garbled circuits in these works. As an illustration of the potential of R3PO, and as an important contribution of independent interest, we present a variant of Multi-Authority Attribute-Based Encryption (MA-ABE) that can be based on (single-authority) CP-ABE in a blackbox manner, using only standard cryptographic assumptions (e.g., DDH) in addition. This is in stark contrast to the existing constructions for MA-ABE, which rely on the random oracle model and supports only limited policy classes.

We introduce a new cryptographic primitive, called Completely Anonymous Signed Encryption(CASE). CASE is a public-key authenticated encryption primitive, that offers anonymity for senders as well as receivers. A “case-packet” should appear, without a (decryption) key for opening it, to be a blackbox that reveals no information at all about its contents. To decase a case-packet fully – so that the message is retrieved and authenticated – a verification key is also required. Defining security for this primitive is subtle. We present a relatively simple Chosen Objects Attack (COA) security definition. Validating this definition, we show that it implies a comprehensive indistinguishability-preservation definition in the real-ideal paradigm. To obtain the latter definition, we extend the Cryptographic Agents framework to allow maliciously created objects. We also provide a novel and practical construction for COA-secure CASE under standard assumptions in public-key cryptography, and in the standard model. We believe CASE can be a staple in future cryptographic libraries, thanks to its robust security guarantees and efficient instantiations based on standard assumptions.

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.