Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the title matches:
Limit to events where the first date of the event:
Date range
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, March 13, 2026 10:30 am - 11:30 am EDT (GMT -04:00)

Crypto Reading Group - Huanhuan Chen-Updatable Encryption

Speaker:

 Huanhuan Chen
Affiliation: University of Waterloo
Location: MC 6029

Abstract:Updatable encryption (UE) enables a cloud server to update ciphertexts using client-generated tokens. There are two types of UE: ciphertext-independent (c-i) and ciphertext-dependent (c-d). In terms of construction and efficiency, c-i UE utilizes a single token to update all ciphertexts. The update mechanism relies mainly on the homomorphic properties of exponentiation, which limits the efficiency of encryption and updating. Although c-d UE may seem inconvenient as it requires downloading parts of the ciphertexts during token generation, it allows for easy implementation of the Dec-then-Enc structure. This methodology significantly simplifies the construction of the update mechanism. Notably, the c-d UE scheme proposed by Boneh et al. (ASIACRYPT’20) has been reported to be 200 times faster than prior UE schemes based on DDH hardness, which is the case for most existing c-i UE schemes. Furthermore, c-d UE ensures a high level of security as the token does not reveal any information about the key, which is difficult for c-i UE to achieve. However, previous security studies on c-d UE only addressed selective security; the studies for adaptive security remain an open problem.

In this study, we make three significant contributions to ciphertext-dependent updatable encryption (c-d UE). Firstly, we provide stronger security notions compared to previous work, which capture adaptive security and also consider the adversary’s decryption capabilities under the adaptive corruption setting. Secondly, we propose a new c-d UE scheme that achieves the proposed security notions. The token generation technique significantly differs from the previous Dec-then-Enc structure, while still preventing key leakages. At last, we introduce a packing technique that enables the simultaneous encryption and updating of multiple messages within a single ciphertext. This technique helps alleviate the cost of c-d UE by reducing the need to download partial ciphertexts during token generation.
Friday, March 13, 2026 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium -Seunghoon Lee-Parallel Reversible Pebbling: Time-Space Tradeoffs on DAGs (with Cryptographic Motivation)

Speaker: Seunghoon Lee
Affiliation: University of Waterloo
Location: MC 5011

Abstract: The (parallel) pebbling game is a useful abstraction for analyzing the resources (e.g., space, space-time, amortized space-time) needed to evaluate a function f with a static data-dependency graph G on a (parallel) computer. The underlying question is purely combinatorial: what tradeoffs does a directed acyclic graph (DAG) force between storing intermediate values and recomputing them? This viewpoint has been particularly influential in cryptography, where many “Memory-Hard Function” (MHF) constructions can be modeled by evaluating a fixed DAG.

Classical pebbling, however, does not capture an essential constraint in quantum/reversible computation: intermediate information cannot be discarded freely, so cleanup must respect the dependency structure. While sequential reversible pebbling has been used to study space-time tradeoffs in sequential settings, it does not reflect the space-time tradeoffs for parallel quantum/reversible algorithms. To model this, we introduce the parallel reversible pebbling game and use it to analyze reversible space-time and amortized costs for important graph families, including line graphs and structured DAGs arising in MHF constructions (e.g., Argon2i and DRSample).
The talk highlights two core results: First, we give a lower bound on the reversible amortized space-time cost for a line graph, which yields a separation between classical and reversible pebbling costs, showing a super-constant (yet sub-polynomial) gap. Second, this overhead is nevertheless controlled: we show that any classical parallel pebbling can be transformed into a reversible one with only a sub-polynomial loss. This generic transformation serves as a central tool for analyzing broader graph families.
The talk will focus on the combinatorial aspects of cryptographic applications; no background in cryptography is assumed. Based on joint work with Jeremiah Blocki and Blake Holman: The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs (TCC 2022), and The Impact of Reversibility on Parallel Pebbling (EUROCRYPT 2025).
Thursday, March 19, 2026 2:30 pm - 3:30 pm EDT (GMT -04:00)

Algebraic and enumerative combinatorics seminar - Moriah Elkin- Open quiver loci, CSM classes, and chained generic pipe dreams

Speaker: Moriah Elkin
Affiliation: Cornell University
Location: MC 5417

Abstract: In the space of type A quiver representations, putting rank conditions on the maps cuts out subvarieties called "open quiver loci." These subvarieties are closed under the group action that changes bases in the vector spaces, so their closures define classes in equivariant cohomology, called "quiver polynomials." Knutson, Miller, and Shimozono found a pipe dream formula to compute these polynomials in 2006. To study the geometry of the open quiver loci themselves, we might instead compute "equivariant Chern-Schwartz-MacPherson classes," which interpolate between cohomology classes and Euler characteristic. I will introduce objects called "chained generic pipe dreams" that allow us to compute these CSM classes combinatorially, and along the way give streamlined formulas for quiver polynomials.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm.

Friday, March 20, 2026 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium -Bruno Sterner-Large smooth twins from short lattice vectors

Speaker: Bruno Sterner
Affiliation: University of Waterloo
Location: MC 5011

Abstract: We discuss the challenging problem of finding pairs of consecutive smooth integers, which we refer to as a smooth twin. In other words the largest prime factor in the twin is relatively small. This computational number theoretic problem has appeared in the context of isogeny-based cryptography whereby a select number of cryptosystems use such twins as part of their parameter setup. The challenging part to the problem is finding smooth twins whose largest prime factor is as small as possible. Prior to this work, twins of this nature have at most 74-bits which is much too small for cryptographic relevance. We bridge this gap by presenting a new method that finds significantly larger smooth twins with as small as possible smoothness bound. The idea of our algorithm is based on the well known and studied problem of finding short vectors in a well constructed lattice. We report a 196-bit smooth twin which falls in this regime as well as a few larger twins that have small (but not the smallest) smoothness bounds.