On the computational security of a distributed key distribution scheme

In a distributed key distribution scheme, a set of servers help a set of users in a group to securely obtain a common key. Security means that an adversary who corrupts some servers and some users has no information about the key of a non-corrupted group. In this work we formalize the security analysis of one of such schemes [11] which was not considered in the original proposal. We prove the scheme secure in the random oracle model, assuming that the Decisional Diffie-Hellman (DDH) problem is hard to solve. We also detail a possible modification of that scheme and the one in [24] which allows to prove the security of the schemes without assuming that a specific hash function behaves as a random oracle. As usual, this improvement in the security of the schemes is at the cost of an efficiency loss. © 2008 IEEE.The authors would like to thank the anonymous referees of the IEEE Transactions on Computers for their helpful comments about this work. The work of the first two authors was partially supported by the Spanish Ministry of Education and Science under Projects TSI2007-65406-C03-02 (“eAEGIS”) and CONSOLIDER CSD2007-00004 (“ARES”). The work of V. Daza was also supported by the Government of Catalonia under Grant 2005-SGR-00446. The work of J. Herranz was also supported by the Government of Catalonia under Grant 2005-SGR-00093. Finally, the work of G. Sáez was partially supported by the Spanish Ministry of Education and Science under Project TSI2006-02731Peer Reviewe