Cryptology ePrint Archive: Report 2012/618

An ultra-lightweight ID-based pairwise key establishment scheme aiming at full collusion resistance

Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen, Domingo Gomez-Perez, Jaime Gutierrez, Santos Merino del Pozo

Abstract: This paper introduces a new key establishment scheme aiming at fully collusion-resistant identity-based symmetric-key agreement. In an identity-based pairwise key agreement scheme, a Trusted Third Party (TTP) manages the system and securely provides any node, e.g., Alice or Bob, with private keying materials. Alice can generate a pairwise key with Bob given her own secret keying material and Bob's identity. The full collusion resistance property would ensure that the scheme remains secure even if arbitrarily many devices collude or are compromised.

Our scheme, the HIMMO algorithm, relies on two design concepts: Hiding Information and Mixing Modular Operations. Hiding information is related to the Noisy Interpolation Problem; the Mixing Modular Operations problem seems to be a new hard problem. We describe our scheme, the security of its underlying design principles and give order of magnitude estimations for secure configuration parameters. For these parameters, we show that our prototypic implementation of HIMMO on the 8-bit CPU ATmega128L can generate 128-bit keys in less than 7 ms based on an algorithm fitting in 428 B and with secret keying materials of size 656 B.

Category / Keywords: ID-based symmetric-key generation, collusion resistance, mixing modular operations, noisy interpolation problem.

Date: received 1 Nov 2012, last revised 1 Jul 2013

Contact author: oscar garcia at philips com

Available format(s): PDF | BibTeX Citation

Note: Updated the description including: - better security analysis (formulation of MMO problem in terms of a lattice). - implementation results.

Version: 20130701:150245 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]