Paper 2026/844

MPlookup: A Quasilinear Multi-Party Lookup Argument in Collaborative zkSNARKs via Four Sorts and a Multi-Point Evaluation

Tingchuang Zhang, Shandong University

Zhijun Li, Shandong University

Minghui Xu, Shandong University

Xiuzhen Cheng, Shandong University

Chao Zhang, Tsinghua University

Abstract

A lookup argument is a cryptographic primitive that allows a prover to convince verifiers that every element of a private query vector belongs to a public table vector without disclosing the underlying data. It can enforce correct instruction execution in zero-knowledge virtual machines and serve as an important supplement to zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). However, existing lookup argument protocols operate exclusively in the single-prover setting and do not address the requirements of collaborative zkSNARKs, in which multiple parties jointly generate proofs over additively secret-shared data while preserving privacy from both other provers and verifiers. This work presents MPlookup, the first multi-party lookup argument protocol for collaborative zkSNARKs. MPlookup achieves quasilinear $O(N \log^2 N)$ complexity through four oblivious sorting operations together with a multi-point polynomial evaluation performed entirely over secret shares. We introduce a multi-point evaluation protocol in the distributed oblivious polynomial evaluation setting, constructed via oblivious subproduct tree construction and oblivious polynomial division with private divisors. We prove that the protocol satisfies obliviousness, completeness, soundness, and zero-knowledge. We implement MPlookup as an open-source Rust library, built upon the collaborative zkSNARKs framework and the CompatCircuit arithmetic black box. Our evaluation confirms a performance improvement over an $O(N^2)$ baseline while remaining competitive given the obliviousness requirement.

@misc{cryptoeprint:2026/844,
      author = {Huayi Qi and Tingchuang Zhang and Zhijun Li and Minghui Xu and Xiuzhen Cheng and Chao Zhang},
      title = {{MPlookup}: A Quasilinear Multi-Party Lookup Argument in Collaborative {zkSNARKs} via Four Sorts and a Multi-Point Evaluation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/844},
      year = {2026},
      url = {https://eprint.iacr.org/2026/844}
}