Past Events

In classical auction design, we take it for granted that the auctioneer is trusted and always implements the auction's rules honestly. This assumption, however, no longer holds in modern auctions based on blockchains, or those mediated by third-party platforms such as Google. For example, in blockchain-based auctions, the consensus nodes that partly serve as the auctioneer are incentivized to deviate from honest behavior if profitable. Third-party auction platforms such as Google have also been involved in high-profile anti-trust lawsuits for manipulating their auctions.

In this talk, I will describe our recent work on decentralized mechanism design, where we aim to build a new scientific foundation for emerging auctions that are not backed by a trusted auctioneer. I will characterize the mathematical landscape of decentralized mechanism design, by showing several infeasibility and feasibility results. I will also highlight how cryptography can play an essential role for bypassing impossibility results in decentralized mechanism design, leading to a new class of auctions that not only incentivize bidders to act honestly, but also incentivize the auctioneer to play by the book.

We present the first unconditionally secure auxiliary-input quantum commitment scheme with statistical hiding. Our construction resolves an open question posed in [Qia24, MNY24] by proving security even when adversaries are equipped with additional classical advice; however, the scheme fails in the presence of quantum advice. Remarkably, this limitation not only poses a compelling open problem in cryptography but also yields an unconditional separation in quantum complexity theory. Specifically, our findings distinguish the quantum promise complexity classes \(\mathsf{p}/\mathsf{mBQP}/\mathsf{qpoly}\) and \(\mathsf{p}/\mathsf{mBQP}/\mathsf{poly}\)—quantum analogues of the classical \(\mathsf{BQP}/\mathsf{(q)poly}\) classes.

In this talk, I will show how to construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). The resulting schemes support an a-priori bounded number of homomorphic operations: \(o(\log \lambda)\) multiplications followed by \(\mathsf{poly}(\lambda)\) additions, where \(\lambda\) is a security parameter. This gives the first constructions of somewhat homomorphic encryption for the class of bounded-degree polynomials that do not rely on lattice assumptions or bilinear maps. Moreover, our schemes are conceptually simple: much as in Gentry, Sahai, and Waters’ fully homomorphic encryption scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication.

Joint work with Henry Corrigan-Gibbs, Yael Kalai, and Vinod Vaikuntanathan (to appear at EUROCRYPT 2025).

It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of \(t < n/2\) corruptions, bypassing the setup-free \(t < n/3\) barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience (\(n/2\) instead of \(n/3\)) for the price of increased assumptions. Is this trade-off necessary?

We further the study of crypto-agnostic Byzantine agreement among parties that answers this question in the negative. Specifically, let \(t_s\) and \(t_i\) denote two parameters such that (1) \(2t_i + t_s < n\), and (2) \(t_i \le t_s < n/2\). Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to \(t_s\) parties, or (2) the adversary is computationally unbounded and corrupts up to \(t_i\) parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only \(O(kn^2)\) bits for security parameter k over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of n and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for \(t_i \le n/4\).

Joint work with Yuval Efron and Jovan Komatovic (to appear at EUROCRYPT 2025).

Registered attribute-based encryption (ABE) is a generalization of public-key encryption that enables fine-grained access control to encrypted data (like standard ABE), but /without/ needing a central trusted authority. In a key-policy registered ABE scheme, users choose their own public and private keys and then register their public keys together with a decryption policy with an (untrusted) key curator. The key curator aggregates all of the individual public keys into a short master public key which serves as the public key for an ABE scheme.

Currently, we can build registered ABE for restricted policies (e.g., Boolean formulas) from pairing-based assumptions and for general policies using witness encryption or indistinguishability obfuscation. In this work, we construct a key-policy registered ABE for general policies (specifically, bounded-depth Boolean circuits) from the \(\ell\)-succinct learning with errors (LWE) assumption in the random oracle model. The ciphertext size in our registered ABE scheme is \(\mathsf{poly}(\lambda, d)\), where \(\lambda\) is a security parameter and \(d\) is the depth of the circuit that computes the policy circuit \(C\). Notably, this is independent of the length of the attribute \(\mathbf{x}\) and is optimal up to the \(\mathsf{poly}(d)\) factor.

