Cryptology ePrint Archive: Report 2016/152

Attacks and parameter choices in HIMMO

Oscar Garcia-Morchon and Ronald Rietman and Ludo Tolhuizen and Jose-Luis Torre-Arce and Moon Sung Lee and Domingo Gomez-Perez and Jaime Gutierrez and Berry Schoenmakers

Abstract: The HIMMO scheme has been introduced as a lightweight collusion-resistant key pre-distribution scheme, with excellent efficiency in terms of bandwidth, energy consumption and computation time. As its cryptanalysis relies on lattice techniques, HIMMO is also an interesting quantum-safe candidate. Unlike the schemes by Blom, by Matsumoto and Imai, and by Blundo {\em et al}, which break down once the number of colluding nodes exceeds a given threshold, it aims at tolerating any number of colluding nodes.

In 2015, a contest for the verification of the scheme was held. During the contest, a method was developed to guess a key by finding an approximate solution of one of the problems underlying the scheme. This attack involves finding a short vector in a lattice of dimension linear in a system parameter $\alpha$ and allowed key recovery for several challenges. Thwarting this attack by increasing $\alpha$ would lead to a significant performance degradation, as CPU and memory requirements for the implementation of the scheme scale quadratically in $\alpha$.

This paper describes a generalization of HIMMO parameters that allows configuring the scheme such that both its performance and the dimension of the lattice involved in the attack grow linearly in $\alpha$. Two attacks inspired by the one developed in the contest are described, and the impact of those attacks for different parameter choices is discussed. Parameters choices are described that thwart existing attacks while enabling high performance implementations of the scheme.

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

Date: received 17 Feb 2016, last revised 18 Feb 2016

Contact author: ludo tolhuizen at philips com

Available format(s): PDF | BibTeX Citation

Version: 20160218:220603 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]