## CryptoDB

### Jesper Buus Nielsen

#### Affiliation: University of Aarhus

#### Publications

**Year**

**Venue**

**Title**

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

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

#### Coauthors

- Divesh Aggarwal (2)
- Jesús F. Almansa (1)
- Zuzana Beerliová-Trubíniová (1)
- Rikke Bendlin (1)
- Peter Bogetoft (1)
- Sai Sheshank Burra (2)
- Ran Canetti (2)
- Ignacio Cascudo (2)
- Dan Lund Christensen (1)
- Ronald Cramer (2)
- Ivan Damgård (37)
- Bernardo Machado David (2)
- Bernardo David (2)
- Yvo Desmedt (1)
- Nico Döttling (2)
- Frédéric Dupuis (3)
- Antonio Faonio (4)
- Sebastian Faust (6)
- 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ácek (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 (4)
- Janus Dam Nielsen (1)
- Michael Nielsen (1)
- Kurt Nielsen (1)
- Tobias Nilges (1)
- Peter Sebastian Nordholt (6)
- Maciej Obremski (2)
- 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 (1)
- Nigel P. Smart (1)
- Adam Smith (1)
- Mario Strefler (1)
- Tomas Toft (3)
- Nikos Triandopoulos (1)
- Roberto Trifiletti (4)
- Daniele Venturi (10)
- Daniel Wichs (4)
- Angela Zottarel (6)