## CryptoDB

### Krzysztof Pietrzak

#### Affiliation: IST Austria

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Adaptively Secure Proxy Re-encryption
Abstract

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
📺
Abstract

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

2016

EUROCRYPT

2016

TOSC

The Exact Security of PMAC
Abstract

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

ASIACRYPT

2013

CRYPTO

2009

EUROCRYPT

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.

2008

EPRINT

The CCA2-Security of Hybrid Damgård's ElGamal
Abstract

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
Abstract

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 1991s Damgaards ElGamal public-key encryption
scheme under the DDH assumption.

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.

2006

EPRINT

Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist
Abstract

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?
Abstract

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
Abstract

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.

#### 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

#### Coauthors

- Hamza Abusalah (3)
- Joël Alwen (7)
- Abhishek Banerjee (2)
- Boaz Barak (1)
- Mihir Bellare (1)
- Jeremiah Blocki (2)
- Joshua Brody (1)
- David Cash (2)
- Binyi Chen (2)
- Bram Cohen (2)
- Yevgeniy Dodis (8)
- Stefan Dziembowski (4)
- Sebastian Faust (4)
- Marc Fischlin (1)
- Georg Fuchsbauer (9)
- Peter Gaži (8)
- Alexander Golovnev (1)
- Johan Håstad (1)
- Felix Heuer (2)
- Stefan Heyse (1)
- Zahra Jafargholi (2)
- Abhishek Jain (5)
- Dimitar Jetchev (1)
- Chethan Kamath (4)
- Danylo Khilko (1)
- Eike Kiltz (15)
- Karen Klein (3)
- Vladimir Kolmogorov (2)
- Ilan Komargodski (1)
- Momchil Konstantinov (2)
- Hugo Krawczyk (1)
- Stephan Krenn (3)
- Albert Kwon (1)
- Anja Lehmann (1)
- Vadim Lyubashevsky (1)
- Daniel Masny (2)
- Ueli Maurer (6)
- Tatsuaki Okamoto (2)
- Roberto Oliveira (1)
- Yvonne Anne Oswald (2)
- Christof Paar (1)
- Sunoo Park (1)
- Rafael Pass (1)
- Chris Peikert (2)
- Olivier Pereira (1)
- Bartosz Przydatek (1)
- Prashant Puniya (1)
- Vanishree Rao (2)
- Renato Renner (2)
- Leonid Reyzin (2)
- Phillip Rogaway (1)
- Alon Rosen (1)
- Guy N. Rothblum (1)
- Michal Rybár (3)
- Joachim Schipper (1)
- Gil Segev (1)
- Johan Sjödin (3)
- Maciej Skórski (3)
- Martijn Stam (3)
- François-Xavier Standaert (1)
- Sophie Stevens (2)
- Mario Szegedy (1)
- Aris Tentes (2)
- Stefano Tessaro (6)
- Daniele Venturi (2)
- Akshay Wadia (1)
- Michael Walter (1)
- Brent Waters (2)
- Daniel Wichs (6)
- Douglas Wikström (2)
- Yu Yu (1)
- Moti Yung (3)