Sok: vector OLE-based zero-knowledge protocols
Pages 3527 - 3561
Abstract
A zero-knowledge proof is a cryptographic protocol where a prover can convince a verifier that a statement is true, without revealing any further information except for the truth of the statement. This article is a survey of recent developments in building practical zero-knowledge proof systems using vector oblivious linear evaluation (VOLE), a tool from secure two-party computation. In this work, we attempt to systematize the recent works on VOLE-based Zero-Knowledge proofs and make the state of the art accessible in one document.
References
[1]
Baum C., Braun L., Munch-Hansen A., Scholl P.: Mozarella: Efficient Vector-OLE and Zero-Knowledge Proofs Over . To appear at IACR CRYPTO 2022 (2022)
[2]
Baum C., Malozemoff A.J., Rosen M.B., Scholl P.: Mac’n’cheese: Zero-knowledge proofs for boolean and arithmetic circuits with nested disjunctions. In: Malkin T., Peikert C. (eds.) CRYPTO 2021, Part IV. LNCS, vol. 12828, pp. 92–122. Springer, Virtual Event (2021).
[3]
Baum C, Escudero D, Pedrouzo-Ulloa A, Scholl P, and Troncoso-Pastoriza JR Galdi C and Kolesnikov V Efficient protocols for oblivious linear function evaluation from ring-LWE SCN 20. LNCS 2020 Amalfi, Italy Springer 130-149
[4]
Baum C, Braun L, Munch-Hansen A, Razet B, and Scholl P Vigna G and Shi E Appenzeller to brie: Efficient zero-knowledge proofs for mixed-mode arithmetic and Z2k ACM CCS 2021 2021 Virtual Event, Republic of Korea ACM Press 192-211
[5]
Beaver D Feigenbaum J Foundations of secure interactive computing CRYPTO’91. LNCS 1992 Santa Barbara, CA, USA Springer 377-391
[6]
Bendlin R, Damgård I, Orlandi C, and Zakarias S Paterson KG Semi-homomorphic encryption and multiparty computation EUROCRYPT 2011. LNCS 2011 Tallinn, Estonia Springer 169-188
[7]
Ben-Sasson E, Chiesa A, Genkin D, Tromer E, and Virza M Canetti R and Garay JA SNARKs for C: Verifying program executions succinctly and in zero knowledge CRYPTO 2013, Part II. LNCS 2013 Santa Barbara, CA, USA Springer 90-108
[8]
Bitansky N, Chiesa A, Ishai Y, Ostrovsky R, and Paneth O Sahai A Succinct non-interactive arguments via linear interactive proofs TCC 2013. LNCS 2013 Tokyo, Japan Springer 315-333
[9]
Boneh D, Boyle E, Corrigan-Gibbs H, Gilboa N, and Ishai Y Boldyreva A and Micciancio D Zero-knowledge proofs on secret-shared data via fully linear PCPs CRYPTO 2019, Part III. LNCS 2019 Santa Barbara, CA, USA Springer 67-97
[10]
Boyle E, Couteau G, Gilboa N, and Ishai Y Lie D, Mannan M, Backes M, and Wang X Compressing vector OLE ACM CCS 2018 2018 Toronto, ON, Canada ACM Press 896-912
[11]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, Rindal P, and Scholl P Cavallaro L, Kinder J, Wang X, and Katz J Efficient two-round OT extension and silent non-interactive secure computation ACM CCS 2019 2019 London, UK ACM Press 291-308
[12]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Boldyreva A and Micciancio D Efficient pseudorandom correlation generators: Silent OT extension and more CRYPTO 2019, Part III. LNCS 2019 Santa Barbara, CA, USA Springer 489-518
[13]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Micciancio D and Ristenpart T Efficient pseudorandom correlation generators from ring-LPN CRYPTO 2020, Part II. LNCS 2020 Santa Barbara, CA, USA Springer 387-416
[14]
Catalano D and Fiore D Johansson T and Nguyen PQ Practical homomorphic MACs for arithmetic circuits EUROCRYPT 2013. LNCS 2013 Athens, Greece Springer 336-352
[15]
Catrina O and de Hoogh S Garay JA and Prisco RD Improved primitives for secure multiparty integer computation SCN 10. LNCS 2010 Amalfi, Italy Springer 182-199
[16]
Cramer R, Damgård I, and Schoenmakers B Desmedt Y Proofs of partial knowledge and simplified design of witness hiding protocols CRYPTO’94. LNCS 1994 Santa Barbara, CA, USA Springer 174-187
[17]
Cramer R, Damgård I, Escudero D, Scholl P, and Xing C Shacham H and Boldyreva A SPD : Efficient MPC mod for dishonest majority CRYPTO 2018, Part II. LNCS 2018 Santa Barbara, CA, USA Springer 769-798
[18]
Damgård I and Zakarias S Sahai A Constant-overhead secure computation of Boolean circuits using preprocessing TCC 2013. LNCS 2013 Tokyo, Japan Springer 621-641
[19]
Damgård I, Pastro V, Smart NP, and Zakarias S Safavi-Naini R and Canetti R Multiparty computation from somewhat homomorphic encryption CRYPTO 2012. LNCS 2012 Santa Barbara, CA, USA Springer 643-662
[20]
de Castro L., Juvekar C., Vaikuntanathan, V.: Fast vector oblivious linear evaluation from ring learning with errors. In: WAHC ’21: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Virtual Event, Korea, 15 November 2021, pp. 29–41. WAHC@ACM, (2021).
[21]
de Castro L, Hazay C, Ishai Y, Vaikuntanathan V, and Venkitasubramaniam M Dunkelman O and Dziembowski S Asymptotically quasi-optimal cryptography EUROCRYPT 2022, Part I. LNCS 2022 Trondheim, Norway Springer 303-334
[22]
Dittmer S., Ishai Y., Lu S., Ostrovsky R.: Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One. To appear at CCS 2022 (2022)
[23]
Dittmer, S., Ishai, Y., Ostrovsky, R.: Line-Point Zero Knowledge and Its Applications. In: 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021)
[24]
Escudero D, Ghosh S, Keller M, Rachuri R, and Scholl P Micciancio D and Ristenpart T Improved primitives for MPC over mixed arithmetic-binary circuits CRYPTO 2020, Part II. LNCS 2020 Santa Barbara, CA, USA Springer 823-852
[25]
Fiat A and Shamir A Odlyzko AM How to prove yourself: Practical solutions to identification and signature problems CRYPTO’86. LNCS 1987 Santa Barbara, CA, USA Springer 186-194
[26]
Franzese N., Katz J., Lu S., Ostrovsky R., Wang X., Weng C.: Constant-overhead zero-knowledge for RAM programs. In: Vigna G., Shi E. (eds.) ACM CCS 2021, pp. 178–191. ACM Press, Virtual Event, Republic of Korea (2021).
[27]
Frederiksen T.K., Nielsen J.B., Orlandi C.: Privacy-free garbled circuits with applications to efficient zero-knowledge. In: Oswald E., Fischlin M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 191–219. Springer, Sofia, Bulgaria (2015).
[28]
Gennaro R., Gentry C., Parno B., Raykova M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson T., Nguyen P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Athens, Greece (2013).
[29]
Giacomelli I., Madsen J., Orlandi C.: ZKBoo: Faster zero-knowledge for Boolean circuits. In: Holz T., Savage S. (eds.) USENIX Security 2016, pp. 1069–1083. USENIX Association, Austin, TX, USA (2016).
[30]
Goldwasser S., Micali S., Rackoff C.: The knowledge complexity of interactive proof-systems (extended abstract). In: 17th ACM STOC, pp. 291–304. ACM Press, Providence, RI, USA (1985).
[31]
Golovnev A., Lee J., Setty S., Thaler J., Wahby R.S.: Brakedown: Linear-time and post-quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021/1043 (2021)
[32]
Haque A., Heath D., Kolesnikov V., Lu S., Ostrovsky R., Shah A.: Garbled Circuits With Sublinear Evaluator. Cryptology ePrint Archive, Paper 2022/797 (2022)
[33]
Heath D., Kolesnikov V.: Stacked garbling for disjunctive zero-knowledge proofs. In: Canteaut A., Ishai Y. (eds.) EUROCRYPT 2020, Part III. LNCS, vol. 12107, pp. 569–598. Springer, Zagreb, Croatia (2020).
[34]
Ishai Y., Kushilevitz E., Ostrovsky R., Sahai A.: Zero-knowledge from secure multiparty computation. In: Johnson D.S., Feige U. (eds.) 39th ACM STOC, pp. 21–30. ACM Press, San Diego, CA, USA (2007).
[35]
Jawurek M., Kerschbaum F., Orlandi C.: Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In: Sadeghi A.-R., Gligor V.D., Yung M. (eds.) ACM CCS 2013, pp. 955–966. ACM Press, Berlin, Germany (2013).
[36]
Keller M, Orsini E, and Scholl P Weippl ER, Katzenbeisser S, Kruegel C, Myers AC, and Halevi S MASCOT: Faster malicious arithmetic secure computation with oblivious transfer ACM CCS 2016 2016 Vienna, Austria ACM Press 830-842
[37]
Liu T., Xie X., Zhang Y.: zkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy. In: Vigna G., Shi E. (eds.) ACM CCS 2021, pp. 2968–2985. ACM Press, Virtual Event, Republic of Korea (2021).
[38]
Luo N., Antonopoulos T., Harris W.R., Piskac R., Tromer E., Wang X.: Proving UNSAT in zero knowledge. In: Yin H., Stavrou A., Cremers C., Shi E. (eds.) ACM CCS 2022, pp. 2203–2217. ACM Press, Los Angeles, CA, USA (2022).
[39]
Neff CA Reiter MK and Samarati P A verifiable secret shuffle and its application to e-voting ACM CCS 2001 2001 Philadelphia, PA, USA ACM Press 116-125
[40]
Nielsen J.B., Orlandi C.: LEGO for two-party secure computation. In: Reingold, O (ed.) TCC 2009. LNCS, Vol. 5444, pp. 368–386. Springer (2009).
[41]
Nielsen JB, Nordholt PS, Orlandi C, and Burra SS Safavi-Naini R and Canetti R A new approach to practical active-secure two-party computation CRYPTO 2012. LNCS 2012 Santa Barbara, CA, USA Springer 681-700
[42]
Ore Ø Über höhere kongruenzen Norsk Mat. Forenings Skrifter 1922 1 7 15
[43]
Parker J., Harris W., Pernsteiner S., Cuellar S., Tromer E.: Proving Information Leaks in Zero Knowledge. private communication, to appear soon
[44]
Parno B., Howell J., Gentry C., Raykova M.: Pinocchio: Nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy, pp. 238–252. IEEE Computer Society Press, Berkeley, CA, USA (2013).
[45]
PROVENANCE: Making complex zero-knowledge proofs more practical. accessed on Jun 30th 2022
[46]
Roy L Dodis Y and Shrimpton T SoftSpokenOT: Quieter OT extension from small-field silent VOLE in the minicrypt model CRYPTO 2022, Part I. LNCS 2022 Santa Barbara, CA, USA Springer 657-687
[47]
Scholl P Abdalla M and Dahab R Extending oblivious transfer with low communication via key-homomorphic PRFs PKC 2018, Part I. LNCS 2018 Rio de Janeiro, Brazil Springer 554-583
[48]
Weng C., Yang K., Katz J., Wang X.: Wolverine: Fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In: 2021 IEEE Symposium on Security and Privacy, pp. 1074–1091. IEEE Computer Society Press, San Francisco, CA, USA (2021).
[49]
Weng C., Yang K., Xie X., Katz J., Wang X.: Mystique: Efficient conversions for zero-knowledge proofs with applications to machine learning. In: Bailey M., Greenstadt R. (eds.) USENIX Security 2021, pp. 501–518. USENIX Association (2021)
[50]
Weng C, Yang K, Yang Z, Xie X, and Wang X Yin H, Stavrou A, Cremers C, and Shi E AntMan: Interactive zero-knowledge proofs with sublinear communication ACM CCS 2022 2022 Los Angeles, CA, USA ACM Press 2901-2914
[51]
Yang K, Weng C, Lan X, Zhang J, and Wang X Ligatti J, Ou X, Katz J, and Vigna G Ferret: Fast extension for correlated OT with small communication ACM CCS 2020 2020 Virtual Event, USA ACM Press 1607-1626
[52]
Yang K, Sarkar P, Weng C, and Wang X Vigna G and Shi E QuickSilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field ACM CCS 2021 2021 Virtual Event, Republic of Korea ACM Press 2986-3001
[53]
Zahur S., Rosulek M., Evans D.: Two halves make a whole - reducing data transfer in garbled circuits using half gates. In: Oswald E., Fischlin M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 220–250. Springer, Sofia, Bulgaria (2015).
[54]
Zhang J., Liu T., Wang W., Zhang Y., Song D., Xie X., Zhang Y.: Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. In: Vigna G., Shi E. (eds.) ACM CCS 2021, pp. 159–177. ACM Press, Virtual Event, Republic of Korea (2021).
Recommendations
An Unconditional Study of Computational Zero Knowledge
We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. ...
Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer
In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or ...
Quantum protocols for zero-knowledge systems
Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2023.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 October 2023
Accepted: 27 July 2023
Revision received: 04 June 2023
Received: 16 August 2022
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
- Defense Sciences Office, DARPA
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
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