Succinct arguments from hashes and lattices
Event details
| Date | 16.06.2023 |
| Hour | 15:00 › 17:00 |
| Speaker | Giacomo Fenzi |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Carmela Troncoso
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Mika Göös
Abstract
Succinct non-interactive arguments of knowledge (SNARKs) are protocols to construct short proofs of NP-statements. In this talk, we outline the classical approach towards obtaining a SNARK from probabilistically checkable proofs (PCPs). First, we describe the sumcheck protocol, and construct a PCP for NP from it. Next, we use lightweight cryptography to obtain an interactive argument using Kilian's techniques. Finally, we describe Micali's approach to obtain non-interactivity in the random oracle model. We conclude by describing a few concluded research projects and future directions.
Background papers
1. Computationally Sound Proofs by Silvio Micali (https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf)
2. A note on efficient zero-knowledge proofs and arguments by Joe Killian (https://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf)
3. Algebraic Methods for Interactive Proof Systems by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan (https://dl.acm.org/doi/pdf/10.1145/146585.146605)
Exam president: Prof. Carmela Troncoso
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Mika Göös
Abstract
Succinct non-interactive arguments of knowledge (SNARKs) are protocols to construct short proofs of NP-statements. In this talk, we outline the classical approach towards obtaining a SNARK from probabilistically checkable proofs (PCPs). First, we describe the sumcheck protocol, and construct a PCP for NP from it. Next, we use lightweight cryptography to obtain an interactive argument using Kilian's techniques. Finally, we describe Micali's approach to obtain non-interactivity in the random oracle model. We conclude by describing a few concluded research projects and future directions.
Background papers
1. Computationally Sound Proofs by Silvio Micali (https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf)
2. A note on efficient zero-knowledge proofs and arguments by Joe Killian (https://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf)
3. Algebraic Methods for Interactive Proof Systems by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan (https://dl.acm.org/doi/pdf/10.1145/146585.146605)
Practical information
- General public
- Free