Previously, the only lattice-based instantiation of registered ABE uses witness encryption, which relies on private-coin evasive LWE, a stronger assumption than \(\ell\)-succinct LWE. Moreover, the ciphertext size in previous registered ABE schemes that support general policies (i.e., from obfuscation or witness encryption) scales with \(\mathsf{poly}(\lambda, |\mathbf{x}|, |C|)\). The ciphertext size in our scheme depends only on the depth of the circuit (and not the length of the attribute or the size of the policy). This enables new applications to identity-based distributed broadcast encryption.

Our techniques are also useful for constructing /adaptively-secure/ (distributed) broadcast encryption, and we give the first scheme from the \(\ell\)-succinct LWE assumption in the random oracle model. Previously, the only lattice-based broadcast encryption scheme with adaptive security relied on witness encryption in the random oracle model. All other lattice-based broadcast encryption schemes only achieved selective security.

Joint work with Yao-Ching Hsieh and David Wu.

Rational Protocol Design (RPD), introduced by Garay, Katz, Maurer, Tackmann and Zikas [FOCS '13] leverages the well-established real/ideal paradigm to prove the security of cryptographic protocols against malicious attackers to incorporate participants' incentives to misbehave. In a nutshell, RPD casts a protocol attack as a two-party game between a rational protocol designer and a rational attacker. The attacker aims at breaking certain security properties, from which he obtains his utility, by choosing an appropriate adversarial strategy corresponding to a central adversary who gets to corrupt parties in a standard cryptographic manner; symmetrically, the goal of the designer is to come up with a protocol which (when executed by the parties who adhere to the protocol) maximizes its own utility. Importantly, RPD allows for the establishment of a partial order of protocols with respect to the property under consideration (e.g., fairness). In this talk, after a brief introduction of the RPD framework, we showcase it in a variety of applications, including secure multi-party computation in the presence of a dishonest majority, fair (reactive) 2-party computation, and the Bitcoin ledger, explaining why Bitcoin continues to work even though majority coalitions are in fact possible.

The problem of reliable/secure all-to-all communication over low-degree networks has been essential for communication-local (CL) \(n\)-party secure multi-party computation (MPC) (i.e., MPC protocols where every party directly communicates only with a few parties, typically poly-logarithmic in \(n\)) and more recently for communication over ad hoc networks, which are used in blockchain protocols. However, a limited number of adaptively secure solutions exist, and they all make relatively strong assumptions on the ability of parties to act in some specific manner before the adversary can corrupt them. Two such assumptions were made in the work of Chandran et al. [ITCS’15]— parties can (a) multi-send messages to several receivers simultaneously; and (b) securely erase the message and the identities of the receivers, before the adversary gets a chance to corrupt the sender (even if a receiver is corrupted).

A natural question to ask is: Are these assumptions necessary for adaptively secure CL-MPC? In this work we characterize the feasibility landscape for all-to-all reliable message transmission (RMT) under these two assumptions, and use this characterization to obtain (asymptotically) tight feasibility results for CL-MPC.

Joint work with Nishanth Chandran, Ankit Kumar Misra, Rafail Ostrovsky, and Vassilis Zikas.

Quantum computing introduces many well-motivated problems rooted in physics, asking to com- pute information from input quantum states. Identifying the computational hardness of these prob- lems yields potential applications with far-reaching impacts across both the realms of computer science and physics. However, these new problems do not neatly fit within the scope of exist- ing complexity theory. The standard classes primarily cater to problems with classical inputs and outputs, leaving a gap to characterize problems involving quantum states as inputs. Notably, the emergence of new quantum cryptographic primitives is reshaping our understanding of the minimal assumption in cryptography, which directly affects the relationships between cryptography and com- plexity theory; in particular, the connection between Minicrypt and Pessiland in Impagliazzo’s five worlds view is somewhat unclear — one reason for this is that breaking new quantum cryptographic primitives involves solving problems with quantum inputs, while the complexity classes central to Pessiland, Heuristica, and Algorithmica are grounded in problems with classical inputs and outputs.

In this talk, I will introduce the complexity theory for quantum promise problems and potential applications. Quantum promise problems are quantum-input decision problems asking to identify whether input quantum states (that can be pure and mixed states) satisfy specific properties. We will see structural results for complexity classes, \(\mathsf{p/mBQP}\), \(\mathsf{p/mQ(C)MA}\), \(\mathsf{p/mQSZKhv}\), \(\mathsf{p/mQIP}\), and \(\mathsf{p/mPSPACE}\), where “\(\mathsf{p/mC}\)” denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C. Surprisingly, our results reveal relationships that differ from their classical counterparts, such as \(\mathsf{p/mQIP} \ne \mathsf{p/mPSPACE}\) and \(\mathsf{mcoQSZKhv} \ne \mathsf{mQSZKhv}\). Building on this framework, we will see applications to cryptography, demonstrating that breaking one-way state generators and pseudorandom states, and EFI has \(\mathsf{mQCMA}\) and \(\mathsf{mQSZKhv}\) upper bounds, and that the average-case hardness of \(\mathsf{pQCZKhv}\) implies the existence of EFI. Notably, our results offer new insights into Impagliazzo’s five worlds view. Roughly, by substituting classical complexity classes in Pessiland, Heuristica, and Algorithmica with \(\mathsf{mBQP}\) and \(\mathsf{mQCMA}\) or \(\mathsf{mQSZKhv}\), we establish a natural connection between quantum cryptography and quantum promise complexity theory.

A broadcast encryption scheme allows a user to encrypt a message to \(N\) recipients with a ciphertext whose size scales sublinearly with \(N\). While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup process that generates a set of public parameters. Thereafter, users can independently generate their own public keys and post them to a public-key directory. Moreover, anyone can broadcast an encrypted message to any subset of user public keys with a ciphertext whose size scales sublinearly with the size of the broadcast set. Unlike traditional broadcast encryption, there are no long-term secrets in distributed broadcast encryption and users can join the system at any time (by posting their public key to the public-key directory).

Previously, distributed broadcast encryption schemes were known from standard pairing-based assumptions or from powerful tools like indistinguishability obfuscation or witness encryption. In this talk, I will describe the first distributed broadcast encryption scheme from a falsifiable lattice assumption. Specifically, we rely on the \(\ell\)-succinct learning with errors (LWE) assumption introduced by Wee (CRYPTO 2024). Previously, the only lattice-based candidate for distributed broadcast encryption goes through general-purpose witness encryption, which in turn is only known from the private-coin evasive LWE assumption, a strong and non-falsifiable lattice assumption. Along the way, I will also describe a direct construction of broadcast encryption from lattices that does not rely on any homomorphic evaluation machinery.

Joint work with David Wu.

As the first proof-of-work (PoW) permissionless blockchain, Bitcoin aims at maintaining a decentralized yet consistent transaction ledger as protocol participants (“miners”) join and leave as they please. This is achieved by means of a subtle PoW difficulty adjustment mechanism that adapts to the perceived block generation rate, and important steps have been taken in previous work to provide a rigorous analysis of the conditions (such as bounds on dynamic participation) that are sufficient for Bitcoin’s security properties to be ascertained.

Such existing analysis, however, is property-based, and as such only guarantees security when the protocol is run in isolation. In this paper we present the first (to our knowledge) simulation-based analysis of the Bitcoin ledger in the dynamic setting where it operates, and show that the protocol abstraction known as the Bitcoin backbone protocol emulates, under certain participation restrictions, Bitcoin’s intended specification. Our formulation and analysis extend the existing Universally Composable treat- ment for the fixed-difficulty setting, and develop techniques that might be of broader applicability, in particular to other composable formulations of blockchain protocols that rely on difficulty adjustment.

Joint work with Juan Garay, Yun Lu, Julien Prat, and Vassilis Zikas.

Recent constructions of vector commitments and non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve a shifted multi-preimage sampling problem. In this talk I will introduce the shifted multi-preimage sampling problem and then show how recent lattice-based constructions of vector commitments and hidden-bits model NIZKs can be viewed from the perspective of designing a solution to the shifted multi-preimage sampling problem. I will then describe a new technique for solving the shifted multi-preimage sampling problem by deriving a structured matrix with a public trapdoor from a short random string.

These techniques immediately yields the following improvements to lattice-based vector commitments and hidden-bits model NIZKs:

• We provide a dual-mode instantiation of the hidden-bits model (and by correspondence, a dual-mode NIZK proof for NP) with (1) a linear-size common reference string (CRS); (2) a transparent setup in hiding mode (which yields statistical NIZK arguments); and (3) hardness from LWE with a polynomial modulus-to-noise ratio. This improves upon the work of Waters (STOC 2024) which required a quadratic-size structured reference string (in both modes) and LWE with a super-polynomial modulus-to-noise ratio.

• We give a statistically-hiding vector commitment with transparent setup and polylogarithmic-size CRS, commitments, and openings from SIS. This simultaneously improves upon the vector commitment schemes of de Castro and Peikert (EUROCRYPT 2023) as well as Wee and Wu (EUROCRYPT 2023).

Joint work with Brent Waters and Hoeteck Wee.

We look at two practical problems, being: Microsoft Calendar and cloud based e-voting systems.

Part of the first part is co-authored by Alireza Kavousi (UCL, UK) and Aydin Abadi (Newcastle Univ., UK)

More details: Proceedings of the 2024 on ACM (Poster: Byzantine Discrepancy Attacks against Calendar, Set-intersection and Nations) and SECRYPT 2022 (Are Clouds making our Research Irrelevant and Who is at Fault?)

Additional link: https://www.scitepress.org/PublishedPapers/2022/113288/113288.pdf

We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning With Errors (LWE) assumption whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et al. (EUROCRYPT 2014) -- we reduce the key size in the latter from poly(depth, λ) to poly(λ). The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo (TCC 2022), which achieves poly(λ) key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

Joint work with Valerio Cini.

Verifying if a remote server has sufficient quantum resources to demonstrate quantum advantage is a fascinating question in complexity theory and a practical challenge. One approach is asking the server to solve some classically intractable problem, such as factoring. Another approach is the proof of quantumness protocols. These protocols enable a classical client to check whether a remote server can complete some classically intractable problem and thus can be used to distinguish quantum from classical computers. However, these two approaches mainly focus on distinguishing quantum computers from classical ones. They do not directly translate into ones that separate quantum computers with different quantum resources.

In this talk, we want to go one step further by showing protocols that can distinguish machines with different quantum depths. We call such protocols Classical Verification of Quantum Depth (CVQD). Roughly speaking, if a server has quantum circuit depth at most d, the classical client will reject it; otherwise, the classical client will accept it. Note that a malicious server, in general, can use classical computers to cheat. Thus, CVQD protocols shall be able to distinguish hybrid quantum-classical computers with different quantum depths. We will see two CVQD protocols: The first protocol can separate hybrid quantum-classical computers with quantum depth d and d+c (for c some fixed constant) assuming quantum LWE with d rounds. The second protocol is a one-round protocol assuming quantum LWE and the classical random oracle heuristics.

A zero-knowledge proof enables a prover to convince a verifier that a statement is true, without revealing anything beyond this fact. By running a zero-knowledge proof k times, it is possible to prove (still in zero-knowledge) that k separate statements are all true. However, this increases the communication by a multiplicative factor of k. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification possible?

Previous work of Kaslasi et al. (TCC 2020, Eurocrypt 2021) presented non-trivial batching for problems that have a non-interactive statistical zero-knowledge, but (1) at the cost of introducing interaction and (2) achieved communication that is roughly poly(n)+k, which is non-trivial but still scales linearly with k. In this talk, we show how to overcome both obstacles and achieve non-interactive batching with total communication of poly(n, log k).

Joint work with Changui Mu, Ron Rothblum, and Prashant Nalini Vasudevan.

In the design and analysis of cryptographic protocols it is often assumed an idealized model where the communication is synchronous and messages are always delivered by the start of the next round. However, while substantially simplifying things, hiding environmental nuisances and allowing us to focus on the task at hand, this strong assumption incurs significant overhead in practice.

In this talk, we will show that, as opposed to the synchronous setting, well-established techniques for parallel protocol composition completely break in the asynchronous setting. Specifically, we rule out the possibility of any black-box compiler for the parallel composition of arbitrary protocols. On the positive side, we introduce a round-preserving compiler for a restricted class of protocols (which includes all existing asynchronous MPC protocols) that achieves parallel composition in asynchronous networks.

Joint work with Ran Cohen, Juan Garay, Rutvik Patel, and Vassilis Zikas.

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (STOC 2024) recently showed how to construct a NIZK argument for NP from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions).

