Paper 2023/1518

Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees

Matteo Campanelli, Protocol Labs
Antonio Faonio, EURECOM
Dario Fiore, IMDEA Software
Tianyu Li, Delft University of Technology
Helger Lipmaa, University of Tartu

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 the 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 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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2024
zkSNARzero-knowledgelookup argumentsdecision trees
Contact author(s)
matteo @ protocol ai
antonio faonio @ eurecom fr
dario fiore @ imdea org
tianyu li @ tudelft nl
helger lipmaa @ gmail com
2024-01-22: revised
2023-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matteo Campanelli and Antonio Faonio and Dario Fiore and Tianyu Li and Helger Lipmaa},
      title = {Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1518},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.