Welcome to the resource topic for 2023/1518
Title:
Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees
Authors: Matteo Campanelli, Antonio Faonio, Dario Fiore, Tianyu Li, Helger Lipmaa
Abstract:Lookup arguments allow to prove that the elements of a committed vector come from a (bigger) committed table. They enable novel approaches to reduce the prover complexity of general-purpose zkSNARKs, implementing “non-arithmetic operations” such as range checks, XOR and AND more efficiently. We extend the notion of lookup arguments along two directions and improve their efficiency:
(1) we extend vector lookups to matrix lookups (where we can prove that a committed matrix is a submatrix of a committed table).
(2) We consider the notion of zero-knowledge lookup argument that keeps the privacy of both the sub-vector/sub-matrix and the table.
(3) We present new zero-knowledge lookup arguments, dubbed cq+, zkcq+ and cq++, more efficient than the state of art, namely the recent work by Eagen, Fiore and Gabizon named cq.
Finally, we give a novel application of zero-knowledge matrix lookup argument to the domain of zero-knowledge decision tree where the model provider releases a commitment to a decision tree and can prove in zero-knowledge statistics over the committed data structure. Our scheme based on lookup arguments has succinct verification, prover’s time complexity asymptotically better than the state of the art, and is secure in a strong security model where the commitment to the decision tree can be malicious.
ePrint: https://eprint.iacr.org/2023/1518
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .