Zero-Knowledge Accumulators and Set Algebra
Zero-Knowledge Accumulators and Set Algebra
复制标题
DOI：
10.1007/978-3-662-53890-6_3
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Esha Ghosh;O. Ohrimenko;D. Papadopoulos;R. Tamassia;Nikos Triandopoulos
中科院分区：
文献类型：
--
作者：
Esha Ghosh;O. Ohrimenko;D. Papadopoulos;R. Tamassia;Nikos Triandopoulos
密码算法允许用一个累加值简洁地表示一个集合，关于这个集合的短（非）成员证明可以被有效地构造和验证。传统上，它们的安全性捕获了可靠性，但没有提供隐私：令人信服的证明可靠地编码集合成员资格，但它们很可能会泄露有关累积集合的信息。在本文中，我们通过引入和设计零知识累积器，另外提供隐藏保证，提出了一个强大的隐私保护增强：累积值和证明不会泄露通过元素插入/删除演变的动态集合。我们正式的新属性使用标准的真实理想的范例，即要求一个自适应的对手访问查询/更新的预言机，不能告诉他是否与诚实的协议执行或模拟器完全无知的集（甚至它的更新类型）。我们严格地比较了新原语与现有原语，用于集成员（或其他关系）的隐私保护验证，并在相关安全定义中得出有趣的含义，表明零知识验证比Naor等人最近的相关工作提供更强的隐私。[TCC 2015]和Derler等人。[CT-RSA 2015]。我们构造了第一个动态的通用零知识累加器，我们证明是完美的零知识和q-强双线性Diffie-Hellman假设下的安全。最后，我们扩展了我们的新的隐私概念和我们的新建设提供隐私保护的证明，也为认证的动态集合-一个原语有效地验证更精细的集合操作，超越了集合成员资格。我们引入了一个原语，支持零知识可验证的集合代数：简洁的证明工会，交集和集差查询的动态演变的集合可以有效地构建和优化验证，而第一次，他们泄漏的集合以外的查询结果。
Cryptographic accumulators allow to succinctly represent a set by an accumulation value with respect to which short (non-)membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: Convincing proofs reliably encode set membership, but they may well leak information about the accumulated set.In this paper we put forward a strong privacy-preserving enhancement by introducing and devisingzero-knowledge accumulatorsthat additionally provide hiding guarantees: Accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/deletions. We formalize the new property using the standard real-ideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set (even of the type of updates on it). We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership (or other relations) and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by Naor et al. [TCC 2015] and Derler et al. [CT-RSA 2015]. We construct the first dynamic universal zero-knowledge accumulator that we show to be perfect zero-knowledge and secure under theq-Strong Bilinear Diffie-Hellman assumption.Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection—a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports azero-knowledge verifiable set algebra: Succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while—for the first time—they leak nothing about the collection beyond the query result.