In this talk, I will show that an adaptively-sound BARG for NP together with an one-way function imply a computational NIZK argument for NP. Using complexity leveraging, adaptively-sound BARGs can be based on a sub-exponentially-secure somewhere sound BARG. Taken together, we obtain a NIZK argument for NP from one-way functions and a sub-exponentially-secure somewhere-sound BARG for NP. I then show that if we instead start with public-key encryption instead of one-way functions, then a polynomially-secure somewhere-sound batch argument for NP suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for NP is essentially no easier than constructing NIZK arguments for NP.

Joint work with Brent Waters and David J. Wu.

Using secure multiparty computation (MPC), organizations which own sensitive data (e.g., in healthcare, finance or law enforcement) can train machine learning models over their joint dataset without revealing their data to each other. At the same time, secure computation restricts operations on the joint dataset, which impedes computation to assess its quality. Without such an assessment, deploying a jointly trained model is potentially illegal. Regulations, such as the European Union's General Data Protection Regulation (GDPR), require organizations to be legally responsible for the errors, bias, or discrimination caused by their machine learning models. Hence, testing data quality emerges as an indispensable step in secure collaborative learning. However, performing distribution testing is prohibitively expensive using current techniques, as shown in our experiments.

We present HOLMES, a protocol for performing distribution testing efficiently. In our experiments, compared with three non-trivial baselines, HOLMES achieves a speedup of more than 10× for classical distribution tests and up to 104× for multidimensional tests. The core of HOLMES is a hybrid protocol that integrates MPC with zero-knowledge proofs and a new ZK-friendly and naturally oblivious sketching algorithm for multidimensional tests, both with significantly lower computational complexity and concrete execution costs.

