## CryptoDB

### Jesper Buus Nielsen

#### Affiliation: University of Aarhus

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

TARDIS: A Foundation of Time-Lock Puzzles in UC
Abstract

Time-based primitives like time-lock puzzles (TLP) are finding widespread use in practical protocols, partially due to the surge of interest in the blockchain space where TLPs and related primitives are perceived to solve many problems. Unfortunately, the security claims are often shaky or plainly wrong since these primitives are used under composition. One reason is that TLPs are inherently not UC secure and time is tricky to model and use in the UC model. On the other hand, just specifying standalone notions of the intended task, left alone correctly using standalone notions like non-malleable TLPs only, might be hard or impossible for the given task. And even when possible a standalone secure primitive is harder to apply securely in practice afterwards as its behavior under composition is unclear. The ideal solution would be a model of TLPs in the UC framework to allow simple modular proofs. In this paper we provide a foundation for proving composable security of practical protocols using time-lock puzzles and related timed primitives in the UC model. We construct UC-secure TLPs based on random oracles and show that using random oracles is necessary. In order to prove security, we provide a simple and abstract way to reason about time in UC protocols. Finally, we demonstrate the usefulness of this foundation by constructing applications that are interesting in their own right, such as UC-secure two-party computation with output-independent abort.

2020

EUROCRYPT

Lower Bounds for Leakage-Resilient Secret Sharing
📺
Abstract

Threshold secret sharing allows a dealer to split a secret into $n$ shares such that any authorized subset of cardinality at least $t$ of those shares efficiently reveals the secret, while at the same time any unauthorized subset of cardinality less than $t$ contains no information about the secret. Leakage-resilience additionally requires that the secret remains hidden even if one is given a bounded amount of additional leakage from every share.
In this work, we study leakage-resilient secret sharing schemes and prove a lower bound on the share size and the required amount randomness of any information-theoretically secure scheme.
We prove that for any information-theoretically secure leakage-resilient secret sharing scheme either the amount of randomness across all shares or the share size has to be linear in $n$.
More concretely, for a secret sharing scheme with $p$-bit long shares, $\ell$-bit leakage per share, where $\widehat{t}$ shares uniquely define the remaining $n - \widehat{t}$ shares, it has to hold that $p \ge \frac{\ell (n - t)}{\widehat{t}}$.
We use this lower bound to gain further insights into a question that was recently posed by Benhamouda et al. (CRYPTO'18), who ask to what extend existing regular secret sharing schemes already provide protection against leakage.
The authors proved that Shamir's secret sharing is $1$-bit leakage-resilient for reconstruction thresholds $t \geq 0.85n$ and conjectured that it is also $1$-bit leakage-resilient for any other threshold that is a constant fraction of the total number of shares.
We do not disprove their conjecture, but show that it is the best one could possibly hope for.
Concretely, we show that for large enough $n$ and any constant $0< c < 1$ it holds that Shamir's secret sharing scheme is \emph{not} leakage-resilient for $t \leq \frac{cn}{\log n}$.
In contrast to the setting with information-theoretic security, we show that our lower bound does not hold in the computational setting.
That is, we show how to construct a leakage-resilient secret sharing scheme in the random oracle model that is secure against computationally bounded adversaries and violates the lower bound stated above.

2020

CRYPTO

Reverse Firewalls for Actively Secure MPCs
📺
Abstract

Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to ``sanitize'' the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a ``functionality-preserving way'' (i.e.~informally speaking, the functionality of the protocol remains unchanged under this attacks).
In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.
In this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a \emph{multi}party computation protocol (i.e.~it works for an arbitrary number $n$ of the parties, and not just for $2$). Secondly, it is secure in much stronger corruption settings, namely in the \emph{actively corruption model}. More precisely: we consider an adversary that can fully corrupt up to $n-1$ parties, while the remaining parties are corrupt in a functionality-preserving way.
Our core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001).

2020

JOFC

Continuously Non-malleable Codes in the Split-State Model
Abstract

