Welcome to the resource topic for 2024/1509
Title:
DUPLEX: Scalable Zero-Knowledge Lookup Arguments over RSA Group
Authors: Semin Han, Geonho Yoon, Hyunok Oh, Jihye Kim
Abstract:Lookup arguments enable a prover to convince a verifier that a committed vector of lookup elements \vec{f} \in \mathbb{F}^m is contained within a predefined table T \in \mathbb{F}^N. These arguments are particularly beneficial for enhancing the performance of SNARKs in handling non-arithmetic operations, such as batched range checks or bitwise operations. While existing works have achieved efficient and succinct lookup arguments, challenges remain, particularly when dealing with large vectors of lookup elements in privacy-sensitive applications.
In this paper, we introduce \duplex, a scalable zero-knowledge lookup argument scheme that offers significant improvements over previous approaches. Notably, we present the first lookup argument designed to operate over the RSA group. Our core technique allows for the transformation of elements into prime numbers to ensure compatibility with the RSA group, all without imposing substantial computational costs on the prover. Given m lookup elements, \duplex achieves an asymptotic proving time of O(m \log m), with constant-sized proofs, constant-time verification, and a public parameter size independent of the table size N. Additionally, \duplex ensures the privacy of lookup elements and is robust against dynamic table updates, making it highly suitable for scalable verifiable computation in real-world applications.
We implemented and empirically evaluated \duplex, comparing it with the state-of-the-art zero-knowledge lookup argument Caulk [CCS’22]. Our experimental results demonstrate that \duplex significantly outperforms Caulk in proving time for both single and batched lookup arguments, while maintaining practical proof size and verification time.
ePrint: https://eprint.iacr.org/2024/1509
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 .