webnotice

Abstract:  FrodoKEM is a lattice-based Key Encapsulation Mechanism (KEM) based on unstructured lattices. From a security point of view this makes it a conservative option to achieve post-quantum security, hence why it is favored over the NIST winners by several European authorities (e.g., German BSI and French ANSSI). Relying on unstructured instead of structured lattices (e.g., CRYSTALS-Kyber) comes at the cost of additional memory usage, which is particularly critical for embedded security applications such as smart cards. For example, prior FrodoKEM-640 implementations (using AES) on Cortex-M4 require more than 80 kB of stack making it impossible to run on embedded systems. In this work, we explore several stack reduction strategies and the resulting time versus memory trade-offs. Concretely, we reduce the stack consumption of FrodoKEM by a factor 2–3× compared to the smallest known implementations with almost no impact on performance. We also present various time-memory trade-offs going as low as 8 kB for all AES parameter sets, and below 4 kB for FrodoKEM-640. By introducing a minor tweak to the FrodoKEM specifications, we additionally reduce the stack consumption down to 8 kB for all the SHAKE versions. As a result, this work enables FrodoKEM on embedded systems.

Abstract: Suppose that you are given an ordering of the elements of a $k$-connected matroid, and you want to remove the elements one at a time, in the given order, keeping the intermediate matroids as highly connected as possible. How much connectivity can you keep?

Abstract: The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander and Ramanujan graphs. In this talk, I will give an overview of recent work studying the maximum order v(k,\theta)  of a regular graph (bipartite graph or hypergraph) of given valency k whose second largest eigenvalue is at most a given value \theta. This problem can be seen as a spectral Moore problem and has connections to Alon-Boppana theorems for graphs and hypergraphs and with the usual Moore or degree-diameter problem. 

Abstract: A (t,n)-threshold signature scheme splits a signing key among "n" participants so that any "t" can jointly produce a valid signature under a single public key, while fewer than "t" cannot. There are three common types of threshold signature schemes: (i) Robust schemes, which guarantee signature production provided at least "t" parties are honest; (ii) Identifiable-abort schemes, which may fail to produce a signature but expose at least one misbehaving signer; and (iii) Simple schemes, which guarantee neither robustness nor identifiable abort, but output a valid signature when "t" honest participants collaborate without deviating from the protocol.

Motivated by NIST's recent emphasis on post-quantum multiparty and threshold designs, this talk presents a new approach to centralized, lattice-based (t,n)-threshold signatures. We first construct a (t,n)-threshold one-time signature and then upgrade it to a many-time scheme by combining it with a long-term signature so that all threshold signatures verify under a single public key.

Abstract: Tensor integrals are the generating functions of triangulations of pseudo-manifolds. Such triangulations are constructed by gluing simplices along facets. These generating functions satisfy an infinite system of recursive equations called the Dyson-Schwinger equations, derived by reclusively gluing together triangulations. Such integrals also satisfy positivity constraints. By combining the Dyson-Schwinger equations and positivity constraints in a process called bootstrapping we are able to deduce known results for the generating functions of certain classes of triangulations as well as find new explicit formulae. This talk is based on joint work with Carlos I. Perez-Sanchez and Brayden Smith.

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

Abstract: A weighted graph G with countable vertex set is bounded if there is an upper bound on the maximum of the sum of absolute values of all edge weights incident to a vertex in G. Most work done on quantum walks focus on finite graphs. In this talk, we extend the theory to bounded infinite graphs and discuss results concerning the rarity of perfect state transfer. This is joint work with Chris Godsil, Steve Kirkland, Sarojini Mohapatra and Hiranmoy Pal.

Abstract:  Modern secure communication systems, such as iMessage, WhatsApp, and Signal include intricate mechanisms that aim to achieve very strong security properties. These mechanisms typically involve continuously merging fresh secrets into the keying material that is used to encrypt messages during communications. In the literature, these mechanisms have been proven to achieve forms of Post-Compromise Security (PCS): the ability to provide communication security even if the full state of a party was compromised some time in the past. However, recent work has shown these proofs cannot be transferred to the end-user level, possibly because of usability concerns. This has raised the question of whether end-users can actually obtain PCS or not, and under which conditions.

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.