CryptoDB
Ran Gelles
Publications and invited talks
Year
Venue
Title
2025
CRYPTO
Nearly Optimal Parallel Broadcast in the Plain Public Key Model
Abstract
Parallel Byzantine broadcast (PBC) (also known as Interactive Consistency), is a fundamental problem in distributed computing and cryptography which asks that all parties reliably distribute a message to all other parties. We give the first communication-efficient protocol for PBC in the model with plain public keys (i.e., no trusted dealer) which achieves security against an adaptive adversary that can corrupt up to $t<n/2$ parties.
Our protocol runs in total communication complexity $O(n^2\ell\log(n)+n\kappa^2\log^4(n))$ bits to succeed with probability $1-2^{-\kappa}$, where $\ell$ is the length of a message. All prior protocols either rely on a trusted setup or require at least $O(n^3)$ communication complexity. As a stepping stone, we present a binary consensus protocol with the same resilience and success probability that sends $O(n^2\kappa\log(n)+n\kappa^2\log^3(n))$ bits.
We achieve these results based on a highly efficient gossip procedure that implements echo operations at low cost, and might prove useful in deriving further efficient protocols relying on simple cryptographic tools.
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.
Coauthors
- Harry Buhrman (1)
- Nishanth Chandran (1)
- Serge Fehr (1)
- Rex Fernando (1)
- Matthew K. Franklin (1)
- Juan A. Garay (1)
- Ran Gelles (5)
- Vipul Goyal (1)
- David S. Johnson (1)
- Aggelos Kiayias (1)
- Ilan Komargodski (1)
- Christoph Lenzen (1)
- Julian Loss (1)
- Rafail Ostrovsky (2)
- Christian Schaffner (1)
- Leonard J. Schulman (1)
- Elaine Shi (1)
- Sravya Yandamuri (1)
- Moti Yung (1)