Paper 2012/306

Efficient Threshold Zero-Knowledge with Applications to User-Centric Protocols

Marcel Keller, Gert Læssøe Mikkelsen, and Andy Rupp

Abstract

In this paper, we investigate on threshold proofs, a framework for distributing the prover’s side of interactive proofs of knowledge over multiple parties. Interactive proofs of knowledge (PoK) are widely used primitives of cryptographic protocols, including important user-centric protocols, such as identification schemes, electronic cash (e-cash), and anonymous credentials. We present a security model for threshold proofs of knowledge and develop threshold versions of well-known primitives such as range proofs, zero-knowledge proofs for preimages of homomorphisms (which generalizes PoKs of discrete logarithms, representations, p-th roots, etc.), as well as OR statements. These building blocks are proven secure in our model. Furthermore, we apply the developed primitives and techniques in the context of user-centric protocols. In particular, we construct distributed-user variants of Brands’ e-cash system and the bilinear anonymous credential scheme by Camenisch and Lysyanskaya. Distributing the user party in such protocols has several practical advantages: First, the security of a user can be increased by sharing secrets and computations over multiple devices owned by the user. In this way, losing control of a single device does not result in a security breach. Second, this approach also allows groups of users to jointly control an application (e.g., a joint e-cash account), not giving a single user full control. The distributed versions of the protocols we propose in this paper are relatively efficient (when compared to a general MPC approach). In comparison to the original protocols only the prover’s (or user’s) side is modified while the other side stays untouched. In particular, it is oblivious to the other party whether it interacts with a distributed prover (or user) or one as defined in the original protocol.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Will be published at "6th International Conference on Information-Theoretic Security (ICITS) 2012"
Keywords
Multiparty computationthreshold cryptographydistributed provers\Sigma-protocolse-cashanonymous credentials
Contact author(s)
gert l mikkelsen @ alexandra dk
History
2012-06-03: received
Short URL
https://ia.cr/2012/306
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/306,
      author = {Marcel Keller and Gert Læssøe Mikkelsen and Andy Rupp},
      title = {Efficient Threshold Zero-Knowledge with Applications to User-Centric Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2012/306},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/306}},
      url = {https://eprint.iacr.org/2012/306}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.