## CryptoDB

### Rex Fernando

#### Publications

**Year**

**Venue**

**Title**

2023

EUROCRYPT

Maliciously-Secure MrNISC in the Plain Model
Abstract

We study strong versions of round-optimal MPC.
A recent work of Benhamouda and Lin (TCC '20)
identified a version of secure multiparty computation (MPC), termed
Multiparty reusable Non-Interactive Secure Computation (MrNISC),
that combines at the same time several fundamental aspects of secure
computation with standard simulation security into one primitive:
round-optimality, succinctness, concurrency, and adaptivity. In more
detail, MrNISC is essentially a two-round MPC protocol where the first
round of messages serves as a reusable commitment to the private inputs
of participating parties. Using these commitments, any subset of parties
can later compute any function of their choice on their respective inputs
by broadcasting one message each. Anyone who sees these parties'
commitments and evaluation messages (even an outside observer) can learn
the function output and nothing else. Importantly, the input commitments
can be computed without knowing anything about other participating
parties (neither their identities nor their number) and they are reusable
across any number of computations.
By now, there are several known MrNISC protocols from either (bilinear)
group-based assumptions or from LWE. They all satisfy semi-malicious
security (in the plain model) and require trusted setup assumptions in
order to get malicious security. We are interested in maliciously secure
MrNISC protocols in the plain model, without trusted setup. Since
the standard notion of polynomial simulation is un-achievable in less
than four rounds, we focus on security with \emph{super-polynomial}-time
simulation (SPS).
Our main result is the first maliciously secure SPS MrNISC in the plain
model. The result is obtained by generically compiling any
semi-malicious MrNISC and the security of our compiler relies on several
well-studied assumptions of an indistinguishability obfuscator, DDH over Z^*_p and asymmetric pairing groups,
and a time-lock puzzle (all of which need to be sub-exponentially hard).
As a special case, we obtain the first 2-round maliciously secure SPS
MPC based on well-founded assumptions. This MPC is also concurrently
self-composable and its first message is short (i.e., its size is
independent of the number of the participating parties) and reusable
throughout any number of computations. Prior to our work, for two round maliciously secure MPC, neither concurrent MPC nor reusable MPC nor MPC with first message independent in the number of parties was known from any set of assumptions. Of independent interest is one of our building blocks: the first construction of a one-round non-malleable commitment scheme from well-studied assumptions, avoiding keyless hash functions and non-standard hardness amplification assumptions.

2023

ASIACRYPT

Two-Round Concurrent 2PC from Sub-Exponential LWE
Abstract

Secure computation is a cornerstone of modern cryptography and a rich body of research is devoted to understanding its round complexity. In this work, we consider two-party computation (2PC) protocols (where both parties receive output) that remain secure in the realistic setting where many instances of the protocol are executed in parallel (concurrent security). We obtain a two-round concurrent-secure 2PC protocol based on a single, standard, post-quantum assumption: The subexponential hardness of the learning-with-errors (LWE) problem. Our protocol is in the plain model, i.e., it has no trusted setup, and it is secure in the super-polynomial simulation framework of Pass (EUROCRYPT 2003). Since two rounds are minimal for (concurrent) 2PC, this work resolves the round complexity of concurrent 2PC from standard assumptions.
As immediate applications, our work establishes feasibility results for interesting cryptographic primitives such as the first two-round password authentication key exchange (PAKE) protocol in the plain model and the first two-round concurrent secure computation protocol for quantum circuits (2PQC).

2023

TCC

Non-Interactive Anonymous Router with Quasi-Linear Router Computation
Abstract

Anonymous routing is an important cryptographic primitive that allows users to communicate privately on the Internet, without revealing their message contents or their contacts. Until the very recent work of Shi and Wu (Eurocrypt’21), all classical anonymous routing schemes are interactive protocols, and their security rely on a threshold number of the routers being honest. The recent work of Shi and Wu suggested a new abstraction called Non-Interactive Anonymous Router (NIAR), and showed how to achieve anonymous routing non-interactively for the first time. In particular, a single untrusted router receives a token which allows it to obliviously apply a permutation to a set of encrypted messages from the senders. Shi and Wu’s construction suffers from two drawbacks: 1) the router takes time quadratic in the number of senders to obliviously route their messages; and 2) the scheme is proven secure only in the presence of static corruptions.
In this work, we show how to construct a non-interactive anonymous router scheme with sub-quadratic router computation, and achieving security in the presence of adaptive corruptions. To get this result, we assume the existence of indistinguishability obfuscation and one-way functions. Our final result is obtained through a sequence of stepping stones. First, we show how to achieve the desired efficiency, but with security under static corruption and in a selective, single-challenge setting. Then, we go through a sequence of upgrades which eventually get us the final result. We devise various new techniques along the way which lead to some additional results. In particular, our techniques for reasoning about a network of obfuscated programs may be of independent interest.

2023

TCC

Distributed-Prover Interactive Proofs
Abstract

Interactive proof systems enable a verifier with limited resources to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee soundness: the prover can only convince the verifier of true statements. This is a central notion in computer science with far-reaching implications. One key drawback of the classical model is that the data on which the prover operates must be held by a single machine.
In this work, we initiate the study of distributed-prover interactive proofs (dpIPs):
an untrusted cluster of machines, acting as a distributed prover, interacts with a single verifier. The machines in the cluster jointly store and operate on a massive data-set that no single machine can store. The goal is for the machines in the cluster to convince the verifier of the validity of some statement about its data-set. We formalize the communication and space constraints via the massively parallel computation (MPC) model, a widely accepted analytical framework capturing the computational power of massive data-centers.
Our main result is a compiler that generically augments any verification algorithm in the MPC model with a soundness guarantee. Concretely, for any language $L$ for which there is an MPC algorithm verifying whether $x{\in} L$, we design a new MPC protocol capable of convincing a verifier of the validity of $x\in L$ and where if $x\not\in L$, the verifier will reject almost surely reject, no matter what. The new protocol requires only slightly more rounds, i.e., a $\mathsf{poly}(\log N)$ blowup, and a slightly bigger memory per machine, i.e., $\mathsf{poly}(\lambda)$ blowup, where $N$ is the total size of the dataset and $\lambda$ is a security parameter independent of $N$.
En route, we introduce distributed-prover interactive oracle proofs (dpIOPs), a natural adaptation of the (by now classical) IOP model to the distributed prover setting. We design a dpIOP for algorithms in the MPC model and then tranlate them to ``plain model'' dpIPs via an adaptation of existing polynomial commitment schemes into the distributed prover setting.

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

- Behzad Abdolmaleki (1)
- Saikrishna Badrinarayanan (3)
- Sourav Das (1)
- Ran Gelles (1)
- Aayush Jain (2)
- Dakshita Khurana (1)
- Ilan Komargodski (4)
- Venkata Koppula (1)
- Yanyi Liu (1)
- Giulio Malavolta (1)
- Ahmadreza Rahimi (1)
- Peter M. R. Rasmussen (1)
- Amit Sahai (4)
- Elaine Shi (4)
- Pratik Soni (2)
- Nikhil Vanjani (1)
- Brent Waters (2)