research-article

Open access

Modular Sumcheck Proofs with Applications to Machine Learning and Image Processing

Authors:

Maria Isabel González Vasco,

Damien Robissout,

Claudio SorienteAuthors Info & Claims

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

Pages 1437 - 1451

https://doi.org/10.1145/3576915.3623160

Published: 21 November 2023 Publication History

Abstract

Cryptographic proof systems provide integrity, fairness, and privacy in applications that outsource data processing tasks. However, general-purpose proof systems do not scale well to large inputs. At the same time, ad-hoc solutions for concrete applications - e.g., machine learning or image processing - are more efficient but lack modularity, hence they are hard to extend or to compose with other tools of a data-processing pipeline.

In this paper, we combine the performance of tailored solutions with the versatility of general-purpose proof systems. We do so by introducing a modular framework for verifiable computation of sequential operations. The main tool of our framework is a new information-theoretic primitive called Verifiable Evaluation Scheme on Fingerprinted Data (VE) that captures the properties of diverse sumcheck-based interactive proofs, including the well-established GKR protocol. Thus, we show how to compose VEs for specific functions to obtain verifiability of a data-processing pipeline.

We propose a novel VE for convolution operations that can handle multiple input-output channels and batching, and we use it in our framework to build proofs for (convolutional) neural networks and image processing. We realize a prototype implementation of our proof systems, and show that we achieve up to 5x faster proving time and 10x shorter proofs compared to the state-of-the-art, in addition to asymptotic improvements.

References

[1]

Ramy E. Ali, Jinhyun So, and Amir Salman Avestimehr. 2020. On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks. CoRR, Vol. abs/2011.05530 (2020). showeprint[arXiv]2011.05530 https://arxiv.org/abs/2011.05530

[2]

arkworks contributors. 2022. textttarkworks zkSNARK ecosystem. https://arkworks.rs

[3]

Matteo Campanelli, Dario Fiore, and Anaïs Querol. 2019. LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, London, UK, 2075--2092. https://doi.org/10.1145/3319535.3339820

Digital Library

[4]

Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. 2023. HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates. In Advances in Cryptology -- EUROCRYPT 2023, Carmit Hazay and Martijn Stam (Eds.). Springer Nature Switzerland, Cham, 499--530.

Digital Library

[5]

Haixia Chen, Xinyi Huang, Jianting Ning, Futai Zhang, and Chao Lin. 2022. VILS: A Verifiable Image Licensing System. IEEE Transactions on Information Forensics and Security, Vol. 17 (2022), 1420--1434. https://doi.org/10.1109/TIFS.2022.3162105

[6]

Shuo Chen, Jung Hee Cheon, Dongwoo Kim, and Daejun Park. 2019. Verifiable Computing for Approximate Computation. Cryptology ePrint Archive, Report 2019/762. https://eprint.iacr.org/2019/762.

[7]

Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and Evan Shelhamer. 2014. cudnn: Efficient primitives for deep learning. arXiv preprint arXiv:1410.0759 (2014).

[8]

Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. 2017. A Zero Knowledge Sumcheck and its Applications. Cryptology ePrint Archive, Report 2017/305. https://eprint.iacr.org/2017/305.

[9]

Alessandro Chiesa and Eran Tromer. 2010. Proof-Carrying Data and Hearsay Arguments from Signature Cards. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5--7, 2010. Proceedings. 310--331.

[10]

Graham Cormode, Michael Mitzenmacher, and Justin Thaler. 2012a. Practical verified computation with streaming interactive proofs. In ITCS 2012, Shafi Goldwasser (Ed.). ACM, Cambridge, MA, USA, 90--112. https://doi.org/10.1145/2090236.2090245

Digital Library

[11]

