log in  |  register  |  feedback?  |  help  |  web accessibility
Non-Interactive Zero Knowledge (NIZKs) from Learning With Errors (LWE)
Daniel Apon - National Institute of Standards and Technology
Friday, March 8, 2019, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

For over a decade, a major open question in the theory of lattice-based cryptography has been to construct non-interactive zero-knowledge proofs from standard assumptions, i.e. Learning With Errors. Indeed, about 5 years ago, this problem was inscribed on the wall at the Simons Institute for the Theory of Computation in Berkeley, CA with a $100 bounty. (Big money!)

In this talk, I will survey the detailed work over the past year or so, by Canetti et al (1-- https://eprint.iacr.org/2018/131.pdf and 2--  https://eprint.iacr.org/2018/1248.pdf) and by Peikert/ Shiehian (https://eprint.iacr.org/2019/158.pdf), which finally resolves this question.

The main result will be the existence of quantum-secure NIZKs from standard cryptographic hardness assumptions.

Pre-requisites: A basic understanding on LWE will be assumed (e.g. https://cims.nyu.edu/~regev/papers/qcrypto.pdf and https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf), and a basic understanding of NIZK proof systems will be helpful, but nothing else is required.

This talk is organized by Aria