On Identity-Based-Like Non-Interactive Key Establishment for Key Predistribution Schemes
Alexey Urivskiy · 2020
We consider a problem of making key predistribution schemes more practical through computing pairwise keys non-interactively. For set intersection schemes this problem is reduced to computing a column of the incidence matrix of the scheme in identity-based manner. This will either reduce nodes' storage or communication overhead. We give simple yet computationally efficient procedures for two schemes: the Double-Complement (DC) construction and BAffine.For the 1- and 2-secure schemes based on the DC-construction any column of the incidence matrix can be computed in $O\left( {\log _2^2N} \right)$ operations on O(log2N)-bit numbers for a network of N nodes.For BAffine scheme, which is a composition of the affine plane of prime order q and Blom's scheme, we explicitly present the incidence matrix of the plane, and show that the number of the block of the plane common to any two points can be computed in 6 operations modulo q.Also we prove that the conjecture that the DC-construction could be scaled to a w-secure scheme for an arbitrary w is false. In particular, we show that for any w ≥ 3 and any matrices used in the DC-construction the resulting scheme is insecure.