Parameter analysis of Blom’s key distribution dynamic scheme

Abstract

Matrix schemes of preliminary key distribution are considered in the paper, they are constructed on the basis of the Blom scheme. Such schemes are used, in particular, in wireless sensor networks and allow effectively changing secret key parameters of a trusted center (TC) when the keys of certain protocol participants are compromised.

The paper presents a modernized Blom matrix scheme. It is assumed that the TC selects an N × N matrix P over a finite field GF (q), where N is the size of the network and q> N. Then, depending on the value of the security parameter t, the first t + 1 rows of the matrix P are taken as an open matrix. The matrix P is public, and it is assumed that any system of t + 1 columns to this matrix is linearly independent. In addition, it is assumed that the TC generates a random (t + 1) × (t + 1) symmetric secret matrix S over GF (q), 16S=X*XT , X is a random matrix of size (t + 1) × (t +1), and computes the matrix 16A=(S.P)T .

If nodes i and j need to set a common key, they first exchange columns from the matrix P and then compute 16Kij  and 16Kji , respectively, using the secret rows of the matrix A.

The probability of coincidence of keys for different pairs of participants is calculated.

Based on the program implementation, the results of computational experiments are presented. In particular, the dependence of the probability of coincidence of the keys of two participants on the protocol parameters (the size of the field and the number of participants) was established experimentally. For q = 1009, the number of key matches for different N values was obtained. Also, the results for the value of N were obtained on the assumption that the maximum of coincidences should be equal to 5.