Krzysztof Pietrzak
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Krzysztof Pietrzak has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Benedikt Auerbach
PQShield
4 shared publications - Christoph U. Günther
Institute of Science and Technology Austria
3 shared publications - Miguel Cueto Noval
ISTA
3 shared publications - Guillermo Pascual-Perez
ISTA
2 shared publications - Amirali Ebrahimzadeh
Computer Engineering, Sharif University of Technology, Tehran, Iran
1 shared publication Boran Erol
UCLA
1 shared publication
Latest Publications
- 5 December 2025
- Published by Springer Nature
- p. 171-202
Space-Deniable Proofs
- 17 August 2025
- Published by Springer Nature
- p. 141-172
Continuous Group-Key Agreement: Concurrent Updates Without Pruning
- 17 August 2025
- Published by Springer Nature
- p. 141-172
Continuous Group-Key Agreement: Concurrent Updates Without Pruning
- 2 December 2024
- Published by Springer Nature
- p. 413-443
The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging
- 2 December 2024
- Published by Springer Nature
- p. 413-443
The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging
- Open Access
- 1 October 2024
- Published by Privacy Enhancing Technologies Symposium Advisory Board in Proceedings on Privacy Enhancing Technologies
- Vol. 2024 (4) , 636-648
Deniability in Automated Contact Tracing: Impossibilities and Possibilities
Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts. Designing effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability. While some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result: A decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes. Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.
- 1 October 2024
- Published by Privacy Enhancing Technologies Symposium Advisory Board in Proceedings on Privacy Enhancing Technologies
- Vol. 2024 (4) , 636-648
Open AccessDeniability in Automated Contact Tracing: Impossibilities and Possibilities
Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts. Designing effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability. While some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result: A decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes. Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 268-278
Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains
We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems - like proofs of stake or proofs of space - and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (MDP). We then present a formal analysis procedure which computes an ϵ-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be any specified precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines. In concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 268-278
Open AccessFully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains
We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems - like proofs of stake or proofs of space - and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (MDP). We then present a formal analysis procedure which computes an ϵ-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be any specified precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines. In concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.
- 27 November 2023
- Published by Springer Nature
- p. 271-300
On the Cost of Post-compromise Security in Concurrent Continuous Group-Key Agreement
- 27 November 2023
- Published by Springer Nature
- p. 271-300
On the Cost of Post-compromise Security in Concurrent Continuous Group-Key Agreement
- 17 August 2007
- Published by Springer Nature
- p. 414-433
Improving the Security of MACs Via Randomized Message Preprocessing
- 17 August 2007
- Published by Springer Nature
- p. 414-433
Improving the Security of MACs Via Randomized Message Preprocessing