Events

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: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: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: Hadamard matrices, quantum groups, and quantum games.

Abstract: A Hadamard matrix is a square matrix of complex numbers whose entries have modulus 1, and whose columns are pairwise orthogonal.  Hadamard matrices appear all over mathematics and its applications, including computer science, statistics, and quantum physics. In this talk, I will give a brief introduction to Hadamard matrices with a particular focus on Hadamard matrices whose entries are powers of a fixed root of unity (a.k.a. Butson Hadamard matrices).  Butson matrices are interesting combinatorial objects, and can be thought of as generalizations of the Fourier transform matrix associated to a finite abelian group.  For a general Hadamard matrix, I will explain how one can associate to it two natural "group-like" objects, called quantum groups (or Hopf algebras).   The first type of quantum group associated to a Hadamard matrix can be thought of as a generalization of the abelian group associated to a Fourier matrix, and the second type of quantum group can be thought of as the "quantum automorphism group" of the Hadamard matrix.  This latter quantum group is particularly interesting as it can be used to define a notion of quantum equivalence of Hadamard matrices, and it turns out that many classically inequivalent Hadamard matrices can be quantum equivalent.  Time permitting, I'll interpret quantum equivalence of Hadamard matrices in terms of a certain non-local game involving Hadamard matrices that can be played perfectly with the aid of quantum entanglement.  This is joint work with Daniel Gromada, Roberto Hernandez-Palomares, and Nicky Priebe.  

Title: An overview of Clapoti(s) and its variants

Abstract: In 2022, it was discovered that one can break SIDH by working with isogenies of higher dimensions. Since then, the study of high dimensional isogenies and their applications has been a prominent subject in isogeny-based cryptography. One such application is Clapoti, an algorithm allowing for the evaluation of ideal class group actions in polynomial time. However, the exact time cost of Clapoti is unclear as it has no implementation. This is mainly because there is currently no generic implantation for high dimensional isogeny computation, although there are some implementations for subsets of these isogenies. Because of this, variants of Clapoti have been proposed that only use isogenies for which we have implementations. In this presentation, we will briefly look at two of these variants, KLaPoTi and PEGASIS, how they work, their advantages and their limitations.

Title: Counting Substructures in Hypergraphs with Spectrum

Abstract: Jacobi’s classical result expresses the generating function for closed walks at a vertex of a graph as the ratio of two characteristic polynomials. We find a hypergraph analogue of this relationship, showing that the same rational function for a hypergraph also counts combinatorial substructures within it, called infragraphs. We use Viennot’s Heaps of Pieces framework to establish this result for the adjacency tensor of a hypergraph. As an immediate consequence, we obtain an alternative proof for the monotonicity of the principal eigenvalue of a hypergraph. This is based on joint work with Joshua Cooper and Utku Okur (arXiv: 2411.03567).

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

Title: Turnpike phenomena in optimal control

Abstract: This talk will begin with a concise introduction to optimal control, viewed as an optimization problem where the decision variables are subject to dynamical constraints. We will then discuss the turnpike phenomenon in optimal control problems and show how it can be characterized through the energy-based concept of dissipativity of the underlying dynamical system. The theoretical results will be illustrated in the context of linear–quadratic optimal control problems, both for discrete and continuous time dynamics, where a complete characterization can be derived in terms of the spectral properties of the system.