Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
Authors: 
Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, Muthuramakrishnan VenkitasubramaniamAuthors Info & Claims
Pages 1452 - 1466
Abstract
Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses \mathcalL _1 łor \cdots łor \mathcalL _B. Typically, ZK requires paying the price to handle all B branches. Prior works have shown how to avoid this price in communication, but not in computation.
Our main result, \mathsfBatchman, is asymptotically and concretely efficient VOLE-based ZK for batched disjunctions, i.e. statements containing R repetitions of the same disjunction. This is crucial for, e.g., emulating CPU steps in ZK. Our prover and verifier complexity is only \bigO(RB+R|\C|+B|\C|), where |\C| is the maximum circuit size of the B branches. Prior works' computation scales in RB|\C|. For non-batched disjunctions, we also construct a VOLE-based ZK protocol, \mathsfRobin, which is (only) communication efficient. For small fields and for statistical security parameter łambda, this protocol's communication improves over the previous state of the art (\mathsfMac'n'Cheese, Baum et al., CRYPTO'21) by up to factor łambda.
Our implementation outperforms prior state of the art. E.g., we achieve up to 6× improvement over \mathsfMac'n'Cheese (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over \mathsfQuickSilver (Yang et al., CCS'21) by up to 70× and over \mathsfAntMan (Weng et al., CCS'22) by up to 36×.
References
[1]
Carsten Baum, Lennart Braun, Alexander Munch-Hansen, Benoît Razet, and Peter Scholl. 2021a. Appenzeller to Brie: Efficient Zero-Knowledge Proofs for Mixed-Mode Arithmetic and Z2k. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, Virtual Event, Republic of Korea, 192--211. https://doi.org/10.1145/3460120.3484812
[2]
Carsten Baum, Lennart Braun, Alexander Munch-Hansen, and Peter Scholl. 2022. Moz$mathbbZ_2^k$arella: Efficient Vector-OLE and Zero-Knowledge Proofs over $mathbbZ_2^k$. In CRYPTO 2022, Part IV (LNCS, Vol. 13510), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 329--358. https://doi.org/10.1007/978--3-031--15985--5_12
[3]
Carsten Baum, Alex J. Malozemoff, Marc B. Rosen, and Peter Scholl. 2021b. Mac'n'Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions. In CRYPTO 2021, Part IV (LNCS, Vol. 12828), Tal Malkin and Chris Peikert (Eds.). Springer, Heidelberg, Germany, Virtual Event, 92--122. https://doi.org/10.1007/978--3-030--84259--8_4
[4]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. 2013. SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. In CRYPTO 2013, Part II (LNCS, Vol. 8043), Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 90--108. https://doi.org/10.1007/978--3--642--40084--1_6
[5]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Scalable Zero Knowledge via Cycles of Elliptic Curves. In CRYPTO 2014, Part II (LNCS, Vol. 8617), Juan A. Garay and Rosario Gennaro (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 276--294. https://doi.org/10.1007/978--3--662--44381--1_16
[6]
Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni. 2020. Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads. In TCC 2020, Part II (LNCS, Vol. 12551), Rafael Pass and Krzysztof Pietrzak (Eds.). Springer, Heidelberg, Germany, Durham, NC, USA, 168--197. https://doi.org/10.1007/978--3-030--64378--2_7
[7]
Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni. 2021. Time- and Space-Efficient Arguments from Groups of Unknown Order. In CRYPTO 2021, Part IV (LNCS, Vol. 12828), Tal Malkin and Chris Peikert (Eds.). Springer, Heidelberg, Germany, Virtual Event, 123--152. https://doi.org/10.1007/978--3-030--84259--8_5
[8]
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. 2019. Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs. In CRYPTO 2019, Part III (LNCS, Vol. 11694), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 67--97. https://doi.org/10.1007/978--3-030--26954--8_3
[9]
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune K. Jakobsen, and Mary Maller. 2018. Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution. In ASIACRYPT 2018, Part I (LNCS, Vol. 11272), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, Germany, Brisbane, Queensland, Australia, 595--626. https://doi.org/10.1007/978--3-030-03326--2_20
[10]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. 2018. Compressing Vector OLE. In ACM CCS 2019, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, Toronto, ON, Canada, 896--912. https://doi.org/10.1145/3243734.3243868
[11]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. 2019b. Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, London, UK, 291--308. https://doi.org/10.1145/3319535.3354255
[12]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2019a. Efficient Pseudorandom Correlation Generators: Silent OT Extension and More. In CRYPTO 2019, Part III (LNCS, Vol. 11694), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 489--518. https://doi.org/10.1007/978--3-030--26954--8_16
[13]
Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish. 2013. Verifying Computations with State. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (Farminton, Pennsylvania) (SOSP '13). Association for Computing Machinery, New York, NY, USA, 341--357. https://doi.org/10.1145/2517349.2522733
[14]
Ran Canetti. 2001. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd FOCS. IEEE Computer Society Press, Las Vegas, NV, USA, 136--145. https://doi.org/10.1109/SFCS.2001.959888
[15]
Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. 2021. Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes. In CRYPTO 2021, Part III (LNCS, Vol. 12827), Tal Malkin and Chris Peikert (Eds.). Springer, Heidelberg, Germany, Virtual Event, 502--534. https://doi.org/10.1007/978--3-030--84252--9_17
[16]
Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. 1994. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In CRYPTO'94 (LNCS, Vol. 839), Yvo Desmedt (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 174--187. https://doi.org/10.1007/3--540--48658--5_19
[17]
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy, and Michiel Verbauwhede. 2022. Efficient Proof of RAM Programs from Any Public-Coin Zero-Knowledge System. In Security and Cryptography for Networks, Clemente Galdi and Stanislaw Jarecki (Eds.). Springer International Publishing, Cham, 615--638.
[18]
Samuel Dittmer, Yuval Ishai, Steve Lu, and Rafail Ostrovsky. 2022. Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One. In ACM CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, Los Angeles, CA, USA, 829--841. https://doi.org/10.1145/3548606.3559385
[19]
Samuel Dittmer, Yuval Ishai, and Rafail Ostrovsky. 2021. Line-Point Zero Knowledge and Its Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 199), Stefano Tessaro (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 5:1--5:24. https://doi.org/10.4230/LIPIcs.ITC.2021.5
[20]
Uriel Feige and Adi Shamir. 1990. Witness Indistinguishable and Witness Hiding Protocols. In 22nd ACM STOC. ACM Press, Baltimore, MD, USA, 416--426. https://doi.org/10.1145/100216.100272
[21]
Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, and Chenkai Weng. 2021. Constant-Overhead Zero-Knowledge for RAM Programs. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, Virtual Event, Republic of Korea, 178--191. https://doi.org/10.1145/3460120.3484800
[22]
Anwar M. Ghuloum and Allan L. Fisher. 1995. Flattening and Parallelizing Irregular, Recurrent Loop Nests. SIGPLAN Not., Vol. 30, 8 (aug 1995), 58--67. https://doi.org/10.1145/209937.209944
[23]
Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk. 2022. Stacking Sigmas: A Framework to Compose $varSigma$-Protocols for Disjunctions. In EUROCRYPT 2022, Part II (LNCS, Vol. 13276), Orr Dunkelman and Stefan Dziembowski (Eds.). Springer, Heidelberg, Germany, Trondheim, Norway, 458--487. https://doi.org/10.1007/978--3-031-07085--3_16
[24]
Aarushi Goel, Mathias Hall-Andersen, Gabriel Kaptchuk, and Nicholas Spooner. 2023. Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions. In EUROCRYPT 2023, Part II (LNCS, Vol. 14005), Carmit Hazay and Martijn Stam (Eds.). Springer, Heidelberg, Germany, Lyon, France, 347--378. https://doi.org/10.1007/978--3-031--30617--4_12
[25]
S Goldwasser, S Micali, and C Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (Providence, Rhode Island, USA) (STOC '85). Association for Computing Machinery, New York, NY, USA, 291--304. https://doi.org/10.1145/22145.22178
[26]
David Heath and Vladimir Kolesnikov. 2020a. A 2.1 KHz Zero-Knowledge Processor with BubbleRAM. In ACM CCS 2020, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). ACM Press, Virtual Event, USA, 2055--2074. https://doi.org/10.1145/3372297.3417283
[27]
David Heath and Vladimir Kolesnikov. 2020b. Stacked Garbling for Disjunctive Zero-Knowledge Proofs. In EUROCRYPT 2020, Part III (LNCS, Vol. 12107), Anne Canteaut and Yuval Ishai (Eds.). Springer, Heidelberg, Germany, Zagreb, Croatia, 569--598. https://doi.org/10.1007/978--3-030--45727--3_19
[28]
David Heath and Vladimir Kolesnikov. 2021. PrORAM - Fast $P(łog n)$ Authenticated Shares ZK ORAM. In ASIACRYPT 2021, Part IV (LNCS, Vol. 13093), Mehdi Tibouchi and Huaxiong Wang (Eds.). Springer, Heidelberg, Germany, Singapore, 495--525. https://doi.org/10.1007/978--3-030--92068--5_17
[29]
David Heath, Yibin Yang, David Devecsery, and Vladimir Kolesnikov. 2021. Zero Knowledge for Everything and Everyone: Fast ZK Processor with Cached ORAM for ANSI C Programs. In 2021 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 1538--1556. https://doi.org/10.1109/SP40001.2021.00089
[30]
Zhangxiang Hu, Payman Mohassel, and Mike Rosulek. 2015. Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost. In CRYPTO 2015, Part II (LNCS, Vol. 9216), Rosario Gennaro and Matthew J. B. Robshaw (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 150--169. https://doi.org/10.1007/978--3--662--48000--7_8
[31]
Vladimir Kolesnikov. 2018. $mathsfFree mathttIF $: How to Omit Inactive Branches and Implement $S$-Universal Garbled Circuit (Almost) for Free. In ASIACRYPT 2018, Part III (LNCS, Vol. 11274), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, Germany, Brisbane, Queensland, Australia, 34--58. https://doi.org/10.1007/978--3-030-03332--3_2
[32]
Ning Luo, Timos Antonopoulos, William R. Harris, Ruzica Piskac, Eran Tromer, and Xiao Wang. 2022. Proving UNSAT in Zero Knowledge. In ACM CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, Los Angeles, CA, USA, 2203--2217. https://doi.org/10.1145/3548606.3559373
[33]
Payman Mohassel, Mike Rosulek, and Alessandra Scafuro. 2017. Sublinear Zero-Knowledge Arguments for RAM Programs. In EUROCRYPT 2017, Part I (LNCS, Vol. 10210), Jean-Sé bastien Coron and Jesper Buus Nielsen (Eds.). Springer, Heidelberg, Germany, Paris, France, 501--531. https://doi.org/10.1007/978--3--319--56620--7_18
[34]
Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. 2019. Distributed Vector-OLE: Improved Constructions and Implementation. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, London, UK, 1055--1072. https://doi.org/10.1145/3319535.3363228
[35]
Riad S. Wahby, Srinath T. V. Setty, Zuocheng Ren, Andrew J. Blumberg, and Michael Walfish. 2015. Efficient RAM and control flow in verifiable outsourced computation. In NDSS 2015. The Internet Society, San Diego, CA, USA.
[36]
Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. 2016. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit.
[37]
Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. 2021a. Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits. In 2021 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 1074--1091. https://doi.org/10.1109/SP40001.2021.00056
[38]
Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. 2021b. Mystique: Efficient Conversions for Zero-Knowledge Proofs with Applications to Machine Learning. In USENIX Security 2021, Michael Bailey and Rachel Greenstadt (Eds.). USENIX Association, 501--518.
[39]
Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, and Xiao Wang. 2022. AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication. In ACM CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, Los Angeles, CA, USA, 2901--2914. https://doi.org/10.1145/3548606.3560667
[40]
Kang Yang, Pratik Sarkar, Chenkai Weng, and Xiao Wang. 2021. QuickSilver: Efficient and Affordable Zero-Knowledge Proofs for Circuits and Polynomials over Any Field. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, Virtual Event, Republic of Korea, 2986--3001. https://doi.org/10.1145/3460120.3484556
[41]
Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. 2020. Ferret: Fast Extension for Correlated OT with Small Communication. In ACM CCS 2020, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). ACM Press, Virtual Event, USA, 1607--1626. https://doi.org/10.1145/3372297.3417276
[42]
Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, and Muthuramakrishnan Venkitasubramaniam. 2023. Batchman and Robin: Batched and Non-batched Branching for Interactive ZK. Cryptology ePrint Archive. https://eprint.iacr.org/2023/1257 https://eprint.iacr.org/2023/1257.
[43]
Yibin Yang, David Heath, Vladimir Kolesnikov, and David Devecsery. 2022. EZEE: Epoch Parallel Zero Knowledge for ANSI C. In 7th IEEE European Symposium on Security and Privacy, EuroS&P 2022, Genoa, Italy, June 6--10, 2022. IEEE, Genoa, Italy, 109--123. https://doi.org/10.1109/EuroSP53844.2022.00015 io
Index Terms
- Batchman and Robin: Batched and Non-batched Branching for Interactive ZK
Recommendations
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityWe describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F(s; r), where ...
Verifiable Oblivious Transfer Protocol
The Oblivious Transfer (OT), introduced by Rabin in 1981, has become an important and fundamental cryptography technique. An OT protocol should have two important characteristics: the sender's privacy and the chooser's privacy. The sender is a party who ...
Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority
A multiparty protocol to compute a function f(x 1, ..., x n ) operates as follows: each of n processors holds an input x i , and jointly they must compute and reveal f(x 1, ..., x n ) without revealing any additional information about the inputs. The ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
3722 pages
ISBN:9798400700507
DOI:10.1145/3576915
- General Chairs:
- Weizhi Meng,
- Christian D. Jensen,
- Program Chairs:
- Cas Cremers,
- Engin Kirda
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
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
- Defense Advanced Research Projects Agency
- Cisco Research Award
- NSF (National Science Foundation)
Conference
CCS '23
Sponsor:
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 '24
- Sponsor:
- sigsac
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 408Total Downloads
- Downloads (Last 12 months)408
- Downloads (Last 6 weeks)59
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in