Paper 2002/069

A Distributed and Computationally Secure Key Distribution Scheme

Vanesa Daza, Javier Herranz, Carles Padró, and Germán Sáez


In 1999, Naor, Pinkas and Reingold introduced schemes in which some groups of servers distribute keys among a set of users in a distributed way. They gave some specific proposals both in the unconditional and in the computational security framework. Their computationally secure scheme is based on the Decisional Diffie-Hellman Assumption. This model assumes secure communication between users and servers. Furthermore it requires users to do some expensive computations in order to obtain a key. In this paper we modify the model introduced by Naor et al., requiring authenticated channels instead of assuming the existence of secure channels. Our model makes the user's computations easier, because most computations of the protocol are carried out by servers, keeping to a more realistic situation. We propose a basic scheme, that makes use of ElGamal cryptosystem, and that fits in with this model in the case of a passive adversary. We then add zero-knowledge proofs and verifiable secret sharing to prevent from the action of an active adversary. We consider general structures (not only the threshold ones) for those subsets of servers that can provide a key to a user and for those tolerated subsets of servers that can be corrupted by the adversary. We find necessary combinatorial conditions on these structures in order to provide security to our scheme.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Proceedings of Information Security Conference, ISC'02. LNCS 2433, pp. 342--356
Key distributionsecret sharing schemes.
Contact author(s)
jherranz @ mat upc es
2003-04-11: revised
2002-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vanesa Daza and Javier Herranz and Carles Padró and Germán Sáez},
      title = {A Distributed and Computationally Secure Key Distribution Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2002/069},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.