[Resource Topic] 2016/152: Attacks and parameter choices in HIMMO

Welcome to the resource topic for 2016/152

Attacks and parameter choices in HIMMO

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


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.

ePrint: https://eprint.iacr.org/2016/152

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .