home
people
research
student projects
contacts
laboratory
for computation
security
We work on the theoretical foundations and practical realizations of cryptographic proofs. This enables checking the correctness of a computation in zero knowledge, and much faster than re-running the computation. These cryptographic proofs have powerful applications in the real world.
Probabilistic proof systems play an important role in theoretical computer science, enabling beautiful applications to delegation of computation, zero knowledge, and hardness of approximation. Interactive proofs (IPs), multi-prover interactive proofs (MIPs), probabilistically checkable proofs (PCPs), and interactive oracle proofs (IOPs) are types of probabilistic proof systems. We study the capabilities and limitations of probabilistic proof systems.
Cryptographic proofs are protocols used to prove and to verify the correct execution of computations. By combining the powers of probabilistic proofs and cryptography, it is possible to achieve "paradoxical" properties such as zero knowledge (the cryptographic proof reveals no information beyond the correctness of the proved computation) and succinctness (the cryptographic proof can be checked exponentially faster than running the proved computation). This leads, e.g., to powerful notions such as zkSNARKs, which have found widespread deployment in practice. We study efficient constructions of zkSNARKs and more.
Proof-carrying data (PCD) is a cryptographic primitives that allows mutually distrustful parties to perform efficiently verifiable distributed computation. PCD has found applications in blockchains, image authentication, enforcing language semantics, and more. We study the theoretical foundations, efficient constructions, and applications of PCD and other related primitives.
Quantum computing impacts cryptography, making numerous cryptographic tools insecure. We investigate how quantum computing affects the construction and security of cryptographic proofs and related primitives, with the ultimate goal of providing post-quantum secure zkSNARKs that are as efficient as possible.
The above topics span complexity theory, cryptography, coding theory, and some systems security. Understanding these topics benefits from a solid background in discrete probability, abstract algebra, and properties of polynomials. Below is a list of useful courses at EPFL that helps assemble relevant background material.
The COMPSEC lab offers the following project opportunities for BSc, MSc, and PhD students. If you are interested in one or more of the following projects, please fill out this application form. You will need to specify which project(s) you are interested in, why you are interested, and if you have any relevant experience in this area. We process applications in batches (early batch deadline: July 6, 2024). We strongly recommend that you apply as soon as possible for best consideration, since we expect most projects would be taken after the first round.
Many constructions for post-quantum-secure probabilistic (zero-knowledge) proofs (ZKPs) rely on hardness assumptions based on lattice problems (notably, variants of the Short Integer Solution). However, setting the parameters for the underlying lattice problem in order to achieve a desired level of security is non-trivial, and really only accessible today to a handful of experts [APS15]. As part of our effort to port lattice-based ZKPs from research to practice, you will design and implement a Rust library for lattice parameter selection. Concretely, this library should: (i) provide an intuitive and hard-to-misuse interface for proof frontends, (ii) internally use precise estimates for the hardness for lattice problems (e.g., by reducing to the shortest vector problem), and (iii) compute estimates for variants of standard problems of interest (e.g., new lattice assumptions, or standard assumptions with additional leakage). This library would be designed to be integrated into lattirust, our library for lattice-based proofs.
This project is aimed at one B.Sc. or M.Sc. student, who will be working with Christian Knabenhans.
Polynomial commitment schemes (PCSs) are a core building block for modern succinct non-interactive arguments of knowledge (SNARKs). The past few years have seen a Cambrian explosion of new PCS constructions based on various lattice assumptions, with different trade-offs and efficiency profiles. The goal of this project is to parametrize, implement and benchmark 1-3 recent lattice PCS constructions using lattirust, our library for lattice-based proofs.
This project is aimed at one B.Sc. or M.Sc. student, who will be working with Christian Knabenhans.
STIR (Shift-To-Improve-Rate) [ACFY24] is an exciting new protocol for low-degree testing, a core component of the most efficient and widely deployed SNARKs to date. In this project, you will be writing a production grade implementation of STIR, and implementing it into the arkworks Rust ecosystem.
This project is aimed at one B.Sc. or M.Sc. student, who will be working with Giacomo Fenzi.
[ACFY24] Arnon, Chiesa, Fenzi, Yogev. STIR: Reed-Solomon Proximity Testing with Fewer Queries
The arkworks Rust ecosystem for developing zkSNARKs has been an invaluable tool for understanding the concrete efficiency of protocols. One of the roles that arkworks fills is that of enabling prototyping, and to enable filling this niche we would like the library to maximize two metrics (i) usability and (ii) efficiency. The Rust programming language notably achieves good results on the (ii), while for (i) it tends to have a lot of boilerplate, which hinders fast iteration. Recently, a few new languages came out which aim to combine the performance of Rust-like languages with the usability of Python (thanks to JIT compilation). One such language is Mojo, which also promises to have good interoperability with GPUs. In this project, you would explore rewriting some core functionality of arkworks in Mojo (such as field operations, Merkle trees and more) and compare the performance and programming experience with their Rust equivalent, to evaluate whether the switch is worthwhile.
This semester project is aimed at one B.Sc. or M.Sc. student, who will be working with Giacomo Fenzi.
A well-known technique to convert an interactive proof to a non-interactive proof is the Fiat-Shamir transformation, which guarantees security in the random oracle model. An alternative transformation to achieve non-interactivity is the Fischlin transform [Fis05], which presents a number of advantages of the Fiat-Shamir transform (in particular, a straight-line, i.e. non-rewinding extractor) [DV24, ABGR12]. The concrete runtime and implementation costs of the Fischlin transform are however still not well-understood, although there has been some very recent progress in this direction. The goal of this project is to (i) derive guidelines to securely instantiate the Fischlin transform for real-world use cases, (ii) implement and optimize the Fischlin transform on top of the arkworks library, and (iii) compare this concrete instantiations with Fiat-Shamir implementations in terms of concrete efficiency, parameter sets, and theoretical security guarantees.
This semester project is aimed at one B.Sc. or M.Sc. student, who will be working with Christian Knabenhans.
[Fis05] M. Fischlin, “Communication-Efficient Non-interactive Proofs of Knowledge with Online Extractors”, CRYPTO 2005
[DV14] Ö. Dagdelen and D. Venturi, “A Second Look at Fischlin's Transformation”, AFRICACRYPT 2014
[ABGC12] P. Ananth, R. Bhaskar, V. Goyal, and V. Rao, “On the (In)security of Fischlin's Paradigm”, Theory of Cryptography 2012
[CL24] Y.-H. Chen and Y. Lindell, “Optimizing and Implementing Fischlin's Transform for UC-Secure Zero-Knowledge”, ePrint 2024.
The Arithmetized Random Oracle Model (AROM) is an exciting new paradigm to construct Proof-Carrying-Data (PCD) that is secure for arbitrary depth computation. Investigating the concrete efficiency of these constructions entails implementing the arithmetized random oracle in question (obtained from a hash function such as SHA3 or Blake3). In this project, you will heuristically instantiate the AROM using one of these functions, and aim to understand which hash functions yield the most efficient PCDs.
This semester project is aimed at one B.Sc. or M.Sc. student, who will be working with Giacomo Fenzi.
[CCGOS23] Chen et al. Proof-Carrying-Data from Arithmetized Random Oracles. EUROCRYPT 2023.
The Fiat-Shamir (FS) transformation is a fundamental building block to compile interactive proofs into non-interactive proofs. The FS transform is usually instantiated heuristically with the help of a standard hash function, it can also be instantiated using correlation-intractable hash functions (CI-HF), in which case it provides provable security under concrete hardness assumptions. The broader goal of this project is to better understand the suitability of instantiating FS using correlation-intractable hash functions, and could include (i) proving limitations on CI-HF [DM23], (ii) investigating the concrete efficiency of CI-HF compared to standard hash functions, or (iii) investigating CI-HF for recursive proof composition.
This semester project is aimed at one B.Sc. or M.Sc. student, who will be working with Christian Knabenhans and Yuxi Zheng.
[CCRR18] Canetti, Chen, Reyzin and Rothblum, Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption. CRYPTO 2018
[PS19] Peikert and Shiehian, Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors. CRYPTO 2019
[LV20] Lombardi & Vaikuntanathan, Correlation-Intractable Hash Functions via Shift-Hiding. ePrint 2020
[CCH+19] Canetti et al., Fiat-Shamir: from practice to theory. STOC 2019
[DM23] Döttling & Nour, On The Black-Box Complexity of Correlation Intractability. ePrint 2023