Non-malleable codes (Dziembowski et al., ICS’10 and J. ACM’18) are a natural relaxation of error correcting/detecting codes with useful applications in cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a message can only leave it unchanged or modify it to the encoding of an unrelated value. This paper introduces continuous non-malleability, a generalization of standard non-malleability where the adversary is allowed to tamper continuously with the same encoding. This is in contrast to the standard definition of non-malleable codes, where the adversary can only tamper a single time. The only restriction is that after the first invalid codeword is ever generated, a special self-destruct mechanism is triggered and no further tampering is allowed; this restriction can easily be shown to be necessary. We focus on the split-state model, where an encoding consists of two parts and the tampering functions can be arbitrary as long as they act independently on each part. Our main contributions are outlined below. We show that continuous non-malleability in the split-state model is impossible without relying on computational assumptions. We construct a computationally secure split-state code satisfying continuous non-malleability in the common reference string (CRS) model. Our scheme can be instantiated assuming the existence of collision-resistant hash functions and (doubly enhanced) trapdoor permutations, but we also give concrete instantiations based on standard number-theoretic assumptions. We revisit the application of non-malleable codes to protecting arbitrary cryptographic primitives against related-key attacks. Previous applications of non-malleable codes in this setting required perfect erasures and the adversary to be restricted in memory. We show that continuously non-malleable codes allow to avoid these restrictions.

2019

EUROCRYPT

Continuous Non-Malleable Codes in the 8-Split-State Model
📺
Abstract

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs [20], provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography. In particular, progress in the study of non-malleable codes and the related notion of non-malleable extractors has led to new insights and progress on even more fundamental problems like the construction of multi-source randomness extractors. A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model. Many variants of NMCs have been introduced in the literature, e.g., strong NMCs, super strong NMCs and continuous NMCs. The most general, and hence also the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary. We present the first efficient information-theoretically secure continuously non-malleable code in the constant split-state model. We believe that our main technical result could be of independent interest and some of the ideas could in future be used to make progress on other related questions.

2019

CRYPTO

Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing
📺
Abstract

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation, both in the standard model with
$$n=2t+1$$
parties of which t are corrupted, and in the preprocessing model with
$$n=t+1$$
. In both cases, we show that for any
$$g \in \mathbb {N}$$
there exists a Boolean circuit C with g gates, where any secure protocol implementing C must communicate
$$\varOmega (n g)$$
bits, even if only passive and statistical security is required. The results easily extends to constructing similar circuits over any fixed finite field. This shows that for all sizes of circuits, the O(n) overhead of all known protocols when t is maximal is inherent. It also shows that security comes at a price: the circuit we consider could namely be computed among n parties with communication only O(g) bits if no security was required. Our results extend to the case where the threshold t is suboptimal. For the honest majority case, this shows that the known optimizations via packed secret-sharing can only be obtained if one accepts that the threshold is
$$t= (1/2 - c)n$$
for a constant c. For the honest majority case, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor
$$\lg n$$
off for Boolean circuits).

2019

CRYPTO

Stronger Leakage-Resilient and Non-Malleable Secret Sharing Schemes for General Access Structures
📺
Abstract

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structure as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing scheme guarantees that a secret that is reconstructed from a set of tampered shares is either equal to the original secret or completely unrelated. To the best of our knowledge we present the first generic compiler for leakage-resilient secret sharing for general access structures. In the case of non-malleable secret sharing, we strengthen previous definitions, provide separations between them, and construct a non-malleable secret sharing scheme for general access structures that fulfills the strongest definition with respect to independent share tampering functions. More precisely, our scheme is secure against concurrent tampering: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt can freely choose the qualified set of shares to be used by the reconstruction algorithm to reconstruct the tampered secret. This is a strong analogue of the multiple-tampering setting for split-state non-malleable codes and extractors.We show how to use leakage-resilient and non-malleable secret sharing schemes to construct leakage-resilient and non-malleable threshold signatures. Classical threshold signatures allow to distribute the secret key of a signature scheme among a set of parties, such that certain qualified subsets can sign messages. We construct threshold signature schemes that remain secure even if an adversary leaks from or tampers with all secret shares.

2018

CRYPTO

