Scalable zero knowledge via cycles of elliptic curves. Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, {it succinctness}, requiring the proof to be very short and easy to verify. Such proof systems are known as {it zero-knowledge succinct non-interactive arguments of knowledge} (zk-SNARKs), and are desired when communication is expensive, or the verifier is computationally weak. Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statement’s decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires “writing down” all intermediate values of the entire computation, and then conducting global operations such as FFTs. The bootstrapping technique of Bitansky et al. (STOC ’13), following Valiant (TCC ’08), offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof system’s own verifier (and correctness of the program’s latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost. Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systems’ field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on today’s hardware, for any program running time. It takes constant time to generate the keys that support {it all} computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computation’s time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of “verified instructions per second”.

References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Chiesa, Alessandro; Chua, Lynn; Weidner, Matthew: On cycles of pairing-friendly elliptic curves (2019)
  2. Ben-Sasson, Eli; Bentov, Iddo; Chiesa, Alessandro; Gabizon, Ariel; Genkin, Daniel; Hamilis, Matan; Pergament, Evgenya; Riabzev, Michael; Silberstein, Mark; Tromer, Eran; Virza, Madars: Computational integrity with a public random string from quasi-linear PCPs (2017)
  3. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2017)
  4. Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Goldwasser, Shafi; Lin, Huijia; Rubinstein, Aviad; Tromer, Eran: The hunting of the SNARK (2017)
  5. López-Alt, Adriana; Tromer, Eran; Vaikuntanathan, Vinod: Multikey fully homomorphic encryption and applications (2017)
  6. Mohassel, Payman; Rosulek, Mike; Scafuro, Alessandra: Sublinear zero-knowledge arguments for RAM programs (2017)
  7. Bellare, Mihir; Fuchsbauer, Georg; Scafuro, Alessandra: NIZKs with an untrusted CRS: security in the face of parameter subversion (2016)
  8. Fiore, Dario; Nitulescu, Anca: On the (in)security of SNARKs in the presence of oracles (2016)
  9. Ishai, Yuval; Weiss, Mor; Yang, Guang: Making the best of a leaky situation: zero-knowledge PCPs from leakage-resilient circuits (2016)
  10. Okano, Keiji: Note on families of pairing-friendly elliptic curves with small embedding degree (2016)
  11. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2014)