SCIPR Lab is a multi-institutional academic collaboration of researchers seeking to bring to practice cryptographic proof systems that provide succinct integrity and privacy.
See our Github webpage for the free (open-source) code that we have published.
DIZK: A Distributed Zero Knowledge Proof System [ePrint]
Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca A. Popa, Ion Stoica
USENIX Security 2018 (27th USENIX Security Symposium)
Zero Knowledge Protocols from Succinct Constraint Detection [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
TCC 2017 (15th Theory of Cryptography Conference)
Interactive Oracle Proofs with Constant Rate and Query Complexity [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
ICALP 2017 (44th International Colloquium on Automata, Languages, and Programming)
Decentralized Anonymous Micropayments [ePrint]
Alessandro Chiesa, Matthew D. Green, Jingcheng Liu, Ian Miers, Peihan Miao, Pratyush Mishra
EUROCRYPT 2017 (36th International Conference on the Theory and Applications of Cryptographic Techniques)
Interactive Oracle Proofs [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner
TCC 2016-B (14th Theory of Cryptography Conference)
PhotoProof: cryptographic image authentication for any set of permissible transformations
Assa Naveh, Eran Tromer
S&P 2016 (37th IEEE Symposium on Security and Privacy)
Quasilinear-Size Zero Knowledge from Linear-Algebraic PCPs [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza
TCC 2016-A (13th Theory of Cryptography Conference)
Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
Eli Ben-Sasson, Alessandro Chiesa, Matthew Green, Eran Tromer, Madars Virza
S&P 2015 (36th IEEE Symposium on Security and Privacy)
Cluster Computing in Zero Knowledge [ePrint]
Alessandro Chiesa, Eran Tromer, Madars Virza
EUROCRYPT 2015 (34th International Conference on the Theory and Applications of Cryptographic Techniques)
Scalable Zero Knowledge via Cycles of Elliptic Curves [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
CRYPTO 2014 (34th IACR International Cryptology Conference)
Zerocash: Decentralized Anonymous Payments from Bitcoin [project website]
Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza
S&P 2014 (35th IEEE Symposium on Security and Privacy)
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
Security 2014 (23rd USENIX Security Symposium)
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza
CRYPTO 2013 (33rd IACR International Cryptology Conference)
On the Concrete Efficiency of Probabilistically-Checkable Proofs [ECCC]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer
STOC 2013 (45th ACM Symposium on the Theory of Computing)
Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems [ePrint]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer
ITCS 2013 (4th Symposium on Innovations in Theoretical Computer Science)
Enforcing Language Semantics Using Proof-Carrying Data [ePrint]
Stephen Chong, Eran Tromer, Jeffrey A. Vaughan
Crypto ePrint 2013/513
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity [ECCC]
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, with an appendix by Henning Stichtenoth
FOCS 2013 (54th Annual Symposium on Foundations of Computer Science)
Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data [ePrint]
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
STOC 2013 (45th ACM Symposium on the Theory of Computing)
Succinct Non-Interactive Arguments via Linear Interactive Proofs [ePrint]
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth
TCC 2013 (10th Theory of Cryptography Conference)
Proof-carrying data: Secure computation on untrusted platforms [pdf] [html]
Alessandro Chiesa, Eran Tromer
The Next Wave, vol. 19 no. 2, NSA, 2012
Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits [ePrint]
Nir Bitansky, Alessandro Chiesa
CRYPTO 2012 (32nd International Cryptology Conference)
From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again [ePrint]
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer
ITCS 2012 (3rd Symposium on Innovations in Theoretical Computer Science)
Proof-Carrying Data and Hearsay Arguments from Signature Cards [html]
Alessandro Chiesa, Eran Tromer
ICS 2010 (1st Symposium on Innovations in Computer Science)
Short PCPs Verifiable in Polylogarithmic Time [html]
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan
CCC 2005 (20th IEEE Conference on Computational Complexity)
Short PCPs with Polylog Query Complexity [pdf]
Eli Ben-Sasson, Madhu Sudan
STOC 2005 (37th ACM Symposium on Theory of Computing)
The TinyRAM architecture is a random-access machine designed to be a convenient tool for expressing the correctness of nondeterministic computations.
Specifically, TinyRAM is a reduced instruction set computer (RISC), with byte- and word-addressable random-access memory. It comes in two variants: one variant follows the Harvard architecture and the other follows the von Neumann architecture.
TinyRAM strikes a balance between two opposing goals:
Having an architecture that is expressive enough to allow for short and fast assembly code obtained by compiling programs written in high-level programming languages; and
Having an architecture that is minimalistic enough to allow for efficient reductions from the correctness of program executions to arithmetic circuit satisfiability (and other algebraic constraint satisfaction problems).
The need to express correctness of nondeterministic computations arises in various applications that utilize proof systems for achieving certain security properties (e.g., zero knowledge).
TinyRAM was introduced in [BCGTV, CRYPTO13] in order to express correctness of nondeterministic computations in the setting of succinct zero-knowledge proofs. More generally, TinyRAM can be used to express computations, e.g., in probabilistically-checkable proofs, and others.