Yes, There is an Oblivious RAM Lower Bound!
📺 ★
Abstract

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM’96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized
$$\varOmega (\lg n)$$
bandwidth overhead lower bound for ORAMs with memory size n. Their lower bound is very strong in the sense that it applies to the “offline” setting in which the ORAM knows the entire sequence of operations ahead of time.However, as pointed out by Boyle and Naor [ITCS’16] in the paper “Is there an oblivious RAM lower bound?”, there are two caveats with the lower bound of Goldreich and Ostrovsky: (1) it only applies to “balls in bins” algorithms, i.e., algorithms where the ORAM may only shuffle blocks around and not apply any sophisticated encoding of the data, and (2), it only applies to statistically secure constructions. Boyle and Naor showed that removing the “balls in bins” assumption would result in super linear lower bounds for sorting circuits, a long standing open problem in circuit complexity. As a way to circumventing this barrier, they also proposed a notion of an “online” ORAM, which is an ORAM that remains secure even if the operations arrive in an online manner. They argued that most known ORAM constructions work in the online setting as well.Our contribution is an
$$\varOmega (\lg n)$$
lower bound on the bandwidth overhead of any online ORAM, even if we require only computational security and allow arbitrary representations of data, thus greatly strengthening the lower bound of Goldreich and Ostrovsky in the online setting. Our lower bound applies to ORAMs with memory size n and any word size
$$r \ge 1$$
. The bound therefore asymptotically matches the known upper bounds when
$$r = \varOmega (\lg ^2 n)$$
.

2015

EPRINT

2014

EPRINT

2010

EPRINT

Perfectly Secure Oblivious RAM Without Random Oracles
Abstract

We present an algorithm for implementing a secure oblivious
RAM where the access pattern is perfectly hidden in the information
theoretic sense, without assuming that the CPU has access to a random
oracle. In addition we prove a lover bound on the amount of randomness
needed for information theoretically secure oblivious RAM.

2008

EPRINT

Multiparty Computation Goes Live
Abstract

In this note, we briefly report on the first large-scale and practical application of multiparty computation, which took place in January 2008.

2008

EPRINT

Essentially Optimal Universally Composable Oblivious Transfer
Abstract

Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters:
Security: it has universal composition.
Trust in setup assumptions: only one of the parties needs to trust the setup and some setup is needed for UC security.
Trust in computational assumptions: only one of the parties needs to trust a computational assumption.
Round complexity: it uses only two rounds.
Communication complexity: it communicates O(1) group elements to transfer one out of two group elements.
The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant.
Our construction is based on pairings, and we assume the presence of a key registration authority.

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.

2008

EPRINT

LEGO for Two Party Secure Computation
Abstract

The first and still most popular solution for secure two-party
computation relies on Yao's garbled circuits. Unfortunately, Yao's
construction provide security only against passive adversaries.
Several constructions (zero-knowledge compiler, cut-and-choose) are
known in order to provide security against active adversaries, but
most of them are not efficient enough to be considered practical. In
this paper we propose a new approach called LEGO (Large Efficient
Garbled-circuit Optimization) for two-party computation, which allows
to construct more efficient protocols secure against active
adversaries. The basic idea is the following: Alice constructs and
provides Bob a set of garbled NAND gates. A fraction of them is
checked by Alice giving Bob the randomness used to construct
them. When the check goes through, with overwhelming probability there
are very few bad gates among the non-checked gates. These gates Bob
permutes and connects to a Yao circuit, according to a fault-tolerant
circuit design which computes the desired function even in the
presence of a few random faulty gates. Finally he evaluates this Yao
circuit in the usual way.
For large circuits, our protocol offers better performance than any
other existing protocol.
The protocol is universally composable (UC) in the OT-hybrid model.

2007

EPRINT

Extending Oblivious Transfers Efficiently - How to get Robustness Almost for Free
Abstract

At Crypto 2003 Ishai et al. gave a protocol which given a
small number of (possibly extremely inefficient) oblivious transfers
implements an essentially unbounded number of oblivious transfers
for an additional overhead, per oblivious transfer, of computing and
sending only two hash values. This highly efficient protocol is
however only passive secure. To get active security, except with
probability $2^{-m}$, the protocol had to suffer an additional
overhead of a factor $1+m$. We introduce a new approach to adding
robustness. For practical security parameters this approach allows
to add robustness while suffering only a small constant overhead
over the passive secure protocol. As an example we can generate one
million oblivious transfers with security $2^{-42}$ with an
amortized cost of just $9$ hash values per oblivious transfer.

2007

EPRINT

Isolated Proofs of Knowledge and Isolated Zero Knowledge
Abstract

