CS Forum: Russell W. F. Lai "Proof systems and Secret Sharing: From Group-land to Lattice-land"

Aika: Maanantai 20. syyskuuta klo 13:00-14:00
Paikka: sali T2 Tietotekniikan talossa

This is a hybrid event, please register if you wish to attend the talk on site.You can also attend the talk via Zoom https://aalto.zoom.us/j/67702668107 (passcode 472317)

Proof systems and Secret Sharing: From Group-land to Lattice-land 

Russell W. F. Lai
Friedrich-Alexander University Erlangen-Nuremberg, Germany

Abstract:

An overwhelming portion of public-key cryptography deployed today is based on the conjectured hardness of computational problems over groups. As these group problems are efficiently solvable using Shor's algorithm on a quantum computer, an ongoing quest in cryptography is to construct cryptographic primitives based on the hardness of computational problems which are believed to be intractable even for quantum computers, such as finding short vectors in lattices. One strategy of doing so is to translate existing group-based constructions into their lattice-based counterparts.

In this talk, I will begin by recalling examples of group-based proof systems and distributed pseudorandom functions. Underneath these constructions are systems of linear equations defined by Vandermonde matrices over prime fields. When translating these constructions to the lattice setting, one encounters the difficulty that the translated Vandermonde systems are now defined over rings and hence not always solvable. I will present recent results towards tackling this very issue.

Host:

Professor Chris Brzuska, Department of Computer Science