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.
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 (2)
- Dakshita Khurana (1)
- Ilan Komargodski (3)
- Venkata Koppula (1)
- Yanyi Liu (1)
- Peter M. R. Rasmussen (1)
- Amit Sahai (3)
- Elaine Shi (2)
- Brent Waters (1)