## CryptoDB

### Stefan Dziembowski

#### Affiliation: University of Warsaw

#### Publications

**Year**

**Venue**

**Title**

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).

2019

EUROCRYPT

Multi-party Virtual State Channels
📺
Abstract

Smart contracts are self-executing agreements written in program code and are envisioned to be one of the main applications of blockchain technology. While they are supported by prominent cryptocurrencies such as Ethereum, their further adoption is hindered by fundamental scalability challenges. For instance, in Ethereum contract execution suffers from a latency of more than 15 s, and the total number of contracts that can be executed per second is very limited. State channel networks are one of the core primitives aiming to address these challenges. They form a second layer over the slow and expensive blockchain, thereby enabling instantaneous contract processing at negligible costs.In this work we present the first complete description of a state channel network that exhibits the following key features. First, it supports virtual multi-party state channels, i.e. state channels that can be created and closed without blockchain interaction and that allow contracts with any number of parties. Second, the worst case time complexity of our protocol is constant for arbitrary complex channels. This is in contrast to the existing virtual state channel construction that has worst case time complexity linear in the number of involved parties. In addition to our new construction, we provide a comprehensive model for the modular design and security analysis of our construction.

2019

ASIACRYPT

Simple Refreshing in the Noisy Leakage Model
Abstract

Masking schemes are a prominent countermeasure against power analysis and work by concealing the values that are produced during the computation through randomness. The randomness is typically injected into the masked algorithm using a so-called refreshing scheme, which is placed after each masked operation, and hence is one of the main bottlenecks for designing efficient masking schemes. The main contribution of our work is to investigate the security of a very simple and efficient refreshing scheme and prove its security in the noisy leakage model (EUROCRYPT’13). Compared to earlier constructions our refreshing is significantly more efficient and uses only n random values and $${<}2n$$ operations, where n is the security parameter. In addition we show how our refreshing can be used in more complex masked computation in the presence of noisy leakage. Our results are established using a new methodology for analyzing masking schemes in the noisy leakage model, which may be of independent interest.

2019

JOFC

Unifying Leakage Models: From Probing Attacks to Noisy Leakage
Abstract

A recent trend in cryptography is to formally show the leakage resilience of cryptographic implementations in a given leakage model. One of the most prominent leakage model—the so-called bounded leakage model—assumes that the amount of leakage that an adversary receives is a-priori bounded. Unfortunately, it has been pointed out by several works that the assumption of bounded leakages is hard to verify in practice. A more realistic assumption is to consider that leakages are sufficiently noisy, following the engineering observation that real-world physical leakages are inherently perturbed by physical noise. While already the seminal work of Chari et al. (in: CRYPTO, pp 398–412, 1999 ) study security of side-channel countermeasures in the noisy model, only recently Prouff and Rivain (in: Johansson T, Nguyen PQ (eds) EUROCRYPT, volume 7881 of lecture notes in 931 computer science, pp 142–159, Springer, 2013 ) offer a full formal analysis of the masking countermeasure in a physically motivated noise model. In particular, the authors show that a block-cipher implementation that uses the Boolean masking scheme is secure against a very general class of noisy leakage functions. While this is an important step toward better understanding the security of masking schemes, the analysis of Prouff and Rivain has several shortcomings including in particular requiring leak-free gates. In this work, we provide an alternative security proof in the same noise model that overcomes these challenges. We achieve this goal by a new reduction from noisy leakage to the important model of probing adversaries (Ishai et al. in: CRYPTO, pp 463–481, 2003 ). This reduction is the main technical contribution of our work that significantly simplifies the formal security analysis of masking schemes against realistic side-channel leakages.

2008

EPRINT

Leakage-Resilient Cryptography in the Standard Model
Abstract

