Linear key predistribution schemes (Q1862446)

The article deals with key predistribution schemes, which enable one to distribute some information among a set of users in such a way that every user of a privileged group is able to compute a common key associated to the group, and no predefined coalition of users outside of the privileged group is able to do so. The authors present a new model for the design of key predistribution schemes based on linear algebraic techniques. They show that the key predistribution schemes constructed from key distribution patterns (e.g. the Fiat-Naor scheme) are linear. The rest of the article is devoted to the construction of the linear key predistribution schemes. Two methods are presented: one based on multilinear functions and the other one on the algebraic concept of duality. Both methods are illustrated with several examples.