Secret Share Based Key Pre-Distribution Scheme

Abstract

The key pre-distribution scheme including an encryption key cogeneration protocol is proposed. The key pre-distribution scheme is formed based on the Blom's scheme. The Shamir secret sharing threshold scheme (3,4) is used for the key generation protocol. The basic scheme and protocol for two users are discussed. Generalization this scheme for an arbitrary number of users is performed. The correctness of the scheme is proved.

Introduction

We propose a protocol first with only two participants A and B. We use Shamir’s scheme to divide the secret [14]. We limit ourselves to a threshold scheme (3; 4). The polynomial F (x) of degree 2 is necessary to implement this scheme. All calculations are performed in the ring Zp. p is a prime number. If user A initiates a communication channel with user B, then he sends him one parts of the secret k1A.

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

User B calculates the common encryption key based on the numbers b0, b1, b2. The function from the three variables h(x; y; z) is used to find the key. This function is open and known to all participants. The coefficients of polynomial a0, a1, a2 are chosen randomly. The polynomial is stored on the key distribution server and is secret. Server selects random numbers x1A, x2A, x1B, x2B 2 Zp. The server generates key materials for each user.

Key materials for user A are calculated based on numbers x1A, x2A.

Key materials for user B are calculated based on numbers x1B, x2B.

k1A = F (x1A); k2A = F (x2A): k1B = F (x1B); k2B = F (x2B):

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

S ! A : (x1A; k1A); (x2A; k2A); S ! B : (x1B; k1B); (x2B; k2B):

A ! B : A; (x1A; k1A): 8 b0 + b1x1B + b2x12B = k1B; < 2

b0 + b1x2B + b2x2B = k2B; : b0 + b1x1A + b2x12A = k1A: kBA = h(b0; b1; b2):

B ! A : (x1B; k1B): 8 c0 + c1x1A + c2x12A = k1A; < 2

c0 + c1x2A + c2x2A = k2A; : c0 + c1x1B + c2x12B = k1B: 8 c0 + c1x1A + c2x12A = F (x1A); < 2

c0 + c1x2A + c2x2A = F (x2A); : c0 + c1x1B + c2x12B = F (x1B): c0 = a0; c1 = a1; c2 = a2:

User B then sends one part of the secret k1B to user A. User A compiles and solves a system of linear equations from three unknown c0, c1, c2.

User A calculates the common encryption key based on the numbers c0, c1, c2.

We prove that both users will receive the same key.

We consider the system of equations for user A.

kAB = h(c0; c1; c2): kAB = kBA: User A obtains the coefficients of the polynomial F (x) when solving this system of equations.

We consider the system of equations for user B.

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

Both users receive the same set of numbers. Users receive the same keys.

8 b0 + b1x1B + b2x12B = F (x1B); < 2

b0 + b1x2B + b2x2B = F (x2B); : b0 + b1x1A + b2x12A = F (x1A): b0 = a0; b1 = a1; b2 = a2: b0 = c0; b1 = c1; b2 = c2: kAB = h(c0; c1; c2) = h(b0; b1; b2) = kBA:

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. 3

Scheme for an arbitrary number of users We modify our scheme for an arbitrary number of users. All calculations are performed in the ring Zp. p is a prime number. The server generates a unique number ai for each user ui (ai 2 Zp). Numbers ai 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) = f2(y; z)x2 + f1(y; z)x + f0(y; z):

The functions f2(y; z), f1(y; z), f0(y; z) are polynomials. We enter the requirement of symmetry F (x; y; z) over the variables y and z.

This requirement leads to symmetry of polynomials f2(y; z), f1(y; z), f0(y; z) over variables y and z.

F (x; y; z) = F (x; z; y): f0(y; z) = f0(z; y); f1(y; z) = f1(z; y); f2(y; z) = f2(z; y): r1i(z) = F (x1i; ai; z); r2i(z) = F (x2i; ai; z):

The degree of polynomials f2(y; z), f1(y; z), f0(y; z) depends on the number of users. The polynomial coefficients f2(y; z), f1(y; z), f0(y; z) are random numbers.

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

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

Key(ui) = fx1i; x2i; r1i(z); r2i(z)g: 8 b2x12j + b1x1j + b0 = q1ji; <

b2x22j + b1x2j + b0 = q2ji; : b2x12i + b1x1i + b0 = q1ij: 8 c2x12i + c1x1i + c0 = q1ij; <

c2x22i + c1x2i + c0 = q2ij; : c2x12j + c1x1j + c0 = q1ji:

kij = h(c0; c1; c2):

The polynomials r1i(z) and r2i(z) are transmitted as a set of coefficients. The server forwards key content to users via a secure channel.

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

3. The user ui forwards a message to the user uj.

4. The user uj requests ai from the server and calculates two numbers.

5. The user uj forwards a message to the user ui.

6. The user uj solves a system of linear equations relative to unknown b0, b1, b2.

7. The user uj calculates the pair key.

kji = h(b0; b1; b2):

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 ui solves the system of linear equations with respect to c0, c1, c2.

9. The user ui calculates the pair key.

We prove that both users receive the same pair keys. We consider the system of user equations ui. q1ij = r1i(aj) = F (x1i; ai; aj) = f2(ai; aj)x21i + f1(ai; aj)x1i + f0(ai; aj); q2ij = r2i(aj) = F (x2i; ai; aj) = f2(ai; aj)x22i + f1(ai; aj)x2i + f0(ai; aj); q1ji = r1j(ai) = F (x1j; aj; ai) = F (x1j; ai; aj) = f2(ai; aj)x21j + f1(ai; aj)x1j + f0(ai; aj); We write this system of equations in matrix form.

