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

DOI10.1515/JMC-2014-0031zbMATH Open1403.94073arXiv1403.1468OpenAlexW2963924363MaRDI QIDQ897709FDOQ897709

Maura Paterson, D. R. Stinson

Publication date: 7 December 2015

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1403.1468

Recommendations

• Publication:4945391
• Graph-theoretic design and analysis of key predistribution schemes
• Construction and application of a perfectly hiding commitment scheme based on one-way functions
• An efficient construction of perfect secret sharing schemes for graph-based structures
• scientific article
• Candidate one-way functions based on expander graphs
• Verifiable random functions: relations to identity-based key encapsulation and new constructions
• Attacks on Okamoto and Tanaka's one-way ID-based key distribution system
• Key predistribution schemes and one-time broadcast encryption schemes from algebraic geometry codes
• One-round identity-based key exchange with perfect forward security

zbMATH Keywords

communication graphkey predistribution

Mathematics Subject Classification ID

Cryptography (94A60)

Cited In (2)

• Title not available (Why is that?)
• Decomposing complete graphs into isomorphic complete multipartite graphs

This page was built for publication: Optimal constructions for ID-based one-way-function key predistribution schemes realizing specified communication graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897709)