Cryptology ePrint Archive: Report 2005/138

I-HARPS: An Efficient Key Pre-distribution Scheme

Mahalingam Ramkumar

Abstract: We introduce an efficient random key pre-distribution scheme (RKPS) whose performance is 2 to 3 \textit{orders of magnitude} better than schemes of comparable complexity in the literature. This dramatic improvement is achieved by increasing \textit{insecure} storage complexity (for example using external flash memory). The proposed scheme is a combination of the Kerberos-like key distribution scheme (KDS) proposed by Leighton and Micali, and random key pre-distribution schemes based on subset intersections.

We also investigate a simple security policy, DOWN (decrypt only when necessary) (which along with very reasonable assurances of tamper resistance / read-proofness could ensures that no more than \textit{one} secret an be exposed by tampering with a node), and its effect on the security of key pre-distribution schemes. The proposed scheme lends itself well for efficient implementation of the DOWN policy, and therefore in practice could be a secure and efficient alternative to more complex conventional key distribution schemes.

Category / Keywords: secret-key cryptography / Key pre-distribution, Leighton Micali KDS, random KPS

Date: received 11 May 2005

Contact author: ramkumar at cse msstate edu

Available format(s): PDF | BibTeX Citation

Version: 20050512:211951 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]