## CryptoDB

### Martin Hirt

#### Publications

**Year**

**Venue**

**Title**

2021

TCC

Round-Efficient Byzantine Agreement and Multi-Party Computation with Asynchronous Fallback
📺
Abstract

Protocols for Byzantine agreement (BA) and secure multi-party computation (MPC) can be classified according to the underlying communication model. The two most commonly considered models are the synchronous one and the asynchronous one. Synchronous protocols typically lose their security guarantees as soon as the network violates the synchrony assumptions. Asynchronous protocols remain secure regardless of the network conditions, but achieve weaker security guarantees even when the network is synchronous.
Recent works by Blum, Katz and Loss [TCC'19], and Blum, Liu-Zhang and Loss [CRYPTO'20] introduced BA and MPC protocols achieving security guarantees in both settings: security up to $t_s$ corruptions in a synchronous network, and up to $t_a$ corruptions in an asynchronous network, under the provably optimal threshold trade-offs $t_a \le t_s$ and $t_a + 2t_s < n$. However, current solutions incur a high synchronous round complexity when compared to state-of-the-art purely synchronous protocols. When the network is synchronous, the round complexity of BA protocols is linear in the number of parties, and the round complexity of MPC protocols also depends linearly on the depth of the circuit to evaluate.
In this work, we provide round-efficient constructions for both primitives with optimal resilience: fixed-round and expected constant-round BA protocols, and an MPC protocol whose round complexity is independent of the circuit depth.

2021

TCC

Adaptive Security of Multi-Party Protocols, Revisited
📺
Abstract

The goal of secure multi-party computation (MPC) is to allow a set of parties to perform an arbitrary computation task, where the security guarantees depend on the set of parties that are corrupted. The more parties are corrupted, the less is guaranteed, and typically the guarantees are completely lost when the number of corrupted parties exceeds a certain corruption bound.
Early and also many recent protocols are only statically secure in the sense that they provide no security guarantees if the adversary is allowed to choose adaptively which parties to corrupt. Security against an adversary with such a strong capability is often called adaptive security and a significant body of literature is devoted to achieving adaptive security, which is known as a difficult problem. In particular, a main technical obstacle in this context is the so-called ``commitment problem'', where the simulator is unable to consistently explain the internal state of a party with respect to its pre-corruption outputs. As a result, protocols typically resort to the use of cryptographic primitives like non-committing encryption, incurring a substantial efficiency loss.
This paper provides a new, clean-slate treatment of adaptive security in MPC, exploiting the specification concept of constructive cryptography (CC). A new natural security notion, called \cc-adaptive security, is proposed, which is technically weaker than standard adaptive security but nevertheless captures security against a fully adaptive adversary. Known protocol examples separating between adaptive and static security are also insecure in our notion. Moreover, our notion avoids the commitment problem and thereby the need to use non-committing or equivocal tools.
We exemplify this by showing that the protocols by Cramer, Damgard and Nielsen (EUROCRYPT'01) for the honest majority setting, and (the variant without non-committing encryption) by Canetti, Lindell, Ostrovsky and Sahai (STOC'02) for the dishonest majority setting, achieve \cc-adaptive security. The latter example is of special interest since all \uc-adaptive protocols in the dishonest majority setting require some form of non-committing encryption or equivocal tools.

2021

TCC

On Communication-Efficient Asynchronous MPC with Adaptive Security
📺
Abstract

