Events

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.

Title: Cover-free Families on Graphs

Abstract: A family of subsets of a t-set is a d-cover-free family or d-CFF if no subset in the family is contained in the union of any d other subsets. Let t(d, n) denote the minimum t for which there exists a d-CFF of a t-set with n subsets. t(1, n) is determined using Sperner’s theorem. For d ≥ 2, we rely on bounds for t(d, n). Erdős, Frankl, and Füredi proved 3.106 log(n) < t(2, n) < 5.512 log(n). 

Title:ROAST: Robust Asynchronous Schnorr Threshold Signatures

Abstract: In this talk, I will review ROAST, which is a practical wrapper that turns any threshold signature scheme into a robust and asynchronous threshold signature scheme, as long as the base scheme is semi-interactive with identifiable aborts and unforgeable under concurrent signing sessions. Since the well-known FROST scheme meets these conditions, applying ROAST to FROST yields a simple, efficient Schnorr-based threshold signature scheme.

Title: Minimising the Martin invariant

Abstract: The Martin invariant of an even degree regular graph is an integer, defined by a recurrence at a vertex. In this talk, we define
this invariant and review some of its properties, and then focus on the following question: which graphs minimise the Martin invariant?

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

Title: Combinatorics of causal set theory

Abstract: Causal set theory is an approach to quantum gravity where spacetime is a locally finite poset. This approach asks interesting questions about posets that are as of yet little explored in combinatorics. I'll explain how I got interested in this subject recently and some of the aspects that might particularly appeal to a discrete mathematician.