Document Open Access Logo

Line-Point Zero Knowledge and Its Applications

Authors Samuel Dittmer, Yuval Ishai, Rafail Ostrovsky

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.5.pdf
  • Filesize: 0.79 MB
  • 24 pages

Document Identifiers

Author Details

Samuel Dittmer
  • Stealth Software Technologies Inc., Los Angeles, CA, USA
Yuval Ishai
  • Department of Computer Science, Technion, Haifa, Israel
Rafail Ostrovsky
  • Department of Computer Science and Mathematics, University of California, Los Angeles, CA, USA

Funding

Supported by DARPA Contract No. HR001120C0087. Y. Ishai supported in part by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and ISF grant 2774/20. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA. Distribution Statement "A" (Approved for Public Release, Distribution Unlimited).

Cite AsGet BibTex

Samuel Dittmer, Yuval Ishai, and Rafail Ostrovsky. Line-Point Zero Knowledge and Its Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.5

Abstract

We introduce and study a simple kind of proof system called line-point zero knowledge (LPZK). In an LPZK proof, the prover encodes the witness as an affine line 𝐯(t) : = at + 𝐛 in a vector space 𝔽ⁿ, and the verifier queries the line at a single random point t = α. LPZK is motivated by recent practical protocols for vector oblivious linear evaluation (VOLE), which can be used to compile LPZK proof systems into lightweight designated-verifier NIZK protocols. We construct LPZK systems for proving satisfiability of arithmetic circuits with attractive efficiency features. These give rise to designated-verifier NIZK protocols that require only 2-5 times the computation of evaluating the circuit in the clear (following an input-independent preprocessing phase), and where the prover communicates roughly 2 field elements per multiplication gate, or roughly 1 element in the random oracle model with a modestly higher computation cost. On the theoretical side, our LPZK systems give rise to the first linear interactive proofs (Bitansky et al., TCC 2013) that are zero knowledge against a malicious verifier. We then apply LPZK towards simplifying and improving recent constructions of reusable non-interactive secure computation (NISC) from VOLE (Chase et al., Crypto 2019). As an application, we give concretely efficient and reusable NISC protocols over VOLE for bounded inner product, where the sender’s input vector should have a bounded L₂-norm.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
Keywords
  • Zero-knowledge proofs
  • NIZK
  • correlated randomness
  • vector oblivious linear evaluation
  • non-interactive secure computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Arash Afshar, Payman Mohassel, Benny Pinkas, and Ben Riva. Non-interactive secure computation based on cut-and-choose. In EUROCRYPT 2014, pages 387-404, 2014. Google Scholar
  2. Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron. Secure arithmetic computation with constant computational overhead. In CRYPTO 2017, Part I, pages 223-254, 2017. Google Scholar
  3. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. How to garble arithmetic circuits. In FOCS 2011, pages 120-129, 2011. Google Scholar
  4. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3), 1998. Google Scholar
  5. Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, and Juan Ramón Troncoso-Pastoriza. Efficient protocols for oblivious linear function evaluation from Ring-LWE. In SCN 2020, pages 130-149, 2020. Google Scholar
  6. Carsten Baum, Alex J. Malozemoff, Marc Rosen, and Peter Scholl. Mac'n'cheese: Zero-knowledge proofs for arithmetic circuits with nested disjunctions. Cryptology ePrint Archive, Report 2020/1410, 2020. URL: https://eprint.iacr.org/2020/1410.
  7. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable zero knowledge with no trusted setup. In CRYPTO 2019, Part III, Lecture Notes in Computer Science, pages 701-732, 2019. Google Scholar
  8. Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, 2011. Google Scholar
  9. Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. In TCC 2013, pages 315-333, 2013. Google Scholar
  10. Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In STOC 1988, pages 103-112, 1988. Google Scholar
  11. Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth, Mohammad Hajiabadi, and Sune K. Jakobsen. Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In ASIACRYPT 2017, Part III, pages 336-365, 2017. Google Scholar
  12. Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In CCS 2018, pages 896-912, 2018. Google Scholar
  13. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In CCS 2019, pages 291-308, 2019. Google Scholar
  14. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In CRYPTO 2019, Part III, pages 489-518, 2019. Google Scholar
  15. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Correlated pseudorandom functions from variable-density LPN. In FOCS 2020, pages 1069-1080, 2020. Full version: URL: https://eprint.iacr.org/2020/1417.
  16. Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators from Ring-LPN. In CRYPTO 2020, Part II, pages 387-416, 2020. Google Scholar
  17. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In FOCS 2001, pages 136-145, 2001. Google Scholar
  18. Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-quantum zero-knowledge and signatures from symmetric-key primitives. In CCS 2017, pages 1825-1842, 2017. Google Scholar
  19. Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, and Vinod Vaikuntanathan. Reusable non-interactive secure computation. In CRYPTO 2019, Part III, pages 462-488, 2019. Google Scholar
  20. Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In EUROCRYPT 2010, pages 445-465, 2010. Google Scholar
  21. Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, 2012. Google Scholar
  22. Leo de Castro, Chiraag Juvekar, and Vinod Vaikuntanathan. Fast vector oblivious linear evaluation from ring learning with errors. IACR Cryptol. ePrint Arch., 2020:685, 2020. URL: https://eprint.iacr.org/2020/685.
  23. Samuel Dittmer, Yuval Ishai, and Rafail Ostrovsky. Line-point zero knowledge and its applications. Cryptology ePrint Archive, Report 2020/1446, 2020. URL: https://eprint.iacr.org/2020/1446.
  24. Tore Kasper Frederiksen, Jesper Buus Nielsen, and Claudio Orlandi. Privacy-free garbled circuits with applications to efficient zero-knowledge. In EUROCRYPT 2015, Part II, pages 191-219, 2015. Google Scholar
  25. Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and Eran Tromer. Circuits resilient to additive attacks with applications to secure computation. In STOC 2014, pages 495-504, 2014. Google Scholar
  26. Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without pcps. In EUROCRYPT, 2013. Google Scholar
  27. Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. Zkboo: Faster zero-knowledge for boolean circuits. In USENIX Security 2016), 2016. Google Scholar
  28. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1-27:64, 2015. Google Scholar
  29. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. Google Scholar
  30. Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, pages 305-326, 2016. Google Scholar
  31. David Heath and Vladimir Kolesnikov. Stacked garbling for disjunctive zero-knowledge proofs. In EUROCRYPT 2020, Part III, pages 569-598, 2020. Google Scholar
  32. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In ICALP 2002, pages 244-256, 2002. Google Scholar
  33. Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky. Efficient arguments without short PCPs. In CCC, 2007. Google Scholar
  34. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, and Amit Sahai. Efficient non-interactive secure computation. In EUROCRYPT 2011, pages 406-425, 2011. Google Scholar
  35. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput., 39(3):1121-1152, 2009. Google Scholar
  36. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Secure arithmetic computation with no honest majority. In TCC 2009, pages 294-314, 2009. Google Scholar
  37. Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang. Improved non-interactive zero knowledge with applications to post-quantum signatures. In CCS 2018, pages 525-537. ACM, 2018. Google Scholar
  38. Dakshita Khurana, Rafail Ostrovsky, and Akshayaram Srinivasan. Round optimal black-box “commit-and-prove”. In Theory of Cryptography Conference, pages 286-313, 2018. Google Scholar
  39. Joe Kilian, Silvio Micali, and Rafail Ostrovsky. Minimum resource zero-knowledge proof. In CRYPTO 1989, pages 545-546. Springer, 1989. Google Scholar
  40. Alex Lombardi, Willy Quach, Ron D. Rothblum, Daniel Wichs, and David J. Wu. New constructions of reusable designated-verifier nizks. In CRYPTO 2019, pages 670-700, 2019. Google Scholar
  41. Payman Mohassel and Mike Rosulek. Non-interactive secure 2pc in the offline/online and batch settings. In EUROCRYPT 2017, Part III, pages 425-455, 2017. Google Scholar
  42. Moni Naor and Benny Pinkas. Oblivious polynomial evaluation. SIAM Journal on Computing, 35(5):1254-1281, 2006. Google Scholar
  43. Willy Quach, Ron D. Rothblum, and Daniel Wichs. Reusable designated-verifier nizks for all NP from CDH. In EUROCRYPT 2019, pages 593-621, 2019. Google Scholar
  44. Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. Distributed vector-OLE: Improved constructions and implementation. In CCS 2019, pages 1055-1072, 2019. Google Scholar
  45. Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In IEEE Symposium on Security and Privacy (S&P), 2021. Full version: URL: https://eprint.iacr.org/2020/925.
  46. Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In CRYPTO 2019, Part III, pages 733-764, 2019. Google Scholar
  47. Jiaheng Zhang, Weijie Wang, Yinuo Zhang, and Yupeng Zhang. Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. Cryptology ePrint Archive, Report 2020/1247, 2020. URL: https://eprint.iacr.org/2020/1247.
  48. Jiaheng Zhang, Tiancheng Xie, Yupeng Zhang, and Dawn Song. Transparent polynomial delegation and its applications to zero knowledge proof. In 2020 IEEE Symposium on Security and Privacy, pages 859-876, 2020. Google Scholar
  49. ZKProof. ZKProof Standards, 2020. URL: https://zkproof.org.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact