Events

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.

Title:The satisfiability threshold and solution space of random uniquely extendable CSPs

Abstract: A random constraint satisfaction problem (CSP) consists of a set of variables and a set of randomly chosen constraints. Many commonly studied CSPs are constructed by choosing constraints of a specific form. One such problem is $k$-UE-SAT, where each constraint is chosen from the set of uniquely extendable (UE) constraints. A conjecture due to Molloy and Connamacher gives an exact value for the high probability satisfiability threshold of $k$-UE-SAT problems. We make progress towards this conjecture by showing that a subclass of random CSPs with UE constraints has the conjectured satisfiability threshold. We also describe the solution space geometry for this class of CSPs, and make further conjectures about the general $k$-UE-SAT problem.This talk is based on joint work with Jane Gao.

Title:Hybrid Signature Schemes

Abstract: The transition to post quantum cryptography comes with many challenges. On the one hand, classically secure algorithms are well-tested, and we have a high degree of confidence in them against classical adversaries, but they are vulnerable to quantum computers. On the other hand, we currently have no reason to believe that post quantum algorithms are vulnerable to either classical or quantum adversaries, however, they are still relatively new, and because of that, they have not been scrutinized to the degree of their classical counterparts. Additionally, the transition will not happen instantaneously, and there will be a period of time where some interfaces are able to support post quantum algorithms while others can only support classical ones. One possible solution to these challenges (on the digital signature side of things) is to use hybrid signature schemes, which, loosely speaking, are digital signature schemes based off of both a classical and a hybrid digital signature scheme, which are secure if at least one of the underlying signature schemes is secure. In this talk, I will cover a few different signature combiners, and compare and contrast both how they work and the properties they guarantee. This talk is based off of the papers "A Note on Hybrid Signature Schemes" by Nina Bindel and Britta Hale, and "Bird of Prey: Practical Signature Combiners Preserving Strong Existential Unforgeability" by Jonas Janneck.

Title: Tilings of Benzels (and other finite regions) in the hexagon grid

Abstract: In 1990, Conway and Lagarias introduced tilability criteria for tilability for finite regions of the hexagon and square grids. In the same year, Thurston expanded upon their work, introducing the height function criterion. We will discuss some new results in tilability: A new tilability criteria via the SL_2(C) double dimer model, and enumeration of tilings of special regions called Benzels, introduced in 2020 by Propp, using a technique called compression. If time allows, we will also discuss ongoing work that expands Thurston's height function to stone-and-bone tilings of the hexagon grid.

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

Title: Valuated Delta Matroids and Principal Minors

Abstract: Delta matroids are a generalization of matroids that arise naturally from combinatorial objects such as matchings, ribbon graphs, and principal minors of symmetric and skew symmetric matrices. In this talk, we will define valuated delta matroids and explore their connection with principal minors of Hermitian matrices, generalizing work by Rincón on valuated even delta matroids and skew symmetric matrices. Based on joint work with Nathan Cheung, Gaku Liu, and Cynthia Vinzant.

Title:Almost Regular Matroids

Abstract: Regular matroids form an important and extensively studied class of matroids and have numerous known descriptions and characterizations. In the 1980s, Truemper gave a constructive description of the related class of almost regular matroids: non-regular matroids $M$ such that for every element $e$ of $M$ either $M/e$ or $M\backslash e$ is regular. In this talk, we present a description of almost regular matroids in terms of grafts. A consequence of this description is that almost regular matroids have bounded complexity. We outline some of the proof ideas after introducing the necessary background.

Title:Seems Legit: Automated Analysis of  Subtle Attacks on Protocols that Use Signatures

Abstract: The standard definition of security for digital signatures—existential unforgeability—does not ensure certain properties that protocol designers might expect. For example, in many modern signature schemes, one signature may verify against multiple distinct public keys. It is left to protocol designers to ensure that the absence of these properties does not lead to attacks. Modern automated protocol analysis tools are able to provably exclude large classes of attacks on complex real-world protocols such as TLS 1.3 and 5G. However, their abstraction of signatures (implicitly) assumes much more than existential unforgeability, thereby missing several classes of practical attacks. We give a hierarchy of new formal models for signature schemes that captures these subtleties, and thereby allows us to analyse (often unexpected) behaviours of real-world protocols that were previously out of reach of symbolic analysis. We implement our models in the Tamarin Prover, yielding the first way to perform these analyses automatically, and validate them on several case studies. In the process, we find new attacks on DRKey and SOAP’s WS-Security, both protocols which were previously proven secure in traditional symbolic models.

Title: Generalized Abelian Complexities for Pisot-Type Substitutive Sequences

Abstract: Two finite words are said to be abelian equivalent if one is a permutation of the letters of the other. For an infinite word, one can investigate the associated complexity function, called Abelian complexity, which is a classical object of study in combinatorics on words. In particular, many works study the abelian complexity of automatic sequences, where a longstanding conjecture states that the abelian complexity of an automatic sequence is a regular sequence. We have studied when the abelian complexity can be computed efficiently, in particular using the theorem prover Walnut. To this end, we study words that are fixed points of Pisot-type substitution and prove that these words satisfy the conjecture. If time permits, I will present k-abelian complexities, which are intermediate complexities between the abelian complexity and the factor complexity. I will also explain how our results can be extended to these
complexities and how we can obtain a two-dimensional linear representation of some examples. This talk is based on joint work with J-M Couvreur, M. Delacourt, N. Ollinger, J. Shallit, and M. Stipulanti (arXiv: 2504.13584).

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