Master's Theses

Proof systems are a fundamental tool in modern cryptography, enabling a prover to convince a verifier of the validity of a statement while providing guarantees such as soundness, succinctness, and, in some settings, zero-knowledge. Over the past decades, proof systems have evolved from primarily theoretical constructions into practical cryptographic primitives with applications in authentication, verifiable computation, digital signatures, blockchain protocols, and digital identity systems.

Designing and deploying practical proof systems, however, involves significant challenges. A central issue is the tension between efficiency and security. While highly secure constructions are known, they are often too inefficient for practical use. Consequently, most deployed proof systems rely on the Fiat-Shamir heuristic, which transforms interactive protocols into non-interactive ones by modeling a cryptographic hash function as a random oracle. Recently, Khovratovich, Rothblum, and Soukhanov [1] presented the first attack targeting the Fiat-Shamir transform itself for a broad class of protocols, although its impact in practice is, for now, very limited.

The goal of this project is to study this attack on Fiat-Shamir, implement it, and explore extensions and variations of the attacks. For this, the student will have to acquire familiarity with proof systems and the GKR protocol, as well as with the Fiat-Shamir transform itself. Then, the student will explore libraries that implement GKR in real-world applications, such as [2], and attempt to replicate the attacks in such libraries. If time allows, the student will research possible extensions to the attacks, both at a practical and at a foundational level.

This is a project with a strong pure-research component. While advanced mathematical knowledge is not required, the student should be comfortable working with basic algebra, polynomials, and finite fields. Good implementation skills are helpful but not expected to be the main bottleneck.

[1] Dmitry Khovratovich, Ron D. Rothblum and Lev Soukhanov. How to Prove False Statements: Practical Attacks on Fiat-Shamir. CRYPTO 2025. external page https://eprint.iacr.org/2025/118

[2] external page https://github.com/PolyhedraZK/Expander

Usually, the communication complexity of a protocol is expressed with two parameters: The round complexity denotes the number of communication rounds needed, and the bit complexity denotes the number of bits communicated through a protocol execution.

Whereas the round complexity seems to have a direct impact on the execution time of a protocol, this is not generally true for the bit complexity. As an example, consider two protocols A and B, both among n parties, both consisting of n rounds. In protocol A, in the very first round, every party needs to send some big message, and in every subsequent round, every party needs to send just one single bit. Incontrast, in protocol B, in the i-th round, party P_i has to send some big message, and every other party needs to send just one bit. Arguably, in many realistic network settings, protocol A will perform better, because the big messages can be communicated in parallel, whereas in protocol B, the big messages need to be sent sequentially. 

In a previous Master's project, we have put forward a new dimension to express the communication complexity, namely the length of a protocol (external page https://ia.cr/2025/931). In a nutshell, the length of a protocol denotes the number of bits that needs to be sent in a non-parallelizable way. However, this notion is only suited for synchronous protocols. 

In this project, we aim at generalizing the length-notion to the asynchronous setting, and improve some existing asynchronous protocols with respect to the new notion. 

As prerequisite, students must have attended the course Cryptographic Protocols (or an equivalent course).

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Yuanming Song)

This project investigates how modern compression algorithms can leak sensitive information through compression side channels, where changes in compressed output size reveal properties of the underlying data even when it is encrypted. While previous attacks have mainly targeted the older DEFLATE algorithm, this work focuses on newer and increasingly popular schemes such as brotli and Zstandard, and potentially others like LZ4, Snappy, LZMA, and bzip2. A key goal is to understand how vulnerable these algorithms are to side-channel attacks and how an attacker might amplify small differences in input into large, observable changes in compressed length.

The project will adapt known exploitation techniques from DEFLATE, such as telescoping and chaining, to brotli and Zstandard, studying how well they transfer and why they may behave differently. It will also develop new, algorithm-specific techniques that exploit unique design features, complex encoding schemes (such as FSE in Zstandard), static dictionaries, and heuristic optimizations in reference implementations. Because many compression algorithms lack formal specifications, the work will rely heavily on analyzing their source code, implementing attack strategies, and empirically evaluating their effectiveness in realistic scenarios.

(Supervisor: Prof. Kenny Paterson, Joint Supervisors: Gabriel Dettling, Dr. Martin Hirt, Dr. Chen-Da Liu-Zhang)

This project studies how to design highly scalable “MPC as a service” protocols that can run continuously with a changing set of participants, as in modern systems like blockchain platforms or TOR. In these dynamic settings, parties should be able to join, contribute to the computation briefly, and leave, without a fixed group of long-term participants. Existing dynamic multi-party computation (MPC) protocols in the “only-speak-once” model, where each committee participates in just one step, incur communication costs proportional to both the number of parties and the circuit size (Ω(nC)), while traditional static MPC can achieve communication proportional only to the circuit size (O(C)). The central goal of this thesis is to investigate whether similar low, constant communication per gate is achievable in the dynamic MPC model.

The work will begin by surveying the state of the art in both standard MPC protocols with constant per-gate communication and dynamic MPC protocols, focusing on their communication complexity. Building on this understanding, the project will explore how to adapt techniques such as packed secret sharing to the dynamic setting. The plan is to first design feasibility protocols with weaker guarantees (passive security, SIMD circuits, and sub-optimal resilience, using lightweight cryptographic tools and no trusted setup), and then progressively strengthen them to handle general circuits, optimal resilience, and fully malicious adversaries.

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Dr. Rune Fiedler)

This project examines the security of the SimpleX messaging system, which markets itself as “the world’s most secure messaging” and claims stronger privacy guarantees than well-known messengers like Signal, especially regarding metadata, profiles, and contacts. Despite a recent external review by Trail of Bits that reported no major issues, SimpleX’s ambitious claims and distinctive design (including stronger metadata-hiding goals) warrant a deeper, independent analysis.

The main task is to reverse-engineer and understand the internal protocols and system architecture of SimpleX, then abstract these into clear models suitable for security analysis. Using these abstractions, one can search for weaknesses (for example in how metadata is hidden or how components interact) and/or attempt to construct formal security proofs. Any vulnerabilities found will be documented and disclosed responsibly to the developers. The thesis will focus on explaining how SimpleX’s systems work, presenting the identified security properties and potential issues (or formal guarantees, if proven), and discussing the scope and limits of the security analysis rather than narrating the full step-by-step investigative process.

(Supervisor: Prof. Kenny Paterson, Joint Supervisor: Dr. Lenka Mareková)

This project contributes to the group's ongoing work on developing a secure smartphone-based communication tool for humanitarian workers that works even in areas with no internet, cellular, or satellite connectivity. Building on an existing prototype that already supports routing, delay-tolerant networking, and basic performance measurement, the next phase focuses on integrating cryptographic security from the link layer up to the application layer. At the same time, the networking stack must be improved to run reliably in the background and to meet new requirements imposed by the cryptographic protocols, while performance overheads and bottlenecks are systematically evaluated.

The system must function in diverse and sometimes restrictive field environments, leading to unusual security requirements. The project’s goals are to improve usability (e.g., background operation), contribute to the design and implementation of the application-layer protocols, and extend experimental evaluation of performance and security, with insights from implementation feeding back into the overall protocol design.