Homomorphic Proofs and Applications

This paper introduces and formalizes homomorphic proofs, which allow ‘adding’ proofs and ‘adding’ their statements to get a new proof of the ‘sum’ statement. We propose a construction of homomorphic proofs and show one of its applications which is a new accumulator scheme with delegatable non-membership (NM) proofs. We use this accumulator in extending the BCCKLS scheme [3] to achieve a delegatable anonymous credential with revocation system. Informally, the accumulator’s delegatable NM proofs enable user A, without revealing her identity, to delegate to user B the ability to prove that A’s identity is not included in a blacklist which could even be updated afterward. Moreover, the delegation should be redelegatable, unlinkable and verifiable. Security of the proposed schemes is provable. We implement a system for Revocation of Anonymous Credentials (RAC) that bases on the proposed accumulator. RAC could provide revocation for several anonymous credential systems.