International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Stefan Dziembowski

Publications

Year
Venue
Title
2021
TCC
Trojan-Resilience without Cryptography 📺
Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as ``time bombs'') or on some particular input (known as ``cheat codes''). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC), have been proposed. On a high level, to realize a circuit with specification $\cF$ one has more sophisticated circuits $\cF^\diamond$ manufactured (where $\cF^\diamond$ specifies a MPC or VC of $\cF$), and then embeds these $\cF^\diamond$'s into a \emph{master circuit} which must be trusted but is relatively simple compared to $\cF$. Those solutions have a significant overhead as $\cF^\diamond$ is significantly more complex than $\cF$ and also the master circuits are not exactly trivial either. In this work, we show that in restricted settings, where $\cF$ has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e., $\cF=\cF^\diamond$). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they're all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to $T$ inputs, the master circuit will catch Trojans that try to deviate on significantly more than a $1/T$ fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where $12$ instantiations of $\cF$ need to be embedded into the master. We also discuss an extremely simple construction with just $2$ instantiations for which we conjecture that it already achieves the optimal bound.
2020
CRYPTO
Reverse Firewalls for Actively Secure MPCs 📺
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 📺
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
Stefan Dziembowski Sebastian Faust Karol Żebrowski
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
Alexandre Duc Stefan Dziembowski Sebastian Faust
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
TCC
2015
EUROCRYPT
2015
CRYPTO
2015
CRYPTO
2014
EUROCRYPT
2013
CRYPTO
2012
TCC
2011
TCC
2011
CRYPTO
2011
ASIACRYPT
2006
CRYPTO
On Forward-Secure Storage
Stefan Dziembowski
2006
TCC
2004
EUROCRYPT
2004
JOFC
2004
JOFC
2001
EUROCRYPT
1999
EUROCRYPT

Program Committees

TCC 2020
Eurocrypt 2019
TCC 2018 (Program chair)
TCC 2018
Eurocrypt 2017
TCC 2017
Crypto 2013
PKC 2013
PKC 2011
TCC 2009
Asiacrypt 2009
Asiacrypt 2008
Eurocrypt 2007
TCC 2006
Asiacrypt 2003