8 c2x12i + c1x1i + c0 = f2(ai; aj)x21i + f1(ai; aj)x1i + f0(ai; aj); <

c2x22i + c1x2i + c0 = f2(ai; aj)x22i + f1(ai; aj)x2i + f0(ai; aj); : c2x12j + c1x1j + c0 = f2(ai; aj)x21j + f1(ai; aj)x1j + f0(ai; aj): 0 x1i 2 2 @ x2i

2 x1j x1i 1 1 0 f2(ai; aj) 1 x2i 1 A @ f1(ai; aj) A x1j 1 f0(ai; aj) The matrix in equality is a Vandermonde matrix. The Vandermonde determinant is not zero if all x1i and x2i are different. Therefore, we conclude that two vectors are equal. We consider the system for user equations uj.

q1ji = r1j(ai) = F (x1j; aj; ai) = f2(aj; ai)x21j + f1(aj; ai)x1j + f0(aj; ai); q2ji = r2j(ai) = F (x2j; aj; ai) = f2(aj; ai)x22j + f1(aj; ai)x2j + f0(aj; ai); q1ij = r1i(aj) = F (x1i; ai; aj) = F (x1i; aj; ai) = f2(aj; ai)x21i + f1(aj; ai)x1i + f0(aj; ai); 8 b2x12j + b1x1j + b0 = f2(aj; ai)x21j + f1(aj; ai)x1j + f0(aj; ai); <

b2x22j + b1x2j + b0 = f2(aj; ai)x22j + f1(aj; ai)x2j + f0(aj; ai); : b2x12i + b1x1i + b0 = f2(aj; ai)x21i + f1(aj; ai)x1i + f0(aj; ai): 0 x1j 2 2 @ x2j

2 x1i x1j 1 1 0 f2(aj; ai) 1 x2j 1 A @ f1(aj; ai) A x1i 1 f0(aj; ai) 0 b2 1 0 f2(aj; ai) 1 @ b1 A = @ f1(aj; ai) A

b0 f0(aj; ai) b2 = f2(aj; ai); b1 = f1(aj; ai); b0 = f0(aj; ai):

We conclude the equality of numbers from the symmetry of polynomials f0, f1, f2.

Both users receive the same set of numbers. We conclude that the pair keys of both users are equal. b0 = c0 = f0(ai; aj); b1 = c1 = f1(ai; aj); b2 = c2 = f2(ai; aj):

kij = h(c0; c1; c2) = h(b0; b1; b2) = kji: 4

Conclusion References

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. [2] R. Blom. An optimal class of symmetric key generation systems. Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques:335-338, 1985.

References

[1] C.J. Mitchell , . Piper. Key storage in Secure Networks . Discrete and Applied Math , 21 : 215 - 228 , 1988 .

[3] E. Shi , A. Perrig . Designing secure sensor networks . IEEE Wireless Communications , 11 ( 6 ): 38 - 43 , 2004 .

[4] Y. Liang , H. V. Poor , S. Shamai . Information Theoretic Security. Found. Trends Commun. Inf. Theory , 5 : 355 - 580 , 2009 .

[5] A. Parakh , S. Kak . Matrix based key agreement algorithms for sensor networks . Fifth IEEE In-ternational Conference on Advanced Telecommunication Systems and Networks (ANTS):1-3 , 2011 .

[6] Y. Liu , M. Dong , K. Ota , A. Liu. ActiveTrust: secure and trustable routing in wireless sensor net-works . IEEE Transactions on Information Forensics and Security , 11 ( 9 ): 2013 - 2027 , 2016 .

[7] D. Zhao , K.-W. Chin , R. Raad . Approximation algorithms for broadcasting in duty cycled wire-less sensor networks . Wireless Networks , 20 ( 8 ): 2219 - 2236 , 2014 .

[8] X. Zheng , J. Wang , W. Dong , Y. He , Y. Liu . Bulk data dissemination in wireless sensor networks: analysis, implications and improvement . IEEE Transactions on Computers , 65 ( 5 ): 1428 - 1439 , 2016 .

[9] S.V. Belim , S. Yu . Belim. Mandatory access control implementation in the distributed systems . Automatic Control and Computer Sciences , 52 ( 8 ): 1124 - 1126 , 2018 .

[10] S.V. Belim , S.Yu. Belim. The modification of Blom's key predistribution scheme, taken into account simplex channels . Automatic Control and Computer Sciences , 52 ( 8 ): 1134 - 1137 , 2018 .

[11] S.V. Belim , S. Yu . Belim. Implementation of simplex channels in the Blom's keys pre-distribution scheme . Journal of Physics: Conf. Series , 1210 : 012008 , 2019 .

[12] S.V. Belim , S. Yu . Belim. Use the keys pre-distribution KDP-scheme for mandatory access control implementation . Journal of Physics: Conf. Series , 1210 : 012009 , 2019 .

[13] S.V. Belim , S. Yu . Belim. Vector key pre-distribution scheme . Journal of Physics: Conf. Series , 1441 : 012033 , 2020 .

[14] A. Shamir . How to share a secret . Commun. ACM , 22 ( 11 ): 612 - 613 , 1979 .