CryptoDB

Stefan Dziembowski

Publications

Year
Venue
Title
2020
CRYPTO
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
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
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
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.
2017
TCC
2016
EUROCRYPT
2016
CRYPTO
2016
TCC
2015
EPRINT
2015
TCC
2015
EUROCRYPT
2015
CRYPTO
2015
CRYPTO
2014
EUROCRYPT
2014
EPRINT
2013
CRYPTO
2012
TCC
2011
TCC
2011
CRYPTO
2011
ASIACRYPT
2008
EPRINT
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
2006
CRYPTO
2006
TCC
2005
EPRINT
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.
2004
EUROCRYPT
2004
JOFC
2004
JOFC
2001
EUROCRYPT
2001
EPRINT
2000
EPRINT
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.
1999
EUROCRYPT

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