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: ia.cr/2014/698