We introduce a new notion called $\ell$-isolated proofs of knowledge
($\ell$-IPoK). These are proofs of knowledge where a cheating prover
is allowed to exchange up to $\ell$ bits of communication with some
external adversarial environment during the run of the proof.
Without any additional setup assumptions, no witness hiding protocol can be an $\ell$-IPoK for \emph{unbounded} values of $\ell$.
However, for any \emph{pre-defined} threshold $\ell$, and any relation in NP and we construct
an $\ell$-IPoK protocol for that relation. The resulting protocols
are zero knowledge (ZK) in the standard sense, i.e.,
w.r.t. a verifier that communicates only with the prover during the proof.
The cost of having a large threshold $\ell$ is a large communication complexity of the constructed protocol.
We analyze these costs and present a solution that is asymptotically optimal.
If a cheating verifier is allowed to communicate arbitrarily with an
external environment, it is not possible to construct an $\ell$-IPoK that
is also ZK with respect to such a verifier. As another new notion,
we define $\ell$-isolated zero knowledge ($\ell$-IZK) where the
verifier is $\ell$-isolated. For every relation in NP and
every $\ell$, we construct an $\ell$-IPoK protocol that is
also $\ell$-IZK.
We describe several applications of $\ell$-IPoK protocols
under the physical assumption that one can $\ell$-isolate a prover for
the duration of the proof phase. Firstly, we can use a witness
indistinguishable (WI) $\ell$-IPoK to prevent ``man-in-the-middle''
attacks on identification schemes. Prior results for this scenario
required all verifiers to register keys under a PKI, or the ability to fully
isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI $\ell$-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.

2007

EPRINT

Universally Composable Multiparty Computation with Partially Isolated Parties
Abstract

It is well known that universally composable multiparty computation
cannot, in general, be achieved in the standard model without setup
assumptions when the adversary can corrupt an arbitrary number of
players. One way to get around this problem is by having a trusted
third party generate some global setup such as a common reference
string (CRS) or a public key infrastructure (PKI). Recently, an
alternative solution was proposed by Katz in \cite{Katz}, suggesting
that one may rely on physical assumptions rather than trusted third
parties. Concretely, the solution assumed it physically possible to
construct tamper proof hardware tokens which can be run in complete
isolation from the surrounding environment. Here we improve upon the
work of \cite{Katz} by constructing a scheme in which the tokens
only need to be partially isolated and may have some {\em limited
communication with the environment}. In addition we improve on
Katz's work by presenting a scheme which is secure against
\emph{adaptive adversaries} and is based on \emph{general
cryptographic assumptions}. We also consider an alternative
scenario, in which there are some trusted third parties but no
single such party is trusted by all of the players. This compromise
allows us to limit the use of the physical set-up and hence might be
preferred in practice.

2005

ASIACRYPT

2005

EUROCRYPT

2005

EPRINT

How to Split a Shared Secret into Shared Bits in Constant-Round
Abstract

We show that if a set of players hold shares of a value $a\in Z_p$
for some prime $p$ (where the set of shares is written $[a]_p$), it
is possible to compute, in constant round and with unconditional
security, sharings of the bits of $a$, i.e.~compute sharings
$[a_0]_p, \ldots, [a_{l-1}]_p$ such that $l = \lceil \log_2(p)
\rceil$, $a_0, \ldots, a_{l-1} \in \{0,1\}$ and $a =
\sum_{i=0}^{l-1} a_i 2^i$. Our protocol is secure against active
adversaries and works for any linear secret sharing scheme with a
multiplication protocol.
This result immediately implies solutions to other long-standing
open problems, such as constant-round and unconditionally secure
protocols for comparing shared numbers and deciding whether a shared
number is zero.
The complexity of our protocol is $O(l \log(l))$
invocations of the multiplication protocol for the underlying secret
sharing scheme, carried out in $O(1)$.

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.

2003

CRYPTO

2003

EPRINT

Relaxing Chosen-Ciphertext Security
Abstract

Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security
notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat {\em too strong:} there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure ``for most practical purposes.''
We propose a relaxed variant of CCA security, called {\sf Replayable CCA (RCCA)} security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security.
We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches,
respectively. We show that the three formulations are equivalent in most interesting cases.

2002

CRYPTO

2002

CRYPTO

2002

CRYPTO

2001

EPRINT

Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor
Abstract

Canetti and Fischlin have recently proposed the security notion {\em
universal composability} for commitment schemes and provided two
examples. This new notion is very strong. It guarantees that security
is maintained even when an unbounded number of copies of the scheme
are running concurrently, also it guarantees non-malleability,
resilience to selective decommitment, and security against adaptive
adversaries. Both of their schemes uses $\Theta(k)$ bits to commit to
one bit and can be based on the existence of trapdoor commitments and
non-malleable encryption.
We present new universally composable commitment schemes based on the
Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The
schemes are efficient: to commit to $k$ bits, they use a constant
number of modular exponentiations and communicates $O(k)$
bits. Further more the scheme can be instantiated in either perfectly
hiding or perfectly binding versions. These are the first schemes to
show that constant expansion factor, perfect hiding, and perfect
binding can be obtained for universally composable commitments.
We also show how the schemes can be applied to do efficient
zero-knowledge proofs of knowledge that are universally composable.

