Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are useful mathematical tools to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.
This meeting — on Friday, 29 April 2022 — is aimed at connecting the two communities with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.
The advent of fully-functioning quantum computers would drastically change our used cryptographic protocols because classically hard problems might be efficiently solvable on a quantum computer. A problem that is believed to be hard even for a quantum computer is the shortest vector problem. I will discuss formulating the shortest vector problem as an algorithm that can be executed on quantum mechanical hardware. Since currently available hardware is limited in terms of qubit number and quality of logical operations, I will focus on approaches that might perform well also with limited hardware.
I will discuss how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we’ll focus on mapping the problem to that of finding the ground state of a suitable Hamiltonian operator:
Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with ≈ 103 noisy qubits such instances can be tackled.
Everyone is welcome.