We construct a stream-cipher $\SC$ whose \emph{implementation} is
secure even if arbitrary (adversely chosen) information on the
internal state of $\SC$ is leaked during computation. This captures
\emph{all} possible side-channel attacks on $\SC$ where the amount
of information leaked in a given period is bounded, but overall can
be arbitrary large, in particular much larger than the internal
state of $\SC$. The only other assumption we make on the
\emph{implementation} of $\SC$ is that only data that is accessed
during computation leaks information.
The construction can be based on any pseudorandom generator, and the
only computational assumption we make is that this PRG is secure
against non-uniform adversaries in the classical
sense (i.e. when there are no side-channels).
The stream-cipher $\SC$ generates its output in chunks
$K_1,K_2,\ldots$, and arbitrary but bounded information leakage is
modeled by allowing the adversary to adaptively chose a function
$f_\ell:\bin^*\rightarrow\bin^\lambda$ before $K_\ell$ is computed,
she then gets $f_\ell(\tau_\ell)$ where $\tau_\ell$ is the internal
state of $\SC$ that is accessed during the computation of
$K_\ell$.
One notion of security we prove for $\SC$ is that $K_\ell$
is indistinguishable from random when given $K_1,\ldots,K_{\ell-1}$,
$f_1(\tau_1),\ldots, f_{\ell-1}(\tau_{\ell-1})$ and also the complete
internal state of $\SC$ after $K_{\ell}$ has been computed
(i.e. our cipher is forward-secure).
The construction is based on alternating extraction (previously
used in the intrusion-resilient secret-sharing scheme from
FOCS'07). We move this concept to the computational setting by
proving a lemma that states that the output of any PRG has high HILL
pseudoentropy (i.e. is indistinguishable from some distribution with
high min-entropy) even if arbitrary information about the seed is
leaked. The amount of leakage $\leak$ that we can tolerate in each
step depends on the strength of the underlying PRG, it is at least
logarithmic, but can be as large as a constant fraction of the
internal state of $\SC$ if the PRG is exponentially hard.

2007

EPRINT

Intrusion-Resilient Secret Sharing
Abstract

We introduce a new primitive called Intrusion-Resilient Secret Sharing
(IRSS), whose security proof exploits the fact that there exist
functions which can be efficiently computed interactively using low
communication complexity in k, but not in k - 1 rounds.
IRSS is a means of sharing a secret message amongst a set of players
which comes with a very strong security guarantee. The shares in an
IRSS are made artificially large so that it is hard to retrieve them
completely, and the reconstruction procedure is interactive requiring
the players to exchange k short messages. The adversaries considered
can attack the scheme in rounds, where in each round the adversary
chooses some player to corrupt and some function, and retrieves the
output of that function applied to the share of the corrupted
player. This model captures for example computers connected to a
network which can occasionally be infected by malicious software like
viruses, which can compute any function on the infected machine, but
cannot sent out a huge amount of data.
Using methods from the Bounded-Retrieval Model, we construct an IRSS
scheme which is secure against any computationally unbounded adversary
as long as the total amount of information retrieved by the adversary
is somewhat less than the length of the shares, and the adversary
makes at most k - 1 corruption rounds (as described above, where k
rounds are necessary for reconstruction). We extend our basic scheme
in several ways in order to allow the shares sent by the dealer to be
short (the players then blow them up locally) and to handle even
stronger adversaries who can learn some of the shares completely.
As mentioned, there is an obvious connection between IRSS schemes and
the fact that there exist functions with an exponential gap in their
communication complexity for k and k - 1 rounds. Our scheme implies
such a separation which is in several aspects stronger than the
previously known ones.

2005

EPRINT

Intrusion-Resilience via the Bounded-Storage Model
Abstract

We introduce a new method of achieving intrusion-resilience in the cryptographic protocols. More precisely we show how to preserve security of such protocols, even if a malicious program (e.g. a virus) was installed on a computer of an honest user (and it was later removed). The security of our protocols relies on the assumption that the amount of data that the adversary can transfer from the infected machine is limited (however, we allow the adversary to perform any efficient computation on user's private data, before deciding on what to transfer). We focus on two cryptographic tasks, namely: authenticated key exchange and entity authentication. Our method is based on the results from the Bounded-Storage Model.

2001

EPRINT

On adaptive vs. non-adaptive security of multiparty protocols
Abstract

Security analysis of multiparty cryptographic protocols distinguishes
between two types of adversarial settings: In the non-adaptive
setting, the set of corrupted parties is chosen in advance, before the
interaction begins. In the adaptive setting, the adversary chooses
who to corrupt during the course of the computation. We study the
relations between adaptive security (i.e., security in the adaptive
setting) and non-adaptive security, according to two definitions and
in several models of computation. While affirming some prevailing
beliefs, we also obtain some unexpected results. Some highlights of
our results are:
o According to the definition of Dodis-Micali-Rogaway (which is set in
the information-theoretic model), adaptive and non-adaptive security
are equivalent. This holds for both honest-but-curious and Byzantine
adversaries, and for any number of parties.
o According to the definition of Canetti, for honest-but-curious
adversaries, adaptive security is equivalent to non-adaptive
security when the number of parties is logarithmic, and is strictly
stronger than non-adaptive security when the number of parties is
super-logarithmic. For Byzantine adversaries, adaptive security is
strictly stronger than non-adaptive security, for any number of
parties.

2000

EPRINT

On the Complexity of Verifiable Secret Sharing and Multi-Party Computation
Abstract

We first study the problem of doing Verifiable Secret Sharing (VSS)
information theoretically secure for a general access structure. We
do it in the model where private channels between players and a
broadcast channel is given, and where an active, adaptive adversary
can corrupt any set of players not in the access structure. In
particular, we consider the complexity of protocols for this
problem, as a function of the access structure and the number of
players. For all access structures where VSS is possible at all, we
show that, up to a polynomial time black-box reduction, the
complexity of adaptively secure VSS is the same as that of ordinary
secret sharing (SS), where security is only required against a
passive, static adversary. Previously, such a connection was only
known for linear secret sharing and VSS schemes.
We then show an impossibility result indicating that a similar
equivalence does not hold for Multiparty Computation (MPC): we show
that even if protocols are given black-box access for free to an
idealized secret sharing scheme secure for the access structure in
question, it is not possible to handle all relevant access
structures efficiently, not even if the adversary is passive and
static. In other words, general MPC can only be black-box reduced
efficiently to secret sharing if extra properties of the secret
sharing scheme used (such as linearity) are assumed.

#### Program Committees

- TCC 2020
- Eurocrypt 2019
- TCC 2018
- TCC 2018
- Eurocrypt 2017
- TCC 2017
- Crypto 2013
- PKC 2013
- PKC 2011
- TCC 2009
- Asiacrypt 2009
- Asiacrypt 2008
- Eurocrypt 2007
- TCC 2006
- Asiacrypt 2003

#### Coauthors

- Divesh Aggarwal (1)
- Marcin Andrychowicz (2)
- Joshua Brody (1)
- Ran Canetti (3)
- Suvradip Chakraborty (1)
- Ronald Cramer (2)
- Ivan Damgård (5)
- Alexandre Duc (3)
- Konrad Durnoga (1)
- Lisa Eckey (1)
- Sebastian Faust (13)
- Gottfried Herold (1)
- Julia Hesse (1)
- Martin Hirt (1)
- Kristina Hostáková (1)
- Yuval Ishai (3)
- Anthony Journault (1)
- Tomasz Kazana (5)
- Vladimir Kolmogorov (1)
- Tal Malkin (3)
- Daniel Masny (1)
- Ueli Maurer (2)
- Jesper Buus Nielsen (1)
- Maciej Obremski (2)
- Krzysztof Pietrzak (4)
- Tal Rabin (1)
- Maciej Skórski (2)
- François-Xavier Standaert (1)
- Daniel Wichs (2)
- Michal Zajac (1)
- Karol Zebrowski (1)