Optimal constructions for ID-based one-way-function keyudpredistribution schemes realizing specified communication graphs

摘要

We study a method for key predistribution in a network of n users where pairwise keys areudcomputed by hashing users’ IDs along with secret information that has been (pre)distributed toudthe network users by a trusted entity. A communication graph G can be specified to indicateudwhich pairs of users should be able to compute keys. We determine necessary and sufficientudconditions for schemes of this type to be secure. We also consider the problem of minimizingudthe storage requirements of such a scheme; we are interested in the total storage as well asudthe maximum storage required by any user. Minimizing the total storage is NP-hard, whereasudminimizing the maximum storage required by a user can be computed in polynomial time.