Seminar

Title:CSI-Otter: Isogeny-based (Partially) Blind Signatures from the Class Group Action with a Twist

Abstract: 

: In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the linear identification protocol abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT’19), which was used to generically construct Schnorr-like blind signatures based on modules such as classical groups and lattices. Consequently, our scheme is provably-secure in the polylogarithmic (in the number of security parameter) concurrent execution and does not seem susceptible to the recent efficient ROS attack exploiting the linear nature of the underlying mathematical tool. In more detail, our blind signature exploits the quadratic twist of an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size 128 B and signature size 8 KB under the CSIDH-512 parameter sets—these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a new ring variant of the group action inverse problem (rGAIP), we can halve the signature size to 4 KB while increasing the public key size to 512 B. We provide preliminary cryptanalysis of rGAIP and show that for certain parameter settings, it is essentially as secure as the standard GAIP. Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key—constructing such a hash function in the isogeny setting remains an open problem.

Title: Distances in trees and inequalities for matroids

Abstract: The distance matrix of a tree appears in a range of contexts, from phylogenetics to physical chemistry.  I will describe a new result about the spectrum of this matrix, one that gives affirmative answers to two questions about matroid positivity properties.  These are both strengthenings of Mason's conjectures about the log-concavity of sequence of numbers of independent sets of a matroid, proposed byIgor Pak and by Giansiracusa, Rincón, Schleis, Ulirsch, respectively.

This is joint work with Federico Ardila, Sergio Cristancho,Chris Eur, June Huh, and Botong Wang.

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

Title:Compact Lattice Signatures via Iterative Rejection Sampling (ePrint: 2024/2052)

Abstract: This talk reviews the paper by Joel Gärtner that received one of the Best Paper Awards at CRYPTO 2025. The work introduces a new method for constructing lattice signatures using the “Fiat–Shamir with aborts” approach. By carefully designing the rejection condition, the authors significantly lower the rejection probability. This leads to a signature scheme that is much more compact than previous lattice-based Fiat–Shamir signature schemes. In this talk, we will carefully examine the proposed techniques as well as the concrete parameters that enable such compact signatures.

Title:Enumerating planar stuffed maps as hypertrees of mobiles

Abstract: A planar stuffed map is an embedding of a graph into the 2-sphere, considered up to orientation-preserving homeomorphisms, such that the complement of the graph is a collection of disjoint topologically connected components that are each homeomorphic to the 2-sphere with multiple boundaries. This is a generalization of planar maps whose complement of the graph is a collection of disjoint topologically connected components that are each homeomorphic to a disc. In this talk I will outline my work in constructing a bisection between bipartite planar stuffed maps and collections of integer-labelled trees connected by hyperedges such that they form a hypertree. This bijection directly generalizes the Bouttier-Di Franceso-Guitter bijection between bipartite planar maps and mobiles. Additionally, we show that the generating functions of these trees of mobiles satisfy both an algebraic equation, generalizing the case of ordinary planar maps, and a new functional equation. As an example, we explicitly enumerate a class of stuffed quadrangulations.

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

Title: Hash-Based Digital Signatures: An Overview with a Focus on Group Signature Schemes

Abstract: Digital signature schemes are crucial for secure communication, authentication, and data integrity in applications like secure email, financial transactions, and blockchain systems. However, classical schemes (e.g., RSA, ECDSA, Schnorr) are vulnerable to quantum attacks, driving the shift to post-quantum cryptographic alternatives.

Hash-based signature schemes are key because their security relies on cryptographic hash functions, not number-theoretic problems, making them more robust for post-quantum security. These schemes are categorized into one-time, few-time, and many-time signatures. To date, NIST has standardized three many-time hash-based schemes: LMS, XMSS, and SPHINCS+.

Group Signature Schemes (GSS) enable anonymous message signing on behalf of a group, with a designated authority able to reveal the signer's identity when necessary. This feature is critical in privacy-preserving applications like anonymous attestations and reputation systems. Fully dynamic GSSs are particularly valuable as they allow users to join or be revoked without system-wide updates. 

In this talk, I will review key hash-based group signature schemes, including G-Merkle, DGM, DGMT, and SPHINX-in-the-Head, discussing their limitations in scalability and efficiency. I will then introduce DGSP, our new scalable and efficient fully dynamic GSS, and compare it with existing post-quantum alternatives to highlight its advantages.

