Zero-Knowledge sets, proposed by Micali et al. in FOCS'03, allow the owner of a set S to publish a very short commitment C_S to S, so that the owner can later prove or disprove, against C_S, the membership of any (potential infinity many) elements chosen by the verifier, without leaking more about S than the membership of the elements. This new secure primitive is proved to be useful in private data queries, and other similar scenarios where depends on the trust and privacy.

We investigate the theoretical primitives underline this new secure notion. The main contribution of this paper is to present a generic scheme for zero-knowledge sets which is as efficient as that in [1]. The new scheme is constructed by adopting the Merkle type of commitment under the assumption of existence of claw free pairs of trapdoor pseudo-permutations.