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