On Some Computational and Security Aspects of the Blom Scheme.

We study some computational and security aspects of the (k, m)-Blom scheme. This key pre-distribution scheme is defined by a symmetric polynomial \( f\left( {x_{ 1} ,x_{ 2} , \ldots ,x_{k} } \right) \) of degree m in each variable over a field Fp and a set of user identifiers \( r_{i} ,r_{i} \in F_{p} ,i\, = \, 1, \ldots ,n \). The pre-shared keys that are distributed to users are the coefficients of the polynomials \( f\left( {r_{i} ,x_{ 2} , \ldots ,x_{k} } \right) \) with distinct users identifiers ri, \( i\, = \, 1, \ldots ,n \). Implementing Stinson’s proof of unconditional security of (2, m)-Blom scheme we get the proof of unconditional security of (k, m)-Blom scheme. We establish that for disclosing of the (k, m)-Blom scheme we do not need to use all coefficients of m + 1 compromised polynomials. We show that for disclosure, it is enough to use just \( \left( {\begin{array}{*{20}c} {m + k} \\ m \\ \end{array} } \right) \) certain coefficients - exactly as many coefficients as there are present in a non-redundant representation of the original polynomial. Additionally, we estimate the number of multiplications in the field Fp sufficient to compute a pre-shared key and the shared key \( f\left( {r_{i} ,r_{ 2} , \ldots ,r_{k} } \right) \) for communication within a privileged group of k users and to find the initial polynomial as well.