SCIPR Lab is a multi-institutional academic collaboration of researchers seeking to bring to practice cryptographic proof systems that provide succinct integrity and privacy.

Code


See our Github webpage for the free (open-source) code that we have published.

Publications


  • 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)

TinyRAM Specifications


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.

Latest TinyRAM specification: [v2.000]

Older TinyRAM specification: [v0.991]