Joint work with: Ian Chang and Katerina Sotiraki (UC Berkeley), Weikeng Chen (UC Berkeley & DZK Labs), Raluca Popa (UC Berkeley)

Over the last twenty years, hardware security and trust has evolved into a major new area of research at the intersection of semiconductor manufacturing, VLSI design and test, computer-aided design, architecture and system security. During the same period, machine learning has experienced a major revival in interest and has flourished from a nearly forgotten area to the talk of the town. In this presentation, we will first briefly review various machine learning-based solutions which have been developed to address a number of concerns in hardware security and trust, including hardware Trojan detection, counterfeit IC identification, provenance attestation, hardware-based malware detection, side-channel attacks, PUF modeling, etc. Then, we will examine the key attributes of these problems which make them amenable to machine learning-based solutions and we will discuss the potential and the fundamental limitations of such approaches. Lastly, we will ponder the role of and necessity for advanced contemporary machine learning methods in the context of hardware security and we will conclude with suggestions for avoiding common pitfalls when employing such methods.

A recent trend for organizations is to shift to cloud services which typically include email. As a result, the natural privacy concerns for users stem not only from outside attackers, but from insiders as well. Our solution does not rely on unproven assumptions and does not need a PKI. To achieve this, we partially rely on concepts from Private and Secure Message Transmission protocols, which are built on top of secret sharing. This technology allows us to distribute trust over email providers. Hence, the system remains secure as long as hackers are unable to penetrate a threshold number of providers, or this set of providers does not form a coalition to attack their users. The prototype of our proposed system has been implemented as an add-on for the Thunderbird email client, using Mozilla’s Web Crypto API and Rempe’s secret.js library. It currently supports the following secret sharing schemes: the 2-out-2 additive scheme (set as a default), the k-out-n threshold Shamir scheme, and the Rabin and Ben-Or robust scheme.

