I am a PhD student in the algorithms and theory group at UIUC, advised by Manoj Prabhakaran.

Elette Boyle, Abhishek Jain, Manoj Prabhakaran, Ching-Hua Yu

▼
** Abstract**

In this work, we initiate the study of "bottleneck" communication complexity
as a new efficiency measure for secure multiparty computation (MPC). Roughly,
the bottleneck communication complexity of an MPC protocol is defined as the
maximum communication complexity required by any party within the protocol execution.

We observe that even without security, bottleneck communication complexity is
an interesting measure of communication complexity for (distributed) functions
and propose it as a fundamental area to explore. While achieving $O(n)$ bottleneck
complexity is straightforward, we show that achieving {\em sublinear} bottleneck
complexity is {\em not} always possible, even when no security is required.

Our main positive result is a compiler that transforms any insecure, fixed
communication-pattern protocol for computing any functionality into a secure
MPC protocol while preserving the bottleneck complexity of the underlying protocol
(up to security parameter overhead). Given our compiler, an insecure protocol for
any function $f$ with sublinear bottleneck complexity can be transformed into
an MPC protocol for $f$ with the same bottleneck complexity. Along the way, we
build cryptographic primitives -- incremental FHE, SNARKs with a simulation-extractability
property and Verifiable Protocol Execution -- that may be of independent interest.

Ching-Hua Yu

▼
** Abstract**

The most popular stability notion in games should be Nash equilibrium under the rationality of players who maximize their own payoff individually. In contrast, in many scenarios, players can be (partly) irrational with some unpredictable factors. Hence a strategy profile can be more robust if it is resilient against certain irrational behaviors. In this paper, we propose a stability notion that is resilient against envy. A strategy profile is said to be "envy-proof" if by deviation, each player cannot gain a competitive edge with respect to the change in utility over the other players. Together with Nash equilibrium and another stability notion called immunity, we show how these separate notions are related to each other, whether they exist in games, and whether and when a strategy profile satisfying these notions can be efficiently found. We answer these questions by starting with the general two player game and extend the discussion for the approximate stability and for the corresponding fault-tolerance notions in multi-player games.

Ching-Hua Yu

Yuval Ishai, Eyal Kushilevitz, Manoj Prabhakaran, Amit Sahai, Ching-Hua Yu.

*CRYPTO
2016.*
▼
** Abstract**

In the rich literature of secure multi-party computation (MPC), several important results rely on ``protocol transformations,'' whereby protocols from one model of MPC are transformed to protocols from another model. Motivated by the goal of simplifying and unifying results in the area of MPC, we formalize a general notion of black-box protocol transformations that captures previous transformations from the literature as special cases, and present several new transformations. We motivate our study of protocol transformations by presenting the following applications.

Simplifying feasibility results:

- Easily rederive a result in Goldreich's book (2004), on MPC with full security in the presence of an honest majority, from an earlier result in the book, on MPC that offers ``security with abort.''

- Rederive the classical result of Rabin and Ben-Or (1989) by applying a transformation to the simpler protocols of Ben-Or et al.\ or Chaum et al. (1988).

Efficiency improvements:

- The first ``constant-rate'' MPC protocol for a constant number of parties that offers full information-theoretic security with an optimal threshold, improving over the protocol of Rabin and Ben-Or;

- A fully secure MPC protocol with optimal threshold that improves over a previous protocol of Ben-Sasson et al.\ (2012) in the case of ``deep and narrow'' computations;

- A fully secure MPC protocol with near-optimal threshold that improves over a previous protocol of Damg{\aa}rd et al. (2010) by improving the dependence on the security parameter from linear to polylogarithmic;

- An efficient new transformation from passive-secure two-party computation in the OT-hybrid and OLE-hybrid model to zero-knowledge proofs, improving over a recent similar transformation of Hazay and Venkitasubramaniam (2016).

Shashank Agrawal, Manoj Prabhakaran, Ching-Hua Yu.

We extend the simulation-based definition of Virtual Grey Box (VGB) security -- originally proposed for obfuscation (Bitansky and Canetti, 2010) -- to a broad class of cryptographic primitives. These include functional encryption, graded encoding schemes, bi-linear maps (with über assumptions), as well as unexplored ones like homomorphic functional encryption. Our main result is a characterization of VGB security, in all these cases, in terms of an "indistinguishability-preserving" notion of security, called $\Gamma^*-\text{s-IND-PRE}$ security, formulated using an extension of the recently proposed "Cryptographic Agents" framework (Agrawal et al., 2015). We further show that this definition is equivalent to an indistinguishability based security definition that is restricted to "concentrated" distributions (wherein the outcome of any computation on encrypted data is essentially known ahead of the computation). A result of Bitansky et al. (2014), who showed that VGB obfuscation is equivalent to strong indistinguishability obfuscation (SIO), is obtained by specializing our result to obfuscation. Our proof, while sharing various elements from the proof of Bitansky et al., is simpler and significantly more general, as it uses $\Gamma^*-\text{s-IND-PRE}$ security as an intermediate notion. Our characterization also shows that the semantic security for graded encoding schemes (Pass et al. 2014), is in fact an instance of this same definition. We also present a composition theorem for $\Gamma^*-\text{s-IND-PRE}$ security. We can then recover the result of Bitansky et al. (2014) regarding the existence of VGB obfuscation for all NC$^1$ circuits, simply by instantiating this composition theorem with a reduction from obfuscation of NC$^1$ circuits to graded encoding schemas (Barak et al., 2014) and the assumption that there exists an $\Gamma^*-\text{s-IND-PRE}$ secure scheme for the graded encoding schema (Pass et al. 2014).