Graham Cormode, Michael Mitzenmacher, and Justin Thaler. 2012b. Practical Verified Computation with Streaming Interactive Proofs. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Cambridge, Massachusetts) (ITCS '12). Association for Computing Machinery, New York, NY, USA, 90--112. https://doi.org/10.1145/2090236.2090245

Digital Library

[12]

Graham Cormode, Justin Thaler, and Ke Yi. 2011. Verifying Computations with Streaming Interactive Proofs. Proc. VLDB Endow., Vol. 5, 1 (sep 2011), 25--36. https://doi.org/10.14778/2047485.2047488

Digital Library

[13]

Council of European Union. 2000. Council Directive 2000/43/EC of 29 June 2000 implementing the principle of equal treatment between persons irrespective of racial or ethnic origin. newlinehttps://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:32000L0043.

[14]

Council of European Union. 2004. Council Directive 2004/113/EC of 13 December 2004 implementing the principle of equal treatment between men and women in the access to and supply of goods and services. newlinehttps://eur-lex.europa.eu/legal-content/EN/TXT/?uri=CELEX:32004L0113.

[15]

Vincent Dumoulin and Francesco Visin. 2016. A guide to convolution arithmetic for deep learning. arXiv preprint arXiv:1603.07285 (2016).

[16]

Liam Eagen, Dario Fiore, and Ariel Gabizon. 2022. cq: Cached quotients for fast lookups. Cryptology ePrint Archive, Report 2022/1763. https://eprint.iacr.org/2022/1763.

[17]

Federal Office for Information Security Germany (BSI). 2022. Auditing machine learning algorithms - A white paper for public auditors. https://www.hhi.fraunhofer.de/fileadmin/Departments/AI/TechnologiesAndSolutions/2022-05--23-whitepaper-tuev-bsi-hhi-towards-auditable-ai-systems.pdf.

[18]

Boyuan Feng, Lianke Qin, Zhenfei Zhang, Yufei Ding, and Shumo Chu. 2021. ZEN: An Optimizing Compiler for Verifiable, Zero-Knowledge Neural Network Inferences. Cryptology ePrint Archive, Report 2021/087. https://ia.cr/2021/087.

[19]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2008. Delegating computation: interactive proofs for muggles. In 40th ACM STOC, Richard E. Ladner and Cynthia Dwork (Eds.). ACM Press, Victoria, BC, Canada, 113--122. https://doi.org/10.1145/1374376.1374396

Digital Library

[20]

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In 17th ACM STOC. ACM Press, Providence, RI, USA, 291--304. https://doi.org/10.1145/22145.22178

Digital Library

[21]

Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. 2021. Brakedown: Linear-time and post-quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021/1043. https://ia.cr/2021/1043.

[22]

Justin Holmgren and Ron Rothblum. 2018. Delegating Computations with (Almost) Minimal Time and Space Overhead. In 59th FOCS, Mikkel Thorup (Ed.). IEEE Computer Society Press, Paris, France, 124--135. https://doi.org/10.1109/FOCS.2018.00021

[23]

Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. 2018. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition. 2704--2713.

[24]

Daniel Kang, Tatsunori Hashimoto, Ion Stoica, and Yi Sun. 2022. ZK-IMG: Attested Images via Zero-Knowledge Proofs to Fight Disinformation. arxiv: 2211.04775 [cs.CR]

[25]

Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. 2010. Constant-Size Commitments to Polynomials and Their Applications. In ASIACRYPT 2010 (LNCS, Vol. 6477), Masayuki Abe (Ed.). Springer, Heidelberg, Germany, Singapore, 177--194. https://doi.org/10.1007/978--3--642--17373--8_11

[26]

Seunghwa Lee, Hankyung Ko, Jihye Kim, and Hyunok Oh. 2020. vCNN: Verifiable Convolutional Neural Network. Cryptology ePrint Archive, Report 2020/584. https://eprint.iacr.org/2020/584.

[27]

Tianyi Liu, Xiang Xie, and Yupeng Zhang. 2021a. zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, Virtual Event, Republic of Korea, 2968--2985. https://doi.org/10.1145/3460120.3485379

Digital Library

[28]

Tianyi Liu, Xiang Xie, and Yupeng Zhang. 2021b. zkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2968--2985.

Digital Library

[29]

Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. 1992. Algebraic Methods for Interactive Proof Systems. J. ACM, Vol. 39, 4 (oct 1992), 859--868. https://doi.org/10.1145/146585.146605

Digital Library

[30]

Assa Naveh and Eran Tromer. 2016. PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations. In 2016 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Jose, CA, USA, 255--271. https://doi.org/10.1109/SP.2016.23

[31]

Jim Posen and Assimakis A. Kattis. 2022. Caulk: Table-independent lookup arguments. Cryptology ePrint Archive, Report 2022/957. https://eprint.iacr.org/2022/957.

[32]

scipr-lab. 2017. libsnark: a C library for zkSNARK proofs. https://github.com/scipr-lab/libsnark.

[33]

Srinath Setty. 2020. Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup. In CRYPTO 2020, Part III (LNCS, Vol. 12172), Daniele Micciancio and Thomas Ristenpart (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 704--737. https://doi.org/10.1007/978--3-030--56877--1_25

Digital Library

[34]

Eduardo Soria-Vazquez. 2022. Doubly Efficient Interactive Proofs over Infinite and Non-commutative Rings. In TCC 2022, Part I (LNCS ). Springer, Heidelberg, Germany, 497--525. https://doi.org/10.1007/978--3-031--22318--1_18

Digital Library

[35]

Justin Thaler. 2013. Time-Optimal Interactive Proofs for Circuit Evaluation. In CRYPTO 2013, Part II (LNCS, Vol. 8043), Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 71--89. https://doi.org/10.1007/978--3--642--40084--1_5

[36]

the Supreme Audit Institutions of Finland, Germany, the Netherlands, Norway and the UK. 2020. Towards Auditable AI Systems - From Principles to Practice. https://www.auditingalgorithms.net/.

[37]

Stanford University. [n.,d.]. CS231: Convolutional Neural Networks for Pattern Recognition. https://cs231n.github.io/convolutional-networks/#convert.

[38]

Victor Vu, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. 2013. A Hybrid Architecture for Interactive Verifiable Computation. In 2013 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Berkeley, CA, USA, 223--237. https://doi.org/10.1109/SP.2013.48

Digital Library

[39]

Riad S. Wahby, Ye Ji, Andrew J. Blumberg, abhi shelat, Justin Thaler, Michael Walfish, and Thomas Wies. 2017. Full Accounting for Verifiable Outsourcing. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, Dallas, TX, USA, 2071--2086. https://doi.org/10.1145/3133956.3133984

Digital Library

[40]

Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. 2018. Doubly-Efficient zkSNARKs Without Trusted Setup. In 2018 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 926--943. https://doi.org/10.1109/SP.2018.00060

[41]

Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. 2019. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. In CRYPTO 2019, Part III (LNCS, Vol. 11694), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 733--764. https://doi.org/10.1007/978--3-030--26954--8_24

[42]

Tiancheng Xie, Yupeng Zhang, and Dawn Song. 2022. Orion: Zero Knowledge Proof with Linear Prover Time. In CRYPTO 2022, Part IV (LNCS, Vol. 13510), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 299--328. https://doi.org/10.1007/978--3-031--15985--5_11

[43]

Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin. 2022a. Caulk: Lookup Arguments in Sublinear Time. In ACM CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, Los Angeles, CA, USA, 3121--3134. https://doi.org/10.1145/3548606.3560646

Digital Library

[44]

Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, and Carla Ràfols. 2022b. Baloo: Nearly Optimal Lookup Arguments. Cryptology ePrint Archive, Report 2022/1565. https://eprint.iacr.org/2022/1565.

[45]

zcash. 2022. halo2. https://zcash.github.io/halo2/.

[46]

Jiaheng Zhang, Zhiyong Fang, Yupeng Zhang, and Dawn Song. 2020a. Zero Knowledge Proofs for Decision Tree Predictions and Accuracy. In ACM CCS 2020, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). ACM Press, Virtual Event, USA, 2039--2053. https://doi.org/10.1145/3372297.3417278

Digital Library

[47]

Jiaheng Zhang, Tianyi Liu, Weijie Wang, Yinuo Zhang, Dawn Song, Xiang Xie, and Yupeng Zhang. 2021. Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, Virtual Event, Republic of Korea, 159--177. https://doi.org/10.1145/3460120.3484767

Digital Library

[48]

Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. 2020b. Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof. In 2020 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 859--876. https://doi.org/10.1109/SP40000.2020.00052

[49]

Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, and Charalampos Papamanthou. 2017. vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases. In 2017 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Jose, CA, USA, 863--880. https://doi.org/10.1109/SP.2017.43

[50]

Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, and Charalampos Papamanthou. 2018. vRAM: Faster Verifiable RAM with Program-Independent Preprocessing. In 2018 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 908--925. https://doi.org/10.1109/SP.2018.00013

Cited By

Goel A(2025)Multiplication Is Hard: A Review Of Techniques Aiming To Parallelize Matrix Operations To Accelerate Crypto-ML Frameworks SSRN Electronic Journal10.2139/ssrn.5017963Online publication date: 2025
https://doi.org/10.2139/ssrn.5017963
Abbaszadeh KPappas CKatz JPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Zero-Knowledge Proofs of Training for Deep Neural NetworksProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670316(4316-4330)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670316

Index Terms

Modular Sumcheck Proofs with Applications to Machine Learning and Image Processing
1. Security and privacy
  1. Cryptography
    1. Information-theoretic techniques
  2. Security services
    1. Privacy-preserving protocols

Recommendations

Zero-Knowledge Proofs of Training for Deep Neural Networks
CCS '24: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security

A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer ...
Multi-focused Proofs with Different Polarity Assignments

In this work, we will reason on how a given focused proof, where atoms are assigned with some polarity, can be transformed into another focused proof, where the polarity assignment to atoms is changed. This will allow, in principle, transforming a proof ...
Symbolic Malleable Zero-Knowledge Proofs
CSF '15: Proceedings of the 2015 IEEE 28th Computer Security Foundations Symposium

Zero-knowledge (ZK) proofs have become a central building block for a variety of modern security protocols. Modern ZK constructions, such as the Groth-Sahai proof system, offer novel types of cryptographic flexibility: a participant is able to re-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

November 2023

3722 pages

ISBN:9798400700507

DOI:10.1145/3576915

General Chairs:
Weizhi Meng
Technical University of Denmark
,
Christian D. Jensen
Technical University of Denmark
,
Program Chairs:
Cas Cremers
CISPA Helmholtz Center for Information Security
,
Engin Kirda
Khoury College of Computer Sciences

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 November 2023

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '23

Sponsor:

SIGSAC

CCS '23: ACM SIGSAC Conference on Computer and Communications Security

November 26 - 30, 2023

Copenhagen, Denmark

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
654
Total Downloads

Downloads (Last 12 months)528
Downloads (Last 6 weeks)42

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goel A(2025)Multiplication Is Hard: A Review Of Techniques Aiming To Parallelize Matrix Operations To Accelerate Crypto-ML Frameworks SSRN Electronic Journal10.2139/ssrn.5017963Online publication date: 2025
https://doi.org/10.2139/ssrn.5017963
Abbaszadeh KPappas CKatz JPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Zero-Knowledge Proofs of Training for Deep Neural NetworksProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670316(4316-4330)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670316

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten