Introduction

Key pre-distribution schemes are widely used in devices with limited resources. Sensor networks and IoT devices use such schemes. The key pre-distribution scheme reduces the amount of information in the device memory. Devices store key materials. The key distribution server generates key materials and sends them to users through secure communication channels. Users store key materials in secure mode. Cryptographic keys are calculated based on key materials. Key materials and open user information are used to calculate keys. The two key pre-distribution schemes are most widely used. KDP scheme uses set theory [1]. Blom's scheme uses polynomial theory over finite fields [2]. Blom's scheme is actively used in wireless networks [3,4,5]. The KDP scheme is applicable to large networks consisting of subnets [6,7,8].

We highlight one important disadvantage of all key pre-distribution schemes. This disadvantage is the complete trust of users. The user can calculate the encryption key without the consent of another user. Leakage the key information of one user leads to leakage of all keys this user. Other users cannot prevent this leak. We propose a key pre-distribution scheme that includes a participant interaction protocol to generate a common key. This protocol allows other users to block a compromised user.

The server sends key content to users over a secure channel.

S → A : (x 1A , k 1A ), (x 2A , k 2A ), S → B : (x 1B , k 1B ), (x 2B , k 2B ).

If user A initiates a communication channel with user B, then he sends him one parts of the secret k 1A .

A → B : A, (x 1A , k 1A ).

If user B agrees to create a secure information channel, then he compiles and solves a system of linear equations with respect to b

0 , b 1 , b 2 .    b 0 + b 1 x 1B + b 2 x 2 1B = k 1B , b 0 + b 1 x 2B + b 2 x 2 2B = k 2B , b 0 + b 1 x 1A + b 2 x 2 1A = k 1A . User B calculatesk BA = h(b 0 , b 1 , b 2 ).

User B then sends one part of the secret k 1B to user A.

B → A : (x 1B , k 1B ).

User A compiles and solves a system of linear equations from three unknown c 0 , c 1 , c 2 .

   c 0 + c 1 x 1A + c 2 x 2 1A = k 1A , c 0 + c 1 x 2A + c 2 x 2 2A = k 2A , c 0 + c 1 x 1B + c 2 x 2 1B = k 1B .

User A calculates the common encryption key based on the numbers c 0 , c 1 , c 2 .

k AB = h(c 0 , c 1 , c 2 ).

We prove that both users will receive the same key.

k AB = k BA .

We consider the system of equations for user A.

   c 0 + c 1 x 1A + c 2 x 2 1A = F (x 1A ), c 0 + c 1 x 2A + c 2 x 2 2A = F (x 2A ), c 0 + c 1 x 1B + c 2 x 2 1B = F (x 1B ).

User A obtains the coefficients of the polynomial F (x) when solving this system of equations.

c 0 = a 0 , c 1 = a 1 , c 2 = a 2 .

We consider the system of equations for user B.

   b 0 + b 1 x 1B + b 2 x 2 1B = F (x 1B ), b 0 + b 1 x 2B + b 2 x 2 2B = F (x 2B ), b 0 + b 1 x 1A + b 2 x 2 1A = F (x 1A ).

User B obtains the coefficients of the polynomial F (x) when solving this system of equations.

b 0 = a 0 , b 1 = a 1 , b 2 = a 2 .

Both users receive the same set of numbers.

b 0 = c 0 , b 1 = c 1 , b 2 = c 2 .

Users receive the same keys.

k AB = h(c 0 , c 1 , c 2 ) = h(b 0 , b 1 , b 2 ) = k BA .

Protocol reliability is based on a threshold scheme (3,4). Both users, as a result of receiving key materials from the server, own two parts of the secret. Users receive a third part of the secret during messaging. Three parts of the secret allow you to restore the full secret. The attacker has the ability to intercept only messages between users, so he can take possession only two parts of the secret. This information is not sufficient to calculate the encryption key.

Scheme for an arbitrary number of users

We modify our scheme for an arbitrary number of users. All calculations are performed in the ring Z p . p is a prime number. The server generates a unique number a i for each user u i (a i ∈ Z p ). Numbers a i are stored in public on the server. The server ensures that these numbers remain unchanged. The server generates a polynomial from three variables F (x, y, z). The polynomial F (x, y, z) is kept secret. We write the polynomial F (x, y, z) as a polynomial from one variable x with coefficients dependent on the variables y and z. The degree of the polynomial over the variable x is 2.

F (x, y, z) = f 2 (y, z)x 2 + f 1 (y, z)x + f 0 (y, z).

The functions f 2 (y, z), f 1 (y, z), f 0 (y, z) are polynomials. We enter the requirement of symmetry F (x, y, z) over the variables y and z. F (x, y, z) = F (x, z, y).

This requirement leads to symmetry of polynomials f 2 (y, z), f 1 (y, z), f 0 (y, z) over variables y and z.

f 0 (y, z) = f 0 (z, y), f 1 (y, z) = f 1 (z, y), f 2 (y, z) = f 2 (z, y).

The degree of polynomials f 2 (y, z), f 1 (y, z), f 0 (y, z) depends on the number of users. The polynomial coefficients f 2 (y, z), f 1 (y, z), f 0 (y, z) are random numbers.

The server selects two random numbers x 1i and x 2i (i = 1,..., n) for each user u i . All numbers x 1i and x 2i must be unique. The server generates two parts of the secret for each user. Parts of the secret are polynomials from one variable z.

r 1i (z) = F (x 1i , a i , z), r 2i (z) = F (x 2i , a i , z).

The server calculates key materials for each user u i (i=1, ..., n). Key materials include two numbers and two functions.

Key(ui ) = {x 1i , x 2i , r 1i (z), r 2i (z)}.

The polynomials r 1i (z) and r 2i (z) are transmitted as a set of coefficients. The server forwards key content to users via a secure channel.

If the user u i wants to establish a connection with the user u j , then a sequence of nine steps is performed. 1. The user u i requests the number a j from the server. 2. The user u i calculates two numbers.

q 1ij = r 1i (a j ), q 2ij = r 2i (a j ).

3. The user u i forwards a message to the user u j .

u i → u j : (u i , x 1i , q 1ij ).

4. The user u j requests a i from the server and calculates two numbers.

q 1ji = r 1j (a i ), q 2ji = r 2j (a i ).

5. The user u j forwards a message to the user u i .

u j → u i : (u j , x 1j , q 1ji ).

6. The user u j solves a system of linear equations relative to unknown b

0 , b 1 , b 2 .    b 2 x 2 1j + b 1 x 1j + b 0 = q 1ji , b 2 x 2 2j + b 1 x 2j + b 0 = q 2ji , b 2 x 2 1i + b 1 x 1i + b 0 = q 1ij .

7. The user u j calculates the pair key.

k ji = h(b 0 , b 1 , b 2 ).

The function from the three variables h = h(x, y, z) is an open part of the schema and is known to all participants.

8. The user u i solves the system of linear equations with respect to c 0 ,

c 1 , c 2 .    c 2 x 2 1i + c 1 x 1i + c 0 = q 1ij , c 2 x 2 2i + c 1 x 2i + c 0 = q 2ij , c 2 x 2 1j + c 1 x 1j + c 0 = q 1ji .

9. The user u i calculates the pair key.

k ij = h(c 0 , c 1 , c 2 ).

We prove that both users receive the same pair keys. We consider the system of user equations u i .

