Aggregated Set Membership Proofs: Aggregated Signature-Based Set Membership Proofs and implementation in Client and Server Verifiable Additive Homomorphic Secret Sharing - Ek, Hanna (My University, 2021)
This thesis addresses the issue of inflated computational complexity for the verification of multiple zero-knowledge proofs. More precisely, verification of numerous zero-knowledge set membership proofs performed by a single verifier is considered. To reduce the computations required by such a verifier Aggregated Set Membership Proofs are introduced. Aggregated set membership proofs unifies multiple set membership proofs into one aggregated proof, such that the validity of the aggregated proof implies the validity of all individual proofs. Completeness, soundness and zero-knowledge requirements are established for zero-knowledge aggregated set membership proofs. A concrete construction of aggregated set membership proofs is presented and proved to satisfy the completeness, soundness and zero-knowledge requirements. The construction is a partial aggregation of signature-based set membership proofs, [5], and is referred to as aggregated signature-based set membership proofs. A general technique to verify clients in verifiable additive homomorphic secret sharing is derived. The clients are verified by computing zero-knowledge proofs, derived from Pedersen commitments, of some given statement and then the proofs are validated by a verifier. If the proved statement is that the shared secrets belong to a discrete set, clients construct set membership proofs. Usually, several clients participate in verifiable additive homomorphic secret sharing protocols resulting in that the verification of clients is computationally expensive. A prototype implementation considering 100 clients showed that the runtime for verification of clients was reduced by 13% when verifying an aggregated signature-based set membership proof compared to verifying the same proofs without performing the aggregation.
Keywords: Aggregated Set Membership Proofs; Zero-knowledge proofs; VAHSS; cryptography