Cryptology ePrint Archive: Report 2014/698

HIMMO - A lightweight collusion-resistant key predistribution scheme

Oscar Garcia-Morchon and Domingo Gomez-Perez and Jaime Gutierrez and Ronald Rietman and Berry Schoenmakers and Ludo Tolhuizen

Abstract: In this paper we introduce HIMMO as a truly practical and lightweight collusion-resistant key predistribution scheme. The scheme is reminiscent ofBlundo et al's elegant key predistribution scheme, in which the master key is a symmetric bivariate polynomial over a finite field, and a unique common key is defined for every pair of nodes as the evaluation of the polynomial at the finite field elements associated with the nodes. Unlike Blundo et al's scheme, however, which completely breaks down once the number of colluding nodes exceeds the degree of the polynomial, the new scheme is designed to tolerateany number of colluding nodes.

Key establishment in HIMMO amounts to the evaluation of a single low-degree univariate polynomial involving reasonably sized numbers, thus exhibiting excellent performance even for constrained devices such as 8-bit CPUs, as we demonstrate. On top of this, the scheme is very versatile, as it not only supports implicit authentication of the nodes like any key predistribution scheme, but also supports identity-based key predistribution in a natural and efficient way. The latter property derives from the fact that HIMMO supports long node identifiers at a reasonable cost, allowing outputs of a collision-resistant hash function to be used as node identifiers. Moreover, HIMMO allows for a transparent way to split the master key between multiple parties.

The new scheme is superior to any of the existing alternatives due to the intricate way it combines the use of multiple symmetric bivariate polynomials evaluated over ``different'' finite rings. We have extensively analyzed the security of HIMMO against two attacks. For these attacks, we have identified the Hiding Information (HI) problem and the Mixing Modular Operations (MMO) problem as the underlying problems. These problems are closely related to some well-defined lattice problems, and therefore the best attacks on HIMMO are dependent on lattice-basis reduction. Based on these connections, we propose concrete values for all relevant parameters, for which we conjecture that the scheme is secure.

Category / Keywords: key predistribution scheme, collusion attack, identity, lattice analysis

Date: received 4 Sep 2014, last revised 18 Aug 2015

Contact author: ludo tolhuizen at philips com

Available format(s): PDF | BibTeX Citation

Note: Results of lattice attacks added.

Version: 20150818:162924 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]