Polaris: Transparent Succinct Zero-Knowledge Arguments for R1CS with Efficient Verifier

[1] A pure-Rust implementation of group operations on Ristretto and curve25519. https://github.com/dalek-cryptography/curve25519-dalek. Search in Google Scholar

[2] libiop: a C++ library for IOP-based zkSNARKs. https://github.com/scipr-lab/libiop. Search in Google Scholar

[3] libsnark: a C++ library for zkSNARK proofs. https://github.com/scipr-lab/libsnark. Search in Google Scholar

[4] Marlin. https://github.com/arkworks-rs/marlin. Search in Google Scholar

[5] Spartan: High-speed zkSNARKs without trusted setup. https://github.com/microsoft/spartan. Search in Google Scholar

[6] Virgo ZK reference implementation. https://github.com/sunblaze-ucb/virgo. Search in Google Scholar

[7] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. CCS 2017: 2087–2104.10.1145/3133956.3134104 Search in Google Scholar

[8] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast reed-solomon interactive oracle proofs of proximity. ICALP 2018: 14:1–14:17. Search in Google Scholar

[9] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive, 2018: 46. Search in Google Scholar

[10] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for Reed-Solomon codes. FOCS 2020: 900–909.10.1109/FOCS46700.2020.00088 Search in Google Scholar

[11] Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Zero knowledge protocols from succinct constraint detection. TCC 2017: 172–206.10.1007/978-3-319-70503-3_6 Search in Google Scholar

[12] Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, and Madars Virza. Quasi-linear size zero knowledge from linear-algebraic PCPs. TCC 2016-A: 33–64.10.1007/978-3-662-49099-0_2 Search in Google Scholar

[13] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. IEEE Symposium on Security and Privacy 2014: 459–474.10.1109/SP.2014.36 Search in Google Scholar

[14] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. ITCS 2013: 401–414.10.1145/2422436.2422481 Search in Google Scholar

[15] Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, and Nicholas Spooner. Linear-Size Constant-Query IOPs for Delegating Computation. TCC (2) 2019: 494–521.10.1007/978-3-030-36033-7_19 Search in Google Scholar

[16] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. EURO-CRYPT (1) 2019: 103–128.10.1007/978-3-030-17653-2_4 Search in Google Scholar

[17] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. TCC (2) 2016: 31–60.10.1007/978-3-662-53644-5_2 Search in Google Scholar

[18] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct non-interactive zero knowledge for a von neumann architecture. USENIX Security Symposium 2014: 781–796. Search in Google Scholar

[19] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling outside the box improves soundness. ITCS 2020: 5:1–5:32. Search in Google Scholar

[20] Rishabh Bhadauria, Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Tiancheng Xie, and Yupeng Zhang. Ligero++: A new optimized sublinear IOP. CCS 2020: 2025–2038.10.1145/3372297.3417893 Search in Google Scholar

[21] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. EUROCRYPT (2) 2016: 327–357.10.1007/978-3-662-49896-5_12 Search in Google Scholar

[22] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short proofs for confidential transactions and more. IEEE Symposium on Security and Privacy 2018: 315–334.10.1109/SP.2018.00020 Search in Google Scholar

[23] Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent snarks from DARK compilers. EUROCRYPT (1) 2020: 677–706.10.1007/978-3-030-45721-1_24 Search in Google Scholar

[24] Nigel P. Byott and Robin J. Chapman. Power sums over finite subspaces of a field. Finite Fields and Their Applications, 5(3): 254–265, 1999.10.1006/ffta.1999.0243 Search in Google Scholar

[25] Benedikt Bünz, Mary Maller, Pratyush Mishra, and Noah Vesely. Proofs for inner pairing products and applications. IACR Cryptology ePrint Archive, 2019: 1177. Search in Google Scholar

[26] Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, and Luca Nizzardo. Zero-knowledge contingent payments revisited: Attacks and payments for services. CCS 2017: 229–243.10.1145/3133956.3134060 Search in Google Scholar

[27] Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. A zero knowledge sumcheck and its applications. IACR Cryptology ePrint Archive, 2017: 305. Search in Google Scholar

[28] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. EUROCRYPT (1) 2020: 738–768.10.1007/978-3-030-45721-1_26 Search in Google Scholar

[29] Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. EUROCRYPT (1) 2020: 769–793.10.1007/978-3-030-45721-1_27 Search in Google Scholar

[30] Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Practical verified computation with streaming interactive proofs. ITCS 2012: 90–112.10.1145/2090236.2090245 Search in Google Scholar

[31] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. CRYPTO 1986: 186–194.10.1007/3-540-47721-7_12 Search in Google Scholar

[32] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without PCPs. EUROCRYPT 2013: 626–645.10.1007/978-3-642-38348-9_37 Search in Google Scholar

[33] Craig Gentry and Daniel Wichs. Separating succinct noninteractive arguments from all falsifiable assumptions. STOC 2011: 99–108.10.1145/1993636.1993651 Search in Google Scholar

[34] Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. Search in Google Scholar

[35] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Roth-blum. Delegating computation: Interactive proofs for muggles. Journal of the ACM, 62(4): 27:1–27:64, 2015. Search in Google Scholar

