Vector oblivious linear evaluation, or VOLE, has recently been shown to be a useful tool for designing efficient zero-knowledge proof systems that can scale to large statements with a low memory footprint (Yang et al. CCS 2021, Baum et al. CRYPTO 2021). While most ZK protocols require statements to be expressed in terms of arithmetic operations over a single finite field, recent works in VOLE-based ZK have shown how to mix Boolean and arithmetic operations in a single statement, through conversions between different finite fields (Baum et al. CCS 2021, Weng et al. USENIX 2021).

We present new, lightweight protocols for arithmetic/Boolean conversions in VOLE-based ZK. In contrast to previous works, which rely on an expensive cut-and-choose method, we take a new approach that leverages the ability of recent proof systems to prove high-degree polynomial constraints, and combines this with specialized low-degree pseudorandom generators. This not only simplifies conversions, but we showcase how it also improves the concrete efficiency of tasks important in practical ZK protocols of complex statements, including fixed point arithmetic, comparison and range proofs.

Joint work with Amit Agarwal (currently visiting IRIF), Carsten Baum, and Peter Scholl. To be presented at Eurocrypt 2025.

We are witnessing the increased availability of powerful quantum computing facilities as a service; also, there are promising prospects of applying quantum computing in fields such as material- and drug discovery, as well as scheduling, and optimisation. With these prospects comes an inherent challenge of quality assurance of complex quantum programs. Quantum programs and programming frameworks are becoming more complex, and this complexity creates a gap, calling for novel and rigorous testing and debugging frameworks. In this talk, we present an overview of the fascinating emerging field of software engineering and its numerous challenges and opportunities.

In particular, we review our recent research on characterising faults in hybrid quantum-classical architectures. This has led to a taxonomy of real faults in hybrid quantum-classical architectures. We also present our long-standing effort to establish a mature property-based testing framework for quantum programs both for fault-tolerant and for noisy architecture. We also present an automated debugging framework based on property-based testing.

In this talk, I will give a glimpse of an ongoing project on the development of quantum algorithms through the composition of graphs. At a high level, the idea is to represent a quantum query algorithm as a graph. The graph composition framework, that this work introduces, then provides a black-box way to turn such graphs into quantum algorithms. It turns out that this framework is able to unify many existing frameworks that generate quantum query algorithms, and it provides tangible ways to make these implementations time-efficient too. If time permits, we will also take a look at several examples for which this framework can be used.

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\mathrm{poly}(n)2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of $\Omega(2^{n/2})$ has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

In the past decade and largely in response to the NIST standardization effort for post-quantum cryptography, many new designs for digital signatures have been proposed. Among those, the FAEST digital signature scheme (Baum et al., CRYPTO 2023) stands out due to its interesting security-performance trade-off. It only relies on well-tested symmetric-key cryptographic primitives, as it constructs a digital signature from a Zero-Knowledge (ZK) proof of knowledge of an AES key. To achieve this, it uses the VOLE-in-the-head ZK proof system. FAEST simultaneously has relatively small signature size and competitive sign and verify times.

In this talk, I will describe how VOLE-in-the-head and FAEST works. Additionally, I will present recent improvements to both the security and practical efficiency of FAEST by revisiting the evaluation of the AES block cipher in ZK.

This talk is based on (recent) joint work with Ward Beullens, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Christian Majenz, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, and Peter Scholl.

In this talk we characterize extreme points of the set of incentive-compatible mechanisms for screening problems with linear utility. Extreme points are exhaustive mechanisms, meaning their menus cannot be scaled and translated to make additional feasibility constraints binding. In problems with one-dimensional types, extreme points admit a tractable description with a tight upper bound on their menu size. In problems with multi-dimensional types, every exhaustive mechanism can be transformed into an extreme point by applying an arbitrarily small perturbation. For mechanisms with a finite menu, this perturbation displaces the menu items into general position. Generic exhaustive mechanisms are extreme points with an uncountable menu. Similar results hold in applications to delegation, veto bargaining, and monopoly problems, where we consider mechanisms that are unique maximizers for specific classes of objective functionals. The proofs involve a novel connection between menus of extreme points and indecomposable convex bodies, first studied by Gale (1954).

Anamorphic Encryption, introduced by Persiano, Phan and Yung at Eurocrypt 2022, allows to establish secure communication in scenarios where users might be forced to hand over their decryption keys to some hostile authority. The challenge here is to be able to establish a secret communication channel to exchange covert (i.e. anamorphic) messages on top of some already deployed public key encryption scheme. Over the last few years, several works have improved our understanding of the primitive by proposing new constructions and refined security notions. However, most of these constructions are either ad hoc, in the sense that they obtain anamorphism exploiting specific properties of the underlying PKE, or impose severe restrictions on the size of the underlying anamorphic message space.

In this talk, I will present three works that aim to explore the inherent limitations of the primitive from a generic point of view. Namely, the question that I will answer is “What is the best that we can obtain from a PKE without making any assumption besides its security?”.

We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance $ε$. In many cases the bounds given by our general theorems are optimal, giving a time complexity of $O(1/Δ)$ with $Δ$ the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the amount of problem-specific insight necessary. As two applications of our framework we obtain optimal scaling for the Grover problem (i.e. $O(N^{1/2})$ where $N$ is the database size) and the Quantum Linear System Problem (i.e. $O(κ \log(1/ε))$ where $κ$ is the condition number and $ε$ the error tolerance) by direct applications of our theorems.

Joint work with Joseph Cunningham.

Oblivious Transfer (OT) is at the heart of secure computation and is a foundation for many applications in cryptography. Over two decades of work have led to extremely efficient protocols for evaluating OT instances in the preprocessing model, through a paradigm called OT extension. A few OT instances generated in an offline phase can be used to perform many OTs in an online phase efficiently, i.e., with very low communication and computational overheads.

In this talk, I will present a novel framework for OT extension with a public-key setup and concretely efficient instantiations. An implementation of our framework is 30-100 times faster when compared to the previous state-of-the-art public-key OT protocols, and remains competitive even when compared to OT protocols that *do not* offer a public-key setup. Additionally, our instantiations result in the first public-key schemes with plausible post-quantum security.