International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Krzysztof Pietrzak

Affiliation: IST Austria

Publications

Year
Venue
Title
2019
PKC
Adaptively Secure Proxy Re-encryption
A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key $$pk'$$ . This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under $$pk'$$ without having to know the underlying message, while transformations from $$pk'$$ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in , rendering the result meaningless already for moderate .Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).
2019
EUROCRYPT
Reversible Proofs of Sequential Work 📺
Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement $$\chi $$ and a time parameter T computes a proof $$\phi (\chi ,T)$$ which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since $$\chi $$ was received.PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].In this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.The fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at).
2019
ASIACRYPT
New proof systems for sustainable blockchains: proofs of space and verifiable delay functions
Krzysztof Pietrzak
The distinctive feature of Bitcoin is that it achieves decentralisation in an open setting where everyone can join. This is achieved at a high price, honest parties must constantly dedicate more computational power towards securing Bitcoin's blockchain than is available to a potential adversary, which leads to a massive waste of energy; at its hitherto peak, the electricity used for Bitcoin mining equaled the electricity consumption of Austria. In this lecture I will discuss how disk-space, instead of computation, can be used as a resource to construct a more sustainable blockchain. We will see definitions and constructions of "proof of space" and "verifiable delay functions", and how they can be used to construct a Blockchain with similar dynamics and security properties as the Bitcoin blockchain.
2018
EUROCRYPT
2018
EUROCRYPT
Simple Proofs of Sequential Work 📺
Bram Cohen Krzysztof Pietrzak
2017
EUROCRYPT
2017
EUROCRYPT
2017
CRYPTO
2017
ASIACRYPT
2017
TCC
2017
JOFC
2016
EUROCRYPT
2016
TCC
2016
TCC
2016
TOSC
The Exact Security of PMAC
Peter Gazi Krzysztof Pietrzak Michal Rybár
PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs a mask to every message block, where the mask for the ith block is computed as τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of γi’s which contains a large coset of a subgroup of GF(2n). We then investigate if the security of PMAC can be further improved by using τi’s that are k-wise independent, for k > 1 (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
CRYPTO
2015
CRYPTO
2015
CRYPTO
2015
ASIACRYPT
2015
ASIACRYPT
2014
CRYPTO
2014
EUROCRYPT
2014
PKC
2014
TCC
2014
EPRINT
2014
EPRINT
2014
JOFC
2014
ASIACRYPT
2013
TCC
2013
CRYPTO
2013
CRYPTO
2012
TCC
2012
TCC
2012
TCC
Subspace LWE
Krzysztof Pietrzak
2012
EUROCRYPT
2012
CHES
2012
ASIACRYPT
2012
FSE
2011
TCC
2011
CRYPTO
2011
EUROCRYPT
2010
TCC
2010
TCC
2010
ASIACRYPT
2010
CRYPTO
2009
EUROCRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2008
EUROCRYPT
2008
EPRINT
Leakage-Resilient Cryptography in the Standard Model
Stefan Dziembowski Krzysztof Pietrzak
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.
2008
EPRINT
The CCA2-Security of Hybrid Damgård's ElGamal
Eike Kiltz Krzysztof Pietrzak Martijn Stam Moti Yung
We consider a hybrid version of Damgård's ElGamal public-key encryption scheme that incorporates the use of a symmetric cipher and a hash function for key-derivation. We prove that under appropriate choice of the hash function this scheme is IND-CCA secure under the Decisional Diffie-Hellman assumption in the standard model. Our results can be generalized to universal hash proof systems where our main technical contribution can be viewed as an efficient generic transformation from 1-universal to 2-universal hash proof systems.
2008
EPRINT
A New Randomness Extraction Paradigm for Hybrid Encryption
Eike Kiltz Krzysztof Pietrzak Martijn Stam Moti Yung
We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as DDH, QR and Paillier. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991’s Damgaard’s ElGamal public-key encryption scheme under the DDH assumption.
2008
CRYPTO
2007
CRYPTO
2007
EUROCRYPT
2007
EUROCRYPT
2007
FSE
2007
TCC
2007
EPRINT
Intrusion-Resilient Secret Sharing
Stefan Dziembowski Krzysztof Pietrzak
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.
2006
EUROCRYPT
2006
EUROCRYPT
2006
TCC
2006
EPRINT
Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist
Krzysztof Pietrzak
A $(k,\ell)$-robust combiner for collision-resistant hash-functions is a construction which from $\ell$ hash-functions constructs a hash-function which is collision-resistant if at least $k$ of the components are collision-resistant. One trivially gets a $(k,\ell)$-robust combiner by concatenating the output of any $\ell-k+1$ of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box $(k,\ell)$-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06).
2006
EPRINT
Luby-Rackoff Ciphers from Weak Round Functions?
The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key. Luby and Rackoff showed that the three-round Feistel-network -- each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) -- is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers. But the round functions used in actual block-ciphers are -- for efficiency reasons -- far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (NCPA). We show that in the information-theoretic setting, four rounds with NCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a NCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation. We also consider other relaxations of the Luby-Rackoff construction and prove their (in)security against different classes of attacks.
2006
EPRINT
Indistinguishability Amplification
Ueli Maurer Krzysztof Pietrzak Renato Renner
A random system is the abstraction of the input-output behavior of any kind of discrete system, in particular cryptographic systems. Many aspects of cryptographic security analyses and proofs can be seen as the proof that a certain random system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the distinguishing advantage of a combined system, assuming upper bounds of various types on the component systems. For a general type of combination operation of systems (including the combination of functions or the cascade of permutations), we prove two amplification theorems. The first is a direct-product theorem, similar in spirit to the XOR-Lemma: The distinguishing advantage (or security) of the combination of two (possibly stateful) systems is twice the product of the individual distinguishing advantages, which is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of attacks. As a corollary we obtain tight bounds on the adaptive security of the cascade and parallel composition of non-adaptively (or only random-query) secure component systems. A key technical tool of the paper is to show a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of provoking an appropriately defined event on one of the systems.
2005
CRYPTO
2005
CRYPTO
2005
CRYPTO
2004
TCC
2003
EUROCRYPT

Program Committees

Eurocrypt 2019
TCC 2018
TCC 2017
Eurocrypt 2017
Crypto 2014
TCC 2014
TCC 2013
CHES 2012
PKC 2012
Eurocrypt 2012
TCC 2011
Eurocrypt 2010
Crypto 2009