## CryptoDB

### Krzysztof Pietrzak

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

CoCoA: Concurrent Continuous Group Key Agreement
📺
Abstract

Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can \emph{efficiently} scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security.
In current proposals -- most notably in TreeKEM (which is part of the IETF's Messaging Layer Security (MLS) protocol draft) -- for users in a group of size $n$ to rotate their keys, they must each craft a message of size $\log(n)$ to be broadcast to the group using an (untrusted) delivery server.
In larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any $T \leq n$ users to simultaneously rotate their keys in just $2$ communication rounds have been suggested (e.g.\ ``Propose and Commit" by MLS). Unfortunately, $2$-round concurrent updates are either damaging or expensive (or both); i.e.\ they either result in future operations being more costly (e.g.\ via ``blanking'' or ``tainting'') or are costly themselves requiring $\Omega(T)$ communication for each user [Bienstock et al., TCC'20].
In this paper we propose CoCoA; a new scheme that allows for $T$ concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require $\Omega(\log^2(n))$ communication per user. To circumvent the [Bienstock et al.] lower bound, CoCoA increases the number of rounds needed to complete all updates from $2$ up to (at most) $\log(n)$; though typically fewer rounds are needed.
The key insight of our protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets $T$ concurrent update requests will approve one and reject the remaining $T-1$. In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most $\log(n)$ such update rounds.
To keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol.

2022

CRYPTO

Practical Statistically-Sound Proofs of Exponentiation in any Group
📺
Abstract

A proof of exponentiation (PoE) in a group G of unknown order allows a prover to convince a verifier that a tuple (x, q, T, y) ∈G × N × N × G satisfies x^q^T= y. This primitive has recently found exciting applications in the constructions of verifiable delay functions and succinct arguments of knowledge. The most practical PoEs only achieve soundness either under computational assumptions, i.e., they are arguments (Wesolowski, Journal of Cryptology 2020), or in groups that come with the promise of not having any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in general groups of unknown order is due to Block et al. (CRYPTO 2021), and can be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits of security, say λ = 80, the number of repetitions required (and thus the blow-up in communication) is as large as λ.
In this work we propose a statistically-sound PoE for the case where the exponent q is the product of all primes up to some bound B. We show that, in this case, it suffices to run only λ/ log(B) parallel instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to Block et al. by an order of magnitude. Furthermore, we show that in the known applications where PoEs are used as a building block such structured exponents are viable. Finally, we also discuss batching of our PoE, showing that many proofs (for the same G and q but different x and T) can be batched by adding only a single element to the proof per additional statement.

2021

CRYPTO

Limits on the Adaptive Security of Yao’s Garbling
📺
Abstract

Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting assuming secure symmetric-key encryption (and hence one-way functions). This was fol- lowed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafagholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth d, the loss in security is at most exponential in d. The above results all concern the simulation-based notion of security.
In this work, we show that the upper bound of Jafargholi and Wichs is more or less optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth d ∈ N, such that any black-box reduction proving the adaptive indistinguishability- security of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is sub-exponential in d. Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation.
To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security

2021

TCC

On Treewidth, Separators and Yao’s Garbling
📺
Abstract

We show that Yao’s garbling scheme is adaptively indistinguishable
for the class of Boolean circuits of size S and treewidth w
with only a S^{O(w)} loss in security. For instance, circuits with constant
treewidth are as a result adaptively indistinguishable with only a polynomial
loss. This (partially) complements a negative result of Applebaum
et al. (Crypto 2013), which showed (assuming one-way functions) that
Yao’s garbling scheme cannot be adaptively simulatable. As main technical
contributions, we introduce a new pebble game that abstracts out
our security reduction and then present a pebbling strategy for this game
where the number of pebbles used is roughly O(\delta w log(S)), \delta being the
fan-out of the circuit. The design of the strategy relies on separators, a
graph-theoretic notion with connections to circuit complexity.

2021

TCC

The Cost of Adaptivity in Security Games on Graphs
📺
Abstract

The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto'17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary.
Some of our lower bounds only apply to a restricted class of black-box reductions which we term "oblivious" (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions.
Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above mentioned primitives using oracle separation techniques.

2021

TCC

Grafting Key Trees: Efficient Key Management for Overlapping Groups
📺
Abstract

Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM.
A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds log(N) keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting 2log(N) ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial
one where we have a separate key tree for each group.
We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution.
As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group
structure into a “lattice graph”, which then is turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code.
To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.

2021

TCC

Trojan-Resilience without Cryptography
📺
Abstract

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.

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

2019

ASIACRYPT

New proof systems for sustainable blockchains: proofs of space and verifiable delay functions
★
Abstract

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.

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

ASIACRYPT

2013

CRYPTO

2009

EUROCRYPT

#### Program Committees

- TCC 2020 (Program chair)
- Eurocrypt 2019
- TCC 2018
- Eurocrypt 2017
- TCC 2017
- Crypto 2014
- TCC 2014
- TCC 2013
- CHES 2012
- PKC 2012
- Eurocrypt 2012
- TCC 2011
- Eurocrypt 2010
- Crypto 2009

#### Coauthors

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