Joint work with: Nicolas Chiapputo (University of North Texas), Yvo Desmedt (University of Texas at Dallas)

Time-Lock Puzzles (TLPs) are a powerful tool for concealing messages until a predetermined point in time. When solving multiple puzzles, it becomes crucial to have the ability to batch-solve puzzles, i.e., simultaneously open multiple puzzles while working to solve a single one. Unfortunately, all previously known TLP constructions that support batch solving rely on super-polynomially secure indistinguishability obfuscation, making them impractical.

In light of this challenge, we present novel TLP constructions that offer batch-solving capabilities without using heavy cryptographic hammers. Our proposed schemes are simple and concretely efficient, and they can be constructed based on well-established cryptographic assumptions based on pairings or learning with errors (LWE). Along the way, we introduce new constructions of puncturable key- homomorphic PRFs both in the lattice and in the pairing setting, which may be of independent interest. Our analysis leverages an interesting connection to Hall’s marriage theorem and incorporates an optimized combinatorial approach, enhancing the practicality and feasibility of our TLP schemes. Furthermore, we introduce the concept of "rogue-puzzle attacks", where maliciously crafted puzzle instances may disrupt the batch-solving process of honest puzzles. We then propose constructions of concrete and efficient TLPs designed to prevent such attacks.

Joint work with: Jesko Dujmovic and Giulio Malavolta

