Model circuits with algebraic tools

Rentrée 2016-2017 :
Liste des projets supervisés

Déscription :
Model circuits with algebraic tools

The class of problems NP-hard is already a myth in theoretical computer science. First natural NP problem to solve is circuit satisfiability (C-SAT). To verify C-SAT we use a smart representation of it as a set of algebraic constraints. An ingenious way of "translating" circuits is the Square Span Program [2]. This remodels any circuit into a polynomial division problem. The project purpose is to understand the existing techniques, then to search for new simpler ways of representing circuits.

Bibliographie :
[1] In Models of Computation: Exploring the Power of Computing - John Savage
[2] Square Span Programs with Applications to Succinct NIZK Arguments - George Danezis, Cédric Fournet, Jens Groth, and Markulf Kohlweiss - AsiaCrypt 2014
[3] Quadratic Span Programs and Succinct NIZKs without PCPs - Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova - EuroCrypt 2013
[4] Pinocchio: Nearly Practical Verifiable Computation - Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova

Progression :
Thème 1 : Square Span Programs [2]
Thème 2 : Quadratic Arithmetic Programs (slides by Bryan Parno )
Thème 3 : Back to Affine Map Constraints

“Any scientist who cannot explain to an eight-year-old what he is doing is a charlatan.”
Kurt Vonnegut