q 1ij = r 1i (a j ) = F (x 1i , a i , a j ) = f 2 (a i , a j )x 2 1i + f 1 (a i , a j )x 1i + f 0 (a i , a j ), q 2ij = r 2i (a j ) = F (x 2i , a i , a j ) = f 2 (a i , a j )x 2 2i + f 1 (a i , a j )x 2i + f 0 (a i , a j ), q 1ji = r 1j (a i ) = F (x 1j , a j , a i ) = F (x 1j , a i , a j ) = f 2 (a i , a j )x 2 1j + f 1 (a i , a j )x 1j + f 0 (a i , a j ),    c 2 x 2 1i + c 1 x 1i + c 0 = f 2 (a i , a j )x 2 1i + f 1 (a i , a j )x 1i + f 0 (a i , a j ), c 2 x 2 2i + c 1 x 2i + c 0 = f 2 (a i , a j )x 2 2i + f 1 (a i , a j )x 2i + f 0 (a i , a j ), c 2 x 2 1j + c 1 x 1j + c 0 = f 2 (a i , a j )x 2 1j + f 1 (a i , a j )x 1j + f 0 (a i , a j ).

We write this system of equations in matrix form.  

x 2 1i x 1i 1 x 2 2i x 2i 1 x 2 1j x 1j 1     c 2 c 1 c 0   =   x 2 1i x 1i 1 x 2 2i x 2i 1 x 2 1j x 1j 1     f 2 (a i , a j ) f 1 (a i , a j ) f 0 (a i , a j )  

The matrix in equality is a Vandermonde matrix. The Vandermonde determinant is not zero if all x 1i and x 2i are different. Therefore, we conclude that two vectors are equal.

  c 2 c 1 c 0   =   f 2 (a i , a j ) f 1 (a i , a j ) f 0 (a i , a j )   c 2 = f 2 (a i , a j ), c 1 = f 1 (a i , a j ), c 0 = f 0 (a i , a j ).

We consider the system for user equations u j .

q 1ji = r 1j (a i ) = F (x 1j , a j , a i ) = f 2 (a j , a i )x 2 1j + f 1 (a j , a i )x 1j + f 0 (a j , a i ), q 2ji = r 2j (a i ) = F (x 2j , a j , a i ) = f 2 (a j , a i )x 2 2j + f 1 (a j , a i )x 2j + f 0 (a j , a i ), q 1ij = r 1i (a j ) = F (x 1i , a i , a j ) = F (x 1i , a j , a i ) = f 2 (a j , a i )x 2 1i + f 1 (a j , a i )x 1i + f 0 (a j , a i ),    b 2 x 2 1j + b 1 x 1j + b 0 = f 2 (a j , a i )x 2 1j + f 1 (a j , a i )x 1j + f 0 (a j , a i ), b 2 x 2 2j + b 1 x 2j + b 0 = f 2 (a j , a i )x 2 2j + f 1 (a j , a i )x 2j + f 0 (a j , a i ), b 2 x 2 1i + b 1 x 1i + b 0 = f 2 (a j , a i )x 2 1i + f 1 (a j , a i )x 1i + f 0 (a j , a i ).   x 2 1j x 1j 1 x 2 2j x 2j 1 x 2 1i x 1i 1     b 2 b 1 b 0   =   x 2 1j x 1j 1 x 2 2j x 2j 1 x 2 1i x 1i 1     f 2 (a j , a i ) f 1 (a j , a i ) f 0 (a j , a i )     b 2 b 1 b 0   =   f 2 (a j , a i ) f 1 (a j , a i ) f 0 (a j , a i )   b 2 = f 2 (a j , a i ), b 1 = f 1 (a j , a i ), b 0 = f 0 (a j , a i ).

We conclude the equality of numbers from the symmetry of polynomials f 0 , f 1 , f 2 .

b 0 = c 0 = f 0 (a i , a j ), b 1 = c 1 = f 1 (a i , a j ), b 2 = c 2 = f 2 (a i , a j ).

Both users receive the same set of numbers. We conclude that the pair keys of both users are equal.

k ij = h(c 0 , c 1 , c 2 ) = h(b 0 , b 1 , b 2 ) = k ji .

Conclusion

The proposed scheme allows any user to control calculation of communication keys with it. This scheme has a level of compromise resistance equivalent to the Blom's scheme. Users can lock a compromised user without involving the key distribution server.