Paper 2026/844

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

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.