Secure multi-party computation (MPC) allows a set of $n$ parties to jointly compute an arbitrary computation over their private inputs. Two main variants have been considered in the literature according to the underlying communication model. Synchronous MPC protocols proceed in rounds, and rely on the fact that the communication network provides strong delivery guarantees within each round. Asynchronous MPC protocols achieve security guarantees even when the network delay is arbitrary.
While the problem of MPC has largely been studied in both variants with respect to both feasibility and efficiency results, there is still a substantial gap when it comes to communication complexity of adaptively secure protocols. Concretely, while adaptively secure synchronous MPC protocols with linear communication are known for a long time, the best asynchronous protocol communicates $\mathcal{O}(n^4 \kappa)$ bits per multiplication.
In this paper, we make progress towards closing this gap by providing two protocols. First, we present an adaptively secure asynchronous protocol with optimal resilience $t<n/3$ and $\mathcal{O}(n^2 \kappa)$ bits of communication per multiplication, improving over the state of the art protocols in this setting by a quadratic factor in the number of parties. The protocol has cryptographic security and follows the CDN approach [Eurocrypt'01], based on additive threshold homomorphic encryption.
Second, we show an optimization of the above protocol that tolerates up to $t<(1-\epsilon)n/3$ corruptions and communicates $\mathcal{O}(n\cdot \poly(\kappa))$ bits per multiplication under stronger assumptions.

2013

CRYPTO

2008

EPRINT

Almost-Asynchronous MPC with Faulty Minority
Abstract

Secure multiparty computation (MPC) allows a set of parties to
securely evaluate any agreed function of their inputs, even when up
to $t$ of the $n$ parties are faulty. Protocols for synchronous
networks (where every sent message is assumed to arrive within a
constant time) tolerate up to $t<n/2$ faulty parties, whereas in the
more realistic asynchronous setting (with no \emph{a priory}
information on maximal message delay) only security against $t<n/3$
is possible. We present the first protocol that achieves security
against $t<n/2$ without assuming a fully synchronous network.
Actually our protocol guarantees security against any faulty
minority in an \emph{almost asynchronous} network, i.e. in a network
with one single round of synchronous broadcast (followed by a fully
asynchronous communication). Furthermore our protocol takes inputs
of all parties (in a fully asynchronous network only inputs of $n-t$
parties can be guaranteed), and so achieves everything that is
possible in synchronous networks (but impossible in fully
asynchronous networks) at the price of just one synchronous
broadcast round.
As tools for our protocol we introduce the notions of \emph{almost
non-interactive verifiable secret-sharing} and \emph{almost
non-interactive zero-knowledge proof of knowledge}, which are of
independent interest as they can serve as efficient replacements for
fully non-interactive verifiable secret-sharing and fully
non-interactive zero-knowledge proof of knowledge.

2007

EPRINT

MPC vs. SFE: Perfect Security in a Unified Corruption Model
Abstract

Secure function evaluation (SFE) allows a set of players to compute
an arbitrary agreed function of their private inputs, even if an
adversary may corrupt some of the players. Secure multi-party
computation (MPC) is a generalization allowing to perform an
arbitrary on-going (also called reactive or stateful) computation
during which players can receive outputs and provide new inputs at
intermediate stages.
At Crypto~2006, Ishai \emph{et al.} considered mixed threshold
adversaries that either passively corrupt some fixed number of players,
or, alternatively, actively corrupt some (smaller) fixed number of
players, and showed that for certain thresholds, cryptographic SFE is
possible, whereas cryptographic MPC is not.
However, this separation does not occur when one considers
\emph{perfect} security. Actually, past work suggests that no such
separation exists, as all known general protocols for perfectly secure SFE
can also be used for MPC. Also, such a separation does not show up with
\emph{general adversaries}, characterized by a collection of corruptible
subsets of the players, when considering passive and active corruption.
In this paper, we study the most general corruption model where the
adversary is characterized by a collection of adversary classes, each
specifying the subset of players that can be actively, passively, or
fail-corrupted, respectively, and show that in this model, perfectly
secure MPC separates from perfectly secure SFE. Furthermore, we derive
the exact conditions on the adversary structure for the existence of
perfectly secure SFE resp.~MPC, and provide efficient protocols for both
cases.

2005

ASIACRYPT

2005

EUROCRYPT

2004

EPRINT

Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation
Abstract

We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an $n$-party randomized function and show that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2 \kappa)$ is an upper bound for active security with optimal resilience $t < n/2$ and security parameter $\kappa$. This improves on the communication complexity of previous protocols by a factor of at least $n$. This improvement comes from the fact that in the new protocol, only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during the \emph{whole} protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts \emph{per gate}.
Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience $t<n$ from $\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to a simple observation.

