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: ia.cr/2016/152 Discussion forum: Show discussion | Start new discussion