## CryptoDB

### Rex Fernando

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Maliciously Secure Massively Parallel Computation for All-but-One Corruptions
📺
Abstract

The Massive Parallel Computing (MPC) model gained wide adoption
over the last decade. By now, it is widely accepted as the right model for
capturing the commonly used programming paradigms (such as MapReduce, Hadoop,
and Spark) that utilize parallel computation power to manipulate and analyze
huge amounts of data.
Motivated by the need to perform large-scale data analytics in a
privacy-preserving manner, several recent works have presented generic
compilers that transform algorithms in the MPC model into secure counterparts,
while preserving various efficiency parameters of the original algorithms. The
first paper, due to Chan et al. (ITCS '20), focused on the honest majority
setting. Later, Fernando et al. (TCC '20) considered the dishonest majority
setting. The latter work presented a compiler that transforms generic MPC
algorithms into ones which are secure against \emph{semi-honest} attackers that
may control all but one of the parties involved. The security of their
resulting algorithm relied on the existence of a PKI and also on rather strong
cryptographic assumptions: indistinguishability obfuscation and the circular
security of certain LWE-based encryption systems.
In this work, we focus on the dishonest majority setting, following Fernando et
al. In this setting, the known compilers do not achieve the standard security
notion called \emph{malicious} security, where attackers can arbitrarily
deviate from the prescribed protocol. In fact, we show that unless very strong
setup assumptions as made (such as a \emph{programmable} random oracle), it is
provably \emph{impossible} to withstand malicious attackers due to the
stringent requirements on space and round complexity.
As our main contribution, we complement the above negative result by designing
the first general compiler for malicious attackers in the dishonest majority
setting. The resulting protocols withstand all-but-one corruptions.
Our compiler relies on a simple PKI and a (programmable) random oracle, and is
proven secure assuming LWE and SNARKs. Interestingly, even with such strong
assumptions, it is rather non-trivial to obtain a secure protocol.

2020

EUROCRYPT

Statistical ZAP Arguments
📺
Abstract

Dwork and Naor (FOCS'00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives.
However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers.
In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with {\em statistical} privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument.
Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

2020

TCC

Secure Massively Parallel Computation for Dishonest Majority
📺
Abstract

This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the types of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS ’20) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt.
We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors
(LWE) problem, and works for any MPC protocol with “short” output—that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE.

2019

ASIACRYPT

Output Compression, MPC, and iO for Turing Machines
Abstract

In this work, we study the fascinating notion of output-compressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct output-compressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set
$$\{$$
LWE, DDH, N
$$^{th}$$
Residuosity
$$\}$$
.We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO): 1.Compact MPC for Turing Machines in the Random Oracle Model. In the context of MPC, we consider the following basic feasibility question: does there exist a malicious-secure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as a compact MPC protocol. Hubácek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (non-compact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming output-compressing randomized encodings in the shared randomness model.2.Succinct iO for Turing Machines in the Shared Randomness Model. In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the set
$$\{$$
LWE, DDH, N
$$^{th}$$
Residuosity
$$\}$$
.

#### Coauthors

- Saikrishna Badrinarayanan (2)
- Ran Gelles (1)
- Aayush Jain (1)
- Dakshita Khurana (1)
- Ilan Komargodski (2)
- Venkata Koppula (1)
- Yanyi Liu (1)
- Peter M. R. Rasmussen (1)
- Amit Sahai (3)
- Elaine Shi (2)
- Brent Waters (1)