2004

EPRINT

Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience
Abstract

We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead.
One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.

2002

EPRINT

Extended Validity and Consistency in Byzantine Agreement
Abstract

A broadcast protocol allows a sender to distribute a value among a set of
players such that it is guaranteed that all players receive the same
value (consistency), and if the sender is honest, then all players
receive the sender's value (validity). Classical broadcast protocols for
$n$ players provide security with respect to a fixed threshold $t<n/3$,
where both consistency and validity are guaranteed as long as at most $t$
players are corrupted, and no security at all is guaranteed as soon as
$t+1$ players are corrupted. Depending on the environment, validity or
consistency may be the more important property.
We generalize the notion of broadcast by introducing an additional
threshold $t^+\ge t$. In a {\em broadcast protocol with extended
validity}, both consistency and validity are achieved when no more than
$t$ players are corrupted, and validity is achieved even when up to $t^+$
players are corrupted. Similarly, we define {\em broadcast with extended
consistency}. We prove that broadcast with extended validity as well as
broadcast with extended consistency is achievable if and only if
$t+2t^+<n$ (or $t=0$).
For example, six players can achieve broadcast when at most one player is
corrupted (this result was known to be optimal), but they can even
achieve consistency (or validity) when two players are corrupted.
Furthermore, our protocols achieve {\em detection} in case of failure,
i.e., if at most $t$ players are corrupted then broadcast is achieved,
and if at most $t^+$ players are corrupted then broadcast is achieved or
every player learns that the protocol failed. This protocol can be
employed in the precomputation of a secure multi-party computation
protocol, resulting in {\em detectable multi-party computation}, where up
to $t$ corruptions can be tolerated and up to $t^+$ corruptions can
either be tolerated or detected in the precomputation, for any $t,t^+$
with $t+2t^+<n$.

2001

EPRINT

Robustness for Free in Unconditional Multi-Party Computation
Abstract

We present a very efficient multi-party computation protocol
unconditionally secure against an active adversary. The security is
maximal, i.e., active corruption of up to $t<n/3$ of the $n$ players is
tolerated. The communication complexity for securely evaluating a circuit
with $m$ multiplication gates over a finite field is $\O(mn^2)$ field
elements, including the communication required for simulating broadcast.
This corresponds to the complexity of the best known protocols for the
passive model, where the corrupted players are guaranteed not to deviate
from the protocol. Even in this model, it seems to be unavoidable that
for every multiplication gate every player must send a value to every
other player, and hence the complexity of our protocol may well be
optimal. The constant overhead factor for robustness is small and the
protocol is practical.

1998

CRYPTO

#### Program Committees

- TCC 2018
- Eurocrypt 2018
- Eurocrypt 2016
- TCC 2015
- TCC 2014
- Eurocrypt 2013
- TCC 2012
- PKC 2011
- Crypto 2007
- Eurocrypt 2006
- PKC 2005
- Eurocrypt 2001

#### Coauthors

- Joël Alwen (2)
- Zuzana Beerliová-Trubíniová (7)
- Annick Chopard (1)
- Sandro Coretti (1)
- Ronald Cramer (1)
- Ivan Damgård (1)
- Giovanni Deligios (1)
- Gregory Demay (1)
- Stefan Dziembowski (1)
- Matthias Fitzi (6)
- Juan A. Garay (1)
- Peter Gaži (1)
- Thomas Holenstein (2)
- Chen-Da Liu-Zhang (3)
- Christoph Lucas (1)
- Ueli Maurer (16)
- Jesper Buus Nielsen (6)
- Arpita Patra (2)
- Bartosz Przydatek (3)
- Tal Rabin (1)
- Pavel Raykov (4)
- Micha Riser (1)
- Kazue Sako (1)
- Daniel Tschudi (2)
- Jürg Wullschleger (2)
- Vassilis Zikas (6)