Welcome to Combinatorics and Optimization

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: 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:  Much of post-quantum PKE from unstructured noisy linear algebra relies on LWE or Alekhnovich’s LPN: both assume samples of the form (A, As+e) are computationally indistinguishable from (A, u), but with different noise models. LWE uses “short” errors, while Alekhnovich LPN uses sparse errors. Motivated by uncertainty around future cryptanalytic advances, we ask whether one can still obtain PKE from noisy linear assumptions even if both LWE and Alekhnovich LPN were broken. We talk about two new assumptions: Learning with Two Errors (LW2E), which mixes an LWE-style short error with an LPN-style sparse error, and Learning with Short and Sparse Errors (LWSSE), which uses errors that are simultaneously short and sparse but denser than Alekhnovich LPN.