Optimal constructions for ID-based one-way-function key predistribution schemes realizing specified communication graphs
We study a method for key predistribution in a network of n users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph G can be specified to indicate which pairs of use...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2015-12-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2014-0031 |
| _version_ | 1817991631237808128 |
|---|---|
| author | Paterson Maura B. Stinson Douglas R. |
| author_facet | Paterson Maura B. Stinson Douglas R. |
| author_sort | Paterson Maura B. |
| collection | DOAJ |
| description | We study a method for key predistribution in a network of n users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph G can be specified to indicate which pairs of users should be able to compute keys. We determine necessary and sufficient conditions for schemes of this type to be secure. We also consider the problem of minimizing the storage requirements of such a scheme;
we are interested in the total storage as well as the maximum storage required by any user. Minimizing the total storage is NP-hard, whereas minimizing the maximum storage required by a user can be computed in polynomial time. |
| first_indexed | 2024-04-14T01:15:46Z |
| format | Article |
| id | doaj.art-50bab3ec296d48b196f4155f15231fa6 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-14T01:15:46Z |
| publishDate | 2015-12-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-50bab3ec296d48b196f4155f15231fa62022-12-22T02:20:52ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842015-12-019421522510.1515/jmc-2014-0031Optimal constructions for ID-based one-way-function key predistribution schemes realizing specified communication graphsPaterson Maura B.0Stinson Douglas R.1Department of Economics, Mathematics and Statistics, Birkbeck, University of London, Malet Street, London WC1E 7HX, UKDavid R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, CanadaWe study a method for key predistribution in a network of n users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph G can be specified to indicate which pairs of users should be able to compute keys. We determine necessary and sufficient conditions for schemes of this type to be secure. We also consider the problem of minimizing the storage requirements of such a scheme; we are interested in the total storage as well as the maximum storage required by any user. Minimizing the total storage is NP-hard, whereas minimizing the maximum storage required by a user can be computed in polynomial time.https://doi.org/10.1515/jmc-2014-0031key predistributioncommunication graph94a60 |
| spellingShingle | Paterson Maura B. Stinson Douglas R. Optimal constructions for ID-based one-way-function key predistribution schemes realizing specified communication graphs Journal of Mathematical Cryptology key predistribution communication graph 94a60 |
| title | Optimal constructions for ID-based one-way-function key predistribution schemes
realizing specified communication graphs |
| title_full | Optimal constructions for ID-based one-way-function key predistribution schemes
realizing specified communication graphs |
| title_fullStr | Optimal constructions for ID-based one-way-function key predistribution schemes
realizing specified communication graphs |
| title_full_unstemmed | Optimal constructions for ID-based one-way-function key predistribution schemes
realizing specified communication graphs |
| title_short | Optimal constructions for ID-based one-way-function key predistribution schemes
realizing specified communication graphs |
| title_sort | optimal constructions for id based one way function key predistribution schemes realizing specified communication graphs |
| topic | key predistribution communication graph 94a60 |
| url | https://doi.org/10.1515/jmc-2014-0031 |
| work_keys_str_mv | AT patersonmaurab optimalconstructionsforidbasedonewayfunctionkeypredistributionschemesrealizingspecifiedcommunicationgraphs AT stinsondouglasr optimalconstructionsforidbasedonewayfunctionkeypredistributionschemesrealizingspecifiedcommunicationgraphs |