Zero-Knowledge Set Membership Proofs Using Bilinear-Map Accumulators

Abstract: The development and research of privacy mechanisms has become increasinglyimportant to different types of organizations which act as a central partyin multi-party data flows. A set membership proof in zero knowledge (ZKSMproof) is an example of such a privacy mechanism which can be applied inmultiple types of systems. This type of proofs allows one to prove statementsabout the (non-)membership of an element to a set – all without explicitly revealingthe element (or possibly the entire set). In order to understand thepossibilities and limitations of using ZKSM proofs in practical applications,we have in this thesis: performed a theoretical analysis of different existingprotocols and primitives, developed functional C implementations of a fewselect protocols, and provided multiple illustrative use cases. We have alsoproposed a modified version of an existing protocol for ZKSM proofs, withour construction using bilinear-map accumulators as a primitive. This modifiedprotocol fits very well to a three-party model.The primitive of zero-knowledge accumulators (based on bilinear maps)played a central role in our implementation. The resulting performance of thesystem can be said to be relatively poor, however, it is likely not prohibitivelybad due to the nature of many relevant use cases. It was concluded that ZKSMproofs most certainly can be applied beneficially to improve the privacy in realsystems. Bilinear-map accumulators provide a solid approach to solving thisproblem, and it is mainly the state of pairing-based cryptography that needs tobe improved for practical industrial applications.