Set Membership with Accumulators or Signatures

Verifying the presence or absence of an element in a set S becomes costly as the set grows. This work presents cryptographic schemes that achieve scalability by compressing the set into a concise digest and using proofs to delegate the increasing cost to a prover. We study further optimizations such as improving computation costs for the prover when the digest is trusted and further limiting the frequency of proof updates when the proofs refer to membership. We also decentralize the trust needed for maintaining the digest when no significant amount of element deletions is expected and achieve privacy against trusted entities who maintain the digest. Regarding fully decentralized settings that do not rely on trust, we present further optimizations through batch proofs for multiple elements that form a set I with verification costs independent from the size of I. Such techniques also apply to the centralized setting. In both settings, we discuss how a prover can avoid disclosing the element(s) of the proof, achieving privacy against a verifier or any outsider. When proving for multiple elements, we describe techniques for proving a stronger statement: only disclose the number of the elements while keeping the elements hidden and verification independent from |I|. Finally, we construct schemes that achieve stronger privacy even against insiders, meaning the rest of the membership proof holders, in the strong, decentralized setting.

Author

• Karantaidou, Ioanna

Identifier

hdl:1920/13708

OAI identifier oai:identifier

oai:MARS:1920/13708