2000

EPRINT

Multiparty Computation from Threshold Homomorphic Encryption
Abstract

We introduce a new approach to multiparty computation (MPC)
basing it on homomorphic
threshold crypto-systems. We show that given keys for any
sufficiently efficient
system of this type, general MPC protocols for $n$ players can be
devised which are
secure against an active adversary that corrupts any minority of the
players.
The total number of bits sent is $O(nk|C|)$, where $k$ is the
security parameter and $|C|$ is
the size of a (Boolean) circuit computing the function to be
securely evaluated.
An earlier proposal by Franklin and Haber with the same complexity
was only secure
for passive adversaries, while all earlier protocols with active
security had complexity at
least quadratic in $n$. We give two examples of threshold
cryptosystems that can support our
construction and lead to the claimed complexities.

#### Program Committees

- TCC 2020
- Eurocrypt 2018
- Eurocrypt 2017
- PKC 2016
- TCC 2015
- Asiacrypt 2014
- PKC 2014
- Eurocrypt 2013
- Crypto 2013
- TCC 2012
- PKC 2011
- Asiacrypt 2011
- Crypto 2011
- Asiacrypt 2010
- Crypto 2010
- PKC 2009
- Crypto 2009
- PKC 2008
- Asiacrypt 2007
- Eurocrypt 2007
- TCC 2006
- Asiacrypt 2004

#### Coauthors

- Divesh Aggarwal (2)
- Jesús F. Almansa (1)
- Carsten Baum (1)
- Zuzana Beerliová-Trubíniová (1)
- Rikke Bendlin (1)
- Peter Bogetoft (1)
- Sai Sheshank Burra (2)
- Ran Canetti (2)
- Ignacio Cascudo (2)
- Suvradip Chakraborty (1)
- Dan Lund Christensen (1)
- Ronald Cramer (2)
- Ivan Damgård (37)
- Bernardo Machado David (2)
- Bernardo David (3)
- Yvo Desmedt (1)
- Nico Döttling (2)
- Rafael Dowsley (1)
- Frédéric Dupuis (3)
- Stefan Dziembowski (1)
- Antonio Faonio (4)
- Sebastian Faust (7)
- Matthias Fitzi (3)
- Tore Kasper Frederiksen (7)
- Martin Geisler (3)
- Satrajit Ghosh (1)
- Irene Giacomelli (3)
- Danny Harnik (1)
- Carmit Hazay (2)
- Martin Hirt (6)
- Pavel Hubáček (1)
- Yuval Ishai (2)
- Thomas Jakobsen (1)
- Thomas P. Jakobsen (4)
- Thomas Pelle Jakobsen (1)
- Eike Kiltz (1)
- Hugo Krawczyk (2)
- Mikkel Krøigaard (3)
- Eyal Kushilevitz (1)
- Enrique Larraia (1)
- Kasper Green Larsen (2)
- Sigurd Meldgaard (2)
- Peter Bro Miltersen (1)
- Pratyay Mukherjee (5)
- Janus Dam Nielsen (1)
- Michael Nielsen (1)
- Kurt Nielsen (1)
- Tobias Nilges (1)
- Peter Sebastian Nordholt (6)
- Maciej Obremski (2)
- Sabine Oechsner (1)
- Claudio Orlandi (11)
- Emmanuela Orsini (1)
- Rafail Ostrovsky (1)
- Jakob Pagter (1)
- Antigoni Polychroniadou (1)
- Bartosz Przydatek (2)
- Erick Purwanto (2)
- Samuel Ranellucci (4)
- Michael Raskin (1)
- João Ribeiro (1)
- Alon Rosen (1)
- Adi Rosén (1)
- Louis Salvail (2)
- Peter Scholl (1)
- Michael Schwartzbach (1)
- Mark Simkin (2)
- Nigel P. Smart (1)
- Adam Smith (1)
- Mario Strefler (1)
- Tomas Toft (3)
- Nikos Triandopoulos (1)
- Roberto Trifiletti (4)
- Daniele Venturi (11)
- Daniel Wichs (4)
- Angela Zottarel (6)