Folding Schemes with  Privacy Preserving Selective Verification

Joan Boyar; Simon Erfurth

doi:10.62056/a0iv4fe-3

Folding Schemes with Privacy Preserving Selective Verification

Authors

Joan Boyar, Simon Erfurth

Joan Boyar

University of Southern Denmark, Odense, Denmark
joan at imada dot sdu dot dk

Simon Erfurth

University of Southern Denmark, Odense, Denmark
simon at serfurth dot dk

Keywords: folding schemes SNARKs delegation of computation

Abstract

Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.

References

[BBB⁺18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In IEEE Symposium on Security and Privacy - SP 2018, pages 315–334. 2018. IEEE Computer Society. DOI: 10.1109/SP.2018.00020

Google Scholar ePrint

[BC23]

Benedikt Bünz and Binyi Chen. Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols. In Advances in Cryptology - ASIACRYPT 2023, volume 14439 of Lecture Notes in Computer Science, pages 77–110. 2023. Springer. DOI: 10.1007/978-981-99-8724-5_3

Google Scholar ePrint

[BC24]

Dan Boneh and Binyi Chen. LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems. In The Science of Blockchain Conference - SBC '24. 2024.

Google Scholar ePrint

[BCC⁺16]

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Advances in Cryptology - EUROCRYPT 2016, volume 9666 of Lecture Notes in Computer Science, pages 327–357. 2016. Springer. DOI: 10.1007/978-3-662-49896-5_12

Google Scholar ePrint

[BCL⁺21]

Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, and Nicholas Spooner. Proof-Carrying Data Without Succinct Arguments. In Advances in Cryptology - CRYPTO 2021, volume 12825 of Lecture Notes in Computer Science, pages 681–710. 2021. Springer. DOI: 10.1007/978-3-030-84242-0_24

Google Scholar ePrint

[BCMS20]

Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, and Nicholas Spooner. Recursive Proof Composition from Accumulation Schemes. In Theory of Cryptography - TCC 2020, volume 12551 of Lecture Notes in Computer Science, pages 1–18. 2020. Springer. DOI: 10.1007/978-3-030-64378-2_1

Google Scholar ePrint

[BCR⁺19]

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Advances in Cryptology - EUROCRYPT 2019, volume 11476 of Lecture Notes in Computer Science, pages 103–128. 2019. Springer. DOI: 10.1007/978-3-030-17653-2_4

Google Scholar ePrint

[BDFG21]

Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments. In Advances in Cryptology - CRYPTO 2021, volume 12825 of Lecture Notes in Computer Science, pages 649–680. 2021. Springer. DOI: 10.1007/978-3-030-84242-0_23

Google Scholar ePrint

[BE24]

Joan Boyar and Simon Erfurth. Folding Schemes with Privacy Preserving Selective Verification. IACR Cryptol. ePrint Arch., 2024.

Google Scholar ePrint

[BELN23]

Joan Boyar, Simon Erfurth, Kim S. Larsen, and Ruben Niederhagen. Quotable Signatures for Authenticating Shared Quotes. In Progress in Cryptology - LATINCRYPT 2023, volume 14168 of Lecture Notes in Computer Science, pages 273–292. 2023. Springer. DOI: 10.1007/978-3-031-44469-2_14

Google Scholar ePrint

[BGH19]

Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive Proof Composition without a Trusted Setup. IACR Cryptol. ePrint Arch., 2019.

Google Scholar ePrint

[BKP20]

Ward Beullens, Shuichi Katsumata, and Federico Pintore. Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices. In Advances in Cryptology - ASIACRYPT 2020, volume 12492 of Lecture Notes in Computer Science, pages 464–492. 2020. Springer. DOI: 10.1007/978-3-030-64834-3_16

Google Scholar ePrint

[C2P]

C2PA. Coalition for Content Provenance and Authenticity (C2PA). https://c2pa.org/.

Google Scholar ePrint

[CF13]

Dario Catalano and Dario Fiore. Vector Commitments and Their Applications. In Public-Key Cryptography - PKC 2013, volume 7778 of Lecture Notes in Computer Science, pages 55–72. 2013. Springer. DOI: 10.1007/978-3-642-36362-7_5

Google Scholar ePrint

[CNR⁺22]

Matteo Campanelli, Anca Nitulescu, Carla Ràfols, Alexandros Zacharakis, and Arantxa Zapico. Linear-Map Vector Commitments and Their Practical Applications. In Advances in Cryptology - ASIACRYPT 2022, volume 13794 of Lecture Notes in Computer Science, pages 189–219. 2022. Springer. DOI: 10.1007/978-3-031-22972-5_7

Google Scholar ePrint

[DCB24]

Trisha Datta, Binyi Chen, and Dan Boneh. VerITAS: Verifying Image Transformations at Scale. 2024.

Google Scholar ePrint

[DEH24]

Stefan Dziembowski, Shahriar Ebrahimi, and Parisa Hassanizadeh. VIMz: Verifiable Image Manipulation using Folding-based zkSNARKs. IACR Cryptol. ePrint Arch., 2024.

Google Scholar ePrint

[Erf24]

Simon Erfurth. Digital Signatures for Authenticating Compressed JPEG Images. In Security-Centric Strategies for Combating Information Disorder - SCID 2024, pages 4. 2024. ACM. DOI: 10.1145/3660512.3665522

Google Scholar ePrint

[FS86]

Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology - CRYPTO '86, volume 263 of Lecture Notes in Computer Science, pages 186–194. 1986. Springer. DOI: 10.1007/3-540-47721-7_12

Google Scholar ePrint

[GGPR13]

Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. In Advances in Cryptology - EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 626–645. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_37

Google Scholar ePrint

[Gro16]

Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Advances in Cryptology - EUROCRYPT 2016, volume 9666 of Lecture Notes in Computer Science, pages 305–326. 2016. Springer. DOI: 10.1007/978-3-662-49896-5_11

Google Scholar ePrint

[GWC19]

Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptol. ePrint Arch., 2019.

Google Scholar ePrint

[JWL11]

Rob Johnson, Leif Walsh, and Michael Lamb. Homomorphic Signatures for Digital Photographs. In Financial Cryptography and Data Security - FC 2011, volume 7035 of LNCS, pages 141–157. 2011. Springer. DOI: 10.1007/978-3-642-27576-0_12

Google Scholar ePrint

[Kot24]

Abhiram Kothapalli. A Theory of Composition for Proofs of Knowledge. PhD thesis, Carnegie Mellon University, 2024.

Google Scholar ePrint

[KP23]

Abhiram Kothapalli and Bryan Parno. Algebraic Reductions of Knowledge. In Advances in Cryptology - CRYPTO 2023, volume 14084 of Lecture Notes in Computer Science, pages 669–701. 2023. Springer. DOI: 10.1007/978-3-031-38551-3_21

Google Scholar ePrint

[KS22]

Abhiram Kothapalli and Srinath T. V. Setty. SuperNova: Proving universal machine executions without universal circuits. IACR Cryptol. ePrint Arch., 2022.

Google Scholar ePrint

[KS24]

Abhiram Kothapalli and Srinath T. V. Setty. HyperNova: Recursive Arguments for Customizable Constraint Systems. In Advances in Cryptology - CRYPTO 2024, volume 14929 of Lecture Notes in Computer Science, pages 345–379. 2024. Springer. DOI: 10.1007/978-3-031-68403-6_11

Google Scholar ePrint

[KST22]

Abhiram Kothapalli, Srinath T. V. Setty, and Ioanna Tzialla. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. In Advances in Cryptology - CRYPTO 2022, volume 13510 of Lecture Notes in Computer Science, pages 359–388. 2022. Springer. DOI: 10.1007/978-3-031-15985-5_13

Google Scholar ePrint

[KZG10]

Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Advances in Cryptology - ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 177–194. 2010. Springer. DOI: 10.1007/978-3-642-17373-8_11

Google Scholar ePrint

[Mer80]

Ralph C. Merkle. Protocols for Public Key Cryptosystems. In IEEE Symposium on Security and Privacy - S&P 1980, pages 122–134. 1980. IEEE Computer Society. DOI: 10.1109/SP.1980.10006

Google Scholar ePrint

[Mer89]

Ralph C. Merkle. A Certified Digital Signature. In Advances in Cryptology - CRYPTO '89, volume 435, pages 218–238. 1989. Springer. DOI: 10.1007/0-387-34805-0_21

Google Scholar ePrint

[MVVZ25]

Pierpaolo Della Monica, Ivan Visconti, Andrea Vitaletti, and Marco Zecchini. Trust Nobody: Privacy-Preserving Proofs for Edited Photos with Your Laptop. In IEEE Symposium on Security and Privacy - S&P 2025. 2025. IEEE Computer Society. DOI: 10.1109/SP61157.2025.00014

Google Scholar ePrint

[NDC⁺24]

Wilson D. Nguyen, Trisha Datta, Binyi Chen, Nirvan Tyagi, and Dan Boneh. Mangrove: A Scalable Framework for Folding-Based SNARKs. In Advances in Cryptology - CRYPTO 2024, volume 14929 of Lecture Notes in Computer Science, pages 308–344. 2024. Springer. DOI: 10.1007/978-3-031-68403-6_10

Google Scholar ePrint

[NT16]

Assa Naveh and Eran Tromer. PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations. In IEEE Symposium on Security and Privacy - S&P 2016, pages 255–271. 2016. IEEE Computer Society. DOI: 10.1109/SP.2016.23

Google Scholar ePrint

[Ped91]

Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Advances in Cryptology - CRYPTO '91, volume 576 of Lecture Notes in Computer Science, pages 129–140. 1991. Springer. DOI: 10.1007/3-540-46766-1_9

Google Scholar ePrint

[RZ23]

Carla Ràfols and Alexandros Zacharakis. Folding Schemes with Selective Verification. In Progress in Cryptology - LATINCRYPT 2023, volume 14168 of Lecture Notes in Computer Science, pages 229–248. 2023. Springer. DOI: 10.1007/978-3-031-44469-2_12

Google Scholar ePrint

[SBV⁺13]

Srinath T. V. Setty, Benjamin Braun, Victor Vu, Andrew J. Blumberg, Bryan Parno, and Michael Walfish. Resolving the conflict between generality and plausibility in verified computation. In EuroSys '13, pages 71–84. 2013. ACM. DOI: 10.1145/2465351.2465359

Google Scholar ePrint

[SF90]

Laura A. Sanchis and Mark A. Fulk. On the Efficient Generation of Language Instances. SIAM Journal on Computing, 19(2):281–296, 1990. DOI: 10.1137/0219019

Google Scholar ePrint

[STW23]

Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. Customizable constraint systems for succinct arguments. IACR Cryptol. ePrint Arch., 2023.

Google Scholar ePrint

[Val08]

Paul Valiant. Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. In Theory of Cryptography - TCC 2008, volume 4948 of Lecture Notes in Computer Science, pages 1–18. 2008. Springer. DOI: 10.1007/978-3-540-78524-8_1

Google Scholar ePrint

[YLF⁺22]

Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller. hbACSS: How to Robustly Share Many Secrets. In Network and Distributed System Security Symposium - NDSS 2022. 2022. The Internet Society.

Google Scholar ePrint

[ZSL04]

Bin Benjamin Zhu, Mitchell D. Swanson, and Shipeng Li. Encryption and authentication for scalable multimedia: Current state of the art and challenges. Internet Multimedia Management Systems V, 5601:157–170, 2004. DOI: 10.1117/12.571869

Google Scholar ePrint

[ZXH⁺22]

Jiaheng Zhang, Tiancheng Xie, Thang Hoang, Elaine Shi, and Yupeng Zhang. Polynomial Commitment with a One-to-Many Prover and Applications. In USENIX Security 2022, pages 2965–2982. 2022. USENIX Association.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0iv4fe-3

History

Submitted: 2024-09-30
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Joan Boyar and Simon Erfurth, Folding Schemes with Privacy Preserving Selective Verification. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0iv4fe-3.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-12,
    author = "Boyar, Joan and Erfurth, Simon",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Folding Schemes with  Privacy Preserving Selective Verification",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/a0iv4fe-3"
}

TY - JOUR
AU - Boyar, Joan
AU - Erfurth, Simon
PY - 2025
TI - Folding Schemes with Privacy Preserving Selective Verification
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 4
DO - 10.62056/a0iv4fe-3
UR - https://doi.org/10.62056/a0iv4fe-3
AB - <p> Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement. </p>
ER -

Joan Boyar and Simon Erfurth, Folding Schemes with Privacy Preserving Selective Verification. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0iv4fe-3.