At Eurocrypt '15, Garay, Kiayias and Leonardos introduced the notion of 2x1 (pronounced "2-for-1") Proofs of Work (PoWs), which allows miners to work on two independent instances using the same computational power needed for just one PoW. In that paper, 2x1 PoWs were used to achieve consensus (aka Byzantine agreement) on the blockchain assuming an honest majority of miners (which is optimal) in O(polylog(\kappa)) rounds of communication, where \kappa is the security parameter. In this talk we present a novel "mx1 PoW" generalization of the tool which effectively enables mining on m blockchains in parallel, and show two applications. First, the first consensus protocol in the PoW-based setting of Bitcoin that runs in expected-constant number of rounds, and second, a permissionless clock synchronization protocol with optimal skew.

Joint work with: Aggelos Kiayias (the University of Edinburgh and IOHK) and Yu Shen (the University of Edinburgh)

Can we design a private variant of "Google search" that would enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a potential solution to this problem, but would require Google to run a huge computation that is linear in the size of the entire internet to answer each encrypted search query, making it realistically infeasible! Is there a way for Google to preprocess the internet content into a special data structure that would then allow it to answer each encrypted search query very efficiently by only accessing a small number of locations in the data structure? We give a solution to this problem as a special case of our work.

Concretely, we construct the first schemes for "doubly efficient private information retrieval (DEPIR)" and "fully homomorphic encryption in the RAM model (RAM-FHE)" under standard cryptographic hardness assumptions (Ring Learning with Errors). Previously we only had heuristic candidate constructions that only satisfied relaxed variants of these primitives. Our new solutions combine tools from cryptography together with data structures for fast polynomial evaluation (Kedlaya and Umans '08).

Joint work with Wei-Kai Lin and Ethan Mook. To appear at STOC 2023. Recipient of "Best Paper Award."

Hertzbleed is a new family of side-channel attacks: frequency side channels. In the worst case, these attacks can allow an attacker to extract cryptographic keys from remote servers that were previously believed to be secure.

Hertzbleed takes advantage of our experiments showing that, under certain circumstances, the dynamic frequency scaling of modern x86 processors depends on the data being processed. This means that, on modern processors, the same program can run at a different CPU frequency (and therefore take a different wall time) when computing, for example, 2022 \+ 23823 compared to 2022 \+ 24436.

Hertzbleed is a real, and practical, threat to the security of cryptographic software. We have demonstrated how a clever attacker can use a novel chosen-ciphertext attack against SIKE (Now retired) to perform full key extraction via remote timing, despite SIKE being implemented as "constant time."

An oblivious common coin (OCC) allows n parties, up to t of which might be malicious, to agree on a random common value from a (not necessarily binary) domain. The coin is "oblivious" because parties may not be aware that agreement on a common value has been achieved. OCC is a fundamental tool in the area of multiparty cryptographic protocols. In fact, as shown by Rabin [FOCS '83], important distributed tasks such as Byzantine agreement (BA) reduce to an OCC, and moreover OCCs enable the circumvention of lower bounds and impossibility results for deterministic protocols. This line of research culminated in the seminal work of Feldman and Micali [STOC '88] for synchronous networks, and later Canetti and Rabin [STOC '93] for asynchronous networks, who showed how to construct a binary OCC in the information-theoretic setting, thereby obtaining expected constant-round protocols for synchronous (resp., asynchronous) BA "from scratch."

Unfortunately, running multiple expected constant-round protocols in parallel, as it would be required by a higher-level protocol where all/multiple parties broadcast a message in the same round, does not guarantee that all of them will terminate in expected constant rounds. In light of this, Ben-Or and El-Yaniv [Distributed Computing '03] showed how to solve arbitrarily many BA instances concurrently, while preserving the expected round complexity. They gave protocols for both synchronous and asynchronous networks, each relying on the existence of oblivious leader election (which immediately follows from a multi-valued OCC). However, while in the synchronous setting this can be obtained by extending the OCC construction of Feldman and Micali, the asynchronous version cannot be derived from Canetti and Rabin's binary coin without giving up on optimal resiliency (i.e., t < n/3 corruptions). In fact, as we discuss in the talk, an optimal asynchronous and multi-valued OCC does not seem to exist, nor is it straightforward to achieve, rendering an important body of follow-up work unsound.

We address this gap by presenting the first multi-valued OCC protocol that is simultaneously optimally-resilient and asynchronous, without relying on computational assumptions. Our result is built atop existing binary OCC constructions and uses novel combinatorial techniques. Furthermore, we use our OCC to simplify the standard approach for obtaining concurrent asynchronous BA in expected constant rounds, and prove the resulting protocols secure in Canetti's UC framework, a task that, as shown by Cohen et al. [CRYPTO '16], is particularly challenging for probabilistic-termination protocols.

This is joint work with Ran Cohen, Juan Garay, Rutvik Patel and Vassilis Zikas.

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates—possibly very widely—over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt '21]. In this work, we present the first proof-of-work (PoW)-based permissionless clock synchronization protocol.

Our construction assumes a public setup (e.g., a CRS) and relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.

Joint work with Juan Garay and Aggelos Kiayias.

Zero-knowledge proof (ZKP) allows one party, referred to as the prover, to convince another party, referred to as the verifier, that a statement about the prover’s secret witness is true. Zero-knowledge proof has been widely used in blockchains and crypto-currencies to achieve privacy and improve scalability. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time, limiting their efficiency and scalability in practice.

In this talk, we will present our recent work on building succinct ZKPs based on linear error-correcting code. The security relies on the good distance of the code and the collision resistant hash functions. The prover time is dominated by the encoding time of the linear code. The scheme is plausibly post-quantum secure and has a transparent setup.

We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be Ω(λ^2/log λ). Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing that the signature length cannot be improved without deviating from the group action framework.

We consider the digital forensics aspects of secret sharing. We investigate the problem of framing which occurs when a coalition is able to calculate the share of a participant who does not belong to it. In the extreme case one authorized coalition can calculate shares of another authorized coalition and use the secret in some way blaming another authorized coalition for their action.

(Paper appeared in IEEE Trans. Inf. Forensics Secur., 2021.)

In this talk, I will introduce a new notion of multiverse threshold signatures (MTS). In an MTS scheme, multiple universes~--~each defined by a set of (possibly overlapping) signers and a specific security threshold~--~can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe. I will present a new construction of MTS, our implementation efforts and envisioned applications to decentralized oracle networks.

This is joint work with Leemon Baird, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang.

A zero-knowledge proof (ZKP) is a cryptographic tool that allows a prover to prove the correctness of an NP statement to a verifier without disclosing the witness. With the recent developement of succinct zero-knowledge proof schemes, there are many efficient ZKP systems with applications in various areas. One of the applications is to improve the scalability of blockchains and crypto-currencies via the techniques of ZK-Rollup and zkEVM. In blockchains, users post all transactions on the chain for others to verify their validity, and thus the throughput of transactions is very low in practice. With succinct ZKPs, a layer-2 node can generate a proof for the correctness of thousands of transactions and post the short proof on-chain. In this way, both the on-chain storage and the time to verify the transactions are reduced significantly, improving the scalability of blockchains. This approach has been used by many blockchains in practice.

However, the main challenge in this solution is the overhead of the prover time and space. Currently, on a single powerful machine, the proof can only batch around 2000 transactions and it takes minutes to generate one proof. To address this issue, in this talk, we will present our ongoing work to speed up the prover time and improve the scalability via a distributed generation of ZKPs. Building on a recent ZKP scheme named Plonk, we are able to develop a distributed protocol for data parallel circuits with minimum communication and synchronization among the machines. Each machine only sends O(1) messages in 2 rounds and the final proof size remains O(1) as in the original Plonk. With such a distributed ZKP scheme, users can help with the proof generation in zk-Rollup and zk-EVM and both the efficiency and the scalability can be improved by a factor of M using M machines.

This is joint work with Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang and Dawn Song.

Attribute-based encryption (ABE) generalizes public-key encryption and enables fine-grained control to encrypted data. However, ABE upends the traditional trust model of public-key encryption by requiring a single trusted authority to issue decryption keys. A compromised central authority has the ability to decrypt every ciphertext in the system.

This work introduces registered ABE, a primitive that allows users to generate secret keys on their own and then register the associated public key with a "key curator" along with their attributes. The key curator aggregates the public keys from the different users into a single compact master public key. To decrypt, users occasionally need to obtain helper decryption keys from the key curator which they combine with their own secret keys. We require that the size of the aggregated public key, the helper decryption keys, the ciphertexts, as well as the encryption/decryption times to be polylogarithmic in the number of registered users. Moreover, the key curator is entirely transparent and maintains no secrets. Registered ABE generalizes the notion of registration-based encryption (RBE) introduced by Garg et al. (TCC 2018), who focused on the simpler setting of identity-based encryption.

We construct a registered ABE scheme that supports an a priori bounded number of users and policies that can be described by a linear secret sharing scheme (e.g., monotone Boolean formulas) from assumptions on composite-order pairing groups (the same pairing-based assumptions previously used to construct vanilla ABE). Notably, our approach deviates sharply from previous techniques for constructing RBE and only makes black-box use of cryptography. All existing RBE constructions (a weaker notion than registered ABE) rely on heavy non-black-box techniques. In fact, the encryption and decryption costs of our construction are comparable to those of vanilla pairing-based ABE. Finally, as a feasibility result, we show how to construct a registered ABE scheme that supports general policies and an arbitrary number of users from indistinguishability obfuscation and somewhere statistically binding hash functions.

This is joint work with Susan Hohenberger, Brent Waters, and David Wu.

Non-interactive batch arguments for \(\mathsf{NP}\) provide a way to amortize the cost of \(\mathsf{NP}\) verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple \(\mathsf{NP}\) statements with communication that scales sublinearly in the number of instances.

In this work, we study fully succinct batch arguments for \(\mathsf{NP}\) in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances \(T\), but also sublinearly with the size of the \(\mathsf{NP}\) relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.

We give a direct construction of a fully succinct batch argument for \(\mathsf{NP}\) that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically-binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof \(\pi\) on \(T\) statements \((x_1, \ldots, x_T)\) and "update" it to obtain a proof \(\pi'\) on \((x_1, \ldots, x_T, x_{T + 1})\). Notably, the update procedure only requires knowledge of a (short) proof for \((x_1, \ldots, x_T)\) along with a single witness \(w_{T + 1}\) for the new instance \(x_{T + 1}\). Importantly, the update does not require knowledge of witnesses for \(x_1, \ldots, x_T\).

This is joint work with Kristin Sheridan, Brent Waters, and David Wu.

We provide the first constant-round construction of post-quantum non-malleable commitments under the minimal assumption that post-quantum one-way functions exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required Ω(log*λ) rounds under the same assumption.

We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest.

As an application, when combined with existing work, our results yield the first constant-round post-quantum secure multiparty computation under the polynomial hardness of quantum fully-homomorphic encryption and quantum learning with errors.

This is joint work with Omkant Pandey and Takashi Yamakawa.

Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced "best-possible security" properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation.

In this work, we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous ``best-possible security'' version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or "quality" of AE-security that is obtained when a protocol's hybrids are replaced with almost-everywhere components.

This is joint work with Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky and Vassilis Zikas.

Data cooperatives allow their members--the data owners--to pool their digital assets together for processing and access management. In this context, reputation is an important measure of trust, which can effectively complement financial assets in the decentralized scenario, also providing incentives for users’ honest behavior. We present a decentralized data cooperative system based on the Proof-of-Reputation and Proof-of-Stake blockchains. In order to provide inclusivity for low reputation (newly joined) users, which is required in our community based scenario, we use the tier-based committee selection introduced by Kleinrock et al. at Indocrypt 2020. As the underlying Proof-of-Stake system, we use Snow White due to its convenient properties such as flexible committee selection and user participation.

This is joint work with Abiola Salau, Ram Dantu, Kritagya Upadhyay, and Syed Badruddoja.

Book authors often "copy" chapters from earlier books, implying that new books might be outdated. Worse, today we have so many security venues, that we find applied crypto "everywhere". Unfortunately, these working on applying crypto do not check updated literature as is evident from work published at, e.g., at USENIX. To give an example we focus on anonymity, in particular the paper published in 2019 (IEEE Tr. Inf. Th.).