Algebraic Construction for Zero-Knowledge Sets

Zero knowledge sets is a new cryptographic primitive introduced byMicali, Rabin, and Kilian in FOCS 2003. It has been intensivelystudied recently. However all the existing ZKS schemes follow thebasic structure by Micali \it et al. That is, the schemes employ theMerkle tree as a basic structure and mercurial commitments as thecommitment units to nodes of the tree. The proof for any queryconsists of an authentication chain. We propose in this paper a newalgebraic scheme that is completely different from all the existingschemes. Our new scheme is computationally secure under the standardstrong RSA assumption. Neither mercurial commitments nor treestructure is used in the new construction. In fact, the proverin our construction commits the desired set without anytrapdoor information, which is another key important difference fromthe previous approaches.