Title: A Combinatorial Gateway to Calabi-Yau Toric Geometry

Abstract: The goal of this talk is to introduce Calabi-Yau toric geometry from a purely combinatorial perspective, through the rich structures carried by an embedded bipartite graph on a torus called a dimer model.

In the pre-talk, we will demonstrate how matchings, tilings, and quivers naturally encodes deep geometric and physical content. No background in algebraic geometry will be assumed; instead, we’ll build the story from the ground up, with an emphasis on visual intuition and discrete structures.

Next, I will discuss how dimer models simultaneously encode the data of a toric Calabi-Yau singularity and its mirror dual, unifying perspectives from the B-model and A-model of homological mirror symmetry through noncommutative algebras. We will proceed with some recent developments and open problems, including connections to the symplectic geometry of Landau-Ginzburg models and Van den Bergh’s noncommutative resolution conjecture for toric Gorenstein affine singularities. To conclude the talk, we will discuss an example of a higher dimensional generalization and its connection to my recent research works.

This talk is also partially based on two undergraduate research projects in the present semester, where we study variations of dimer models of the same lattice polygon from different choices in the fast inverse algorithm, and implications on the two sides of mirror symmetry:

- (DRP) Dimer Variation and Geometry of Landau-Ginzburg Models, with Kenneth Xiao and Elizabeth Cai (A-model)

- (NSERC USRA) Dimer Variation and NCCR Mutations, with Filip Mildrag and Elana Kalashnikov (B-model)

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

Title: Graphs with High Chromatic Number

Abstract: The classical theorem of Brooks tells us that if a graph G has no colouring with its maximum degree ∆≥3 colours, then it contains a clique with ∆+1 vertices. Does a similar phenomenon occur when the chromatic number is slightly smaller than ∆? Even the next case is unknown: in 1977, Borodin and Kostochka famously conjectured that if ∆≥9 and G has no (∆-1)-colouring then it contains a ∆(G)-clique. We discuss various results and questions around this conjecture.

Title: Approximation Algorithms for Flexible Graph Connectivity

Abstract: This is a "non specialist" talk on a couple of results from a long-running project in the area of capacitated network design. The key problem here is to find a sub-graph of minimum cost that satisfies a (global) edge connectivity requirement, where the input is a graph G that has a capacity u(e) and a cost c(e) for each edge e in E(G). (Note: The minimum spanning tree problem is the special case where the connectivity requirement is one and  all edge-capacities are one.)

The results in the talk are from joint work with Bansal, Grout, Ibrahimpur, Khanna, and Simmons.

Title: On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption

Abstract: Traditional encryption (secret key and public key encryption) has a very limited functionality. Namely, it allows encryption of data for a single recipient that can recover the entire data. This is typically sufficient for transmitting data over insecure channels, but insufficient for many modern applications, like end-to-end encrypted cloud storage, where partial access to the data might be needed.

Functional encryption (FE) is a cryptographic primitive that can solve this challenge by allowing to generate customized secret keys that are associated with a function f. Decrypting with such a secret key will reveal only f(m), where m is the encrypted message, and reveal nothing else about m. One of the most well studied variants of FE is inner-product functional encryption (IPFE), where the functions f are restricted to linear functions.

All known instantiations of IPFE, even of its secret-key version, require strong assumptions typically used for public-key encryption. In this talk I will give an insight on why this is the case: An impossibility result for black-box constructions of IPFE from secret-key assumptions (like one-way functions).

The core of our proof is based on a new result of extremal combinatorics, which we proof based on Fourier analysis or the Cauchy-Schwartz inequality.

The talk will first introduce the cryptographic background and give an overview about the cryptographic part of the proof. Then, the combinatorial problem we encountered and our solution will be discussed in more detail. The talk will not require any prior knowledge in cryptography.

The full version of the paper presented can be found here: https://eprint.iacr.org/2024/1877

Title: Centralizers in the Plactic Monoid

Abstract: Let u be a word over the positive integers. Motivated in part by a question of representation theory, we study the centralizer set C(u), which consists of words w for which wu and uw are Knuth-equivalent. In particular, we characterize C(u) when u has few letters or is a certain type of decreasing sequence, and we address related enumerative questions.

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