[36] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1): 186–208, 1989.10.1137/0218012 Search in Google Scholar

[37] Jens Groth. On the size of pairing-based non-interactive arguments. EUROCRYPT (2) 2016: 305–326.10.1007/978-3-662-49896-5_11 Search in Google Scholar

[38] Jens Groth and Yuval Ishai. Sub-linear zero-knowledge argument for correctness of a shuffle. EUROCRYPT 2008: 379–396.10.1007/978-3-540-78967-3_22 Search in Google Scholar

[39] Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash Protocol Specification, March 2020. Search in Google Scholar

[40] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. ASIACRYPT 2010: 177–194.10.1007/978-3-642-17373-8_11 Search in Google Scholar

[41] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). STOC 1992: 723–732.10.1145/129712.129782 Search in Google Scholar

[42] Jonathan Lee. Dory: Efficient, transparent arguments for generalised inner products and polynomial commitments. IACR Cryptology ePrint Archive, 2020: 1274. Search in Google Scholar

[43] Rudolf Lidl and Harald Niederreiter. Finite Fields. Second Edition. Cambridge University Press, 1997.10.1017/CBO9780511525926 Search in Google Scholar

[44] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. FOCS (1) 1990: 2–10. Search in Google Scholar

[45] Ralph C. Merkle. A certified digital signature. CRYPTO 1989: 218–238.10.1007/0-387-34805-0_21 Search in Google Scholar

[46] Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4): 1253–1298, 2000.10.1137/S0097539795284959 Search in Google Scholar

[47] NIST. Common vulnerabilities and exposures. https://nvd.nist.gov/vuln/detail/cve-2019-7167, March 2019. Search in Google Scholar

[48] Srinath Setty. Spartan: Efficient and general-purpose zk-SNARKs without trusted setup. CRYPTO (3) 2020: 704–737.10.1007/978-3-030-56877-1_25 Search in Google Scholar

[49] Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4): 869–877, 1992.10.1145/146585.146609 Search in Google Scholar

[50] Justin Thaler. Time-optimal interactive proofs for circuit evaluation. CRYPTO (2) 2013: 71–89.10.1007/978-3-642-40084-1_5 Search in Google Scholar

[51] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. TCC 2008: 1–18.10.1007/978-3-540-78524-8_1 Search in Google Scholar

[52] Alexander Vlasov and Konstantin Panarin. Transparent polynomial commitment scheme with polylogarithmic communication complexity. IACR Cryptology ePrint Archive, 2019: 1020. Search in Google Scholar

[53] Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, and Thomas Wies. Full accounting for verifiable outsourcing. CCS 2017: 2071–2086.10.1145/3133956.3133984 Search in Google Scholar

[54] Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. IEEE Symposium on Security and Privacy 2018: 926–943.10.1109/SP.2018.00060 Search in Google Scholar

[55] Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Char-alampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. CRYPTO (3) 2019: 733–764.10.1007/978-3-030-26954-8_24 Search in Google Scholar

[56] Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. Transparent polynomial delegation and its applications to zero knowledge proof. IEEE Symposium on Security and Privacy 2020: 859–876.10.1109/SP40000.2020.00052 Search in Google Scholar

• Understanding Privacy-Related Advice on Stack Overflow

• Revisiting Identification Issues in GDPR ‘Right Of Access’ Policies: A Technical and Longitudinal Analysis

• Employees’ privacy perceptions: exploring the dimensionality and antecedents of personal data sensitivity and willingness to disclose

• Visualizing Privacy-Utility Trade-Offs in Differentially Private Data Releases

• Analyzing the Feasibility and Generalizability of Fingerprinting Internet of Things Devices

• CoverDrop: Blowing the Whistle Through A News App

• Building a Privacy-Preserving Smart Camera System

• FP-Radar: Longitudinal Measurement and Early Detection of Browser Fingerprinting

• Are iPhones Really Better for Privacy? A Comparative Study of iOS and Android Apps

• How to prove any NP statement jointly? Efficient Distributed-prover Zero-Knowledge Protocols

• Editors’ Introduction

• PUBA: Privacy-Preserving User-Data Bookkeeping and Analytics

• Who Knows I Like Jelly Beans? An Investigation Into Search Privacy

• SoK: Plausibly Deniable Storage

• d3p - A Python Package for Differentially-Private Probabilistic Programming

• Updatable Private Set Intersection

• Knowledge Cross-Distillation for Membership Privacy

• RegulaTor: A Straightforward Website Fingerprinting Defense

• Privacy-Preserving Positioning in Wi-Fi Fine Timing Measurement

• Efficient Set Membership Proofs using MPC-in-the-Head

• Checking Websites’ GDPR Consent Compliance for Marketing Emails

• Comprehensive Analysis of Privacy Leakage in Vertical Federated Learning During Prediction

• Understanding Utility and Privacy of Demographic Data in Education Technology by Causal Analysis and Adversarial-Censoring

• User-Level Label Leakage from Gradients in Federated Learning

• Privacy-preserving training of tree ensembles over continuous data

• Differentially Private Simple Linear Regression

• Increasing Adoption of Tor Browser Using Informational and Planning Nudges