A Transparent Zero-Knowledge Dual Membership Set Commitment based on Perfect Hash Function

Abstract

Verifying a secret element’s (non-)membership status to a private set is challenging yet valuable for access control and verifiable computing applications. On the other hand, blockchain technology, known for its decentralized and tamper-proof nature, allows one to commit any data publicly. This work proposes a zero-knowledge Dual Membership Set Commit (zkDMSC) scheme to bridge the two. Our scheme allows the provers to commit their private set on blockchain and prove a secret element’s membership status to the set in a zero-knowledge manner.We introduce the Perfect Hash Function(PHF) into the field of membership query and use the Merkle tree to construct an efficient zero-knowledge dual membership proof. The prover can combine our dual membership proof with other property proofs of the queried element for different verification requirements. In addition, our proposal does not require a trusted setup and only uses post-quantum cryptographic assumptions. We also implement the proposal and show the performance of our implementation that matches or surpasses the state of the art.