Title: Towards post-quantum cryptography: complexity and protocols

LIVE STREAM: https://uwmadison.zoom.us/j/92090109069?pwd=SWRoOWpkVDRoc1dyZGpBd25jSW0wUT09

Abstract: The advent of quantum computers places many widely used cryptographic protocols at risk.  In response to this threat, the field of post-quantum cryptography has emerged. The most broadly recognized post-quantum protocols are related to lattices. Beyond their resistance to quantum attacks, lattices are instrumental tools in cryptography due to their rich mathematical structure. In this talk, I will present my work on understanding the complexity of lattice problems and on constructing lattice-based cryptographic protocols useful in practical scenarios. First, I will present an optimal construction for worst-case collision-resistant hash functions based on a lattice problem. Second, I will show the first lattice-based construction of cryptographic proofs with minimal communication and zero-knowledge for any language in NP.

Bio: Katerina Sotiraki is a postdoc at UC Berkeley, working with Alessandro Chiesa and Raluca Popa. She received her PhD from MIT in 2020, with a dissertation supervised by Vinod Vaikunanthan.

At MIT she held the Kanellakis Fellowship and the Chateaubriand Fellowship, and was an intern for Microsoft Research (Redmond)and IDC (Herzilya).  Her bachelor's degree is from the National Technical University of Athens.

Her primary research work is in cryptography.  In particular, she studies how cryptography will need to evolve as quantum computation becomes powerful enough to threaten standard protocols such as RSA public-key encryption.  One primary tool for advancing post-quantum cryptography is the theory of lattices (discrete additive subgroups of Euclidean space).  Accordingly, she has contributed both new cryptographic tools that exploit lattices, and a deeper understanding of the computational complexity of lattice problems.