2008 | OriginalPaper | Buchkapitel
Zero-Knowledge Sets with Short Proofs
verfasst von : Dario Catalano, Dario Fiore, Mariagrazia Messina
Erschienen in: Advances in Cryptology – EUROCRYPT 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Zero Knowledge Sets, introduced by Micali, Rabin and Kilian in [17], allow a prover to commit to a secret set
S
in a way such that it can later prove, non interactively, statements of the form
x
∈
S
(or
x
∉
S
), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on
S
, not even its size. Later, Chase
et al.
[5] abstracted away the Micali, Rabin and Kilian’s construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown in [5,4] how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic).
In this paper we introduce the notion of trapdoor
q
-mercurial commitments (
qTMC
s), a notion of mercurial commitment that allows the sender to commit to an
ordered
sequence of exactly
q
messages, rather than to a single one. Following [17,5] we show how to construct ZKS from
qTMC
s and collision resistant hash functions.
Then, we present an efficient realization of
qTMC
s that is secure under the so called Strong Diffie Hellman assumption, a number theoretic conjecture recently introduced by Boneh and Boyen in [3]. Using our scheme as basic building block, we obtain a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of non membership.