=Paper=
{{Paper
|id=Vol-2928/paper6
|storemode=property
|title=Secret Share Based Key Pre-Distribution Scheme
|pdfUrl=https://ceur-ws.org/Vol-2928/paper6.pdf
|volume=Vol-2928
|authors=Sergey V. Belim,,Svetlana Yu. Belim
}}
==Secret Share Based Key Pre-Distribution Scheme==
https://ceur-ws.org/Vol-2928/paper6.pdf
Secret Share Based Key Pre-Distribution Scheme
Sergey V. Belim 1,2 Svetlana Yu. Belim
1
Omsk State Technical University Omsk State Technical University
11 Mira avenue, 644050, Omsk, Russia 11 Mira avenue, 644050, Omsk, Russia
2
Siberian State Automobile svbelim@gmail.com
and Highway University
5 Mira avenue, 644080, Omsk, Russia
sbelim@mail.ru
Abstract
The key pre-distribution scheme including an encryption key co-
generation protocol is proposed. The key pre-distribution scheme is
formed based on the Blom’s scheme. The Shamir secret sharing thresh-
old 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.
1 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.
2 Basic scheme
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.
F (x) = a2 x2 + a1 x + a0 .
Copyright ⃝
c by the paper’s authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
In: Sergei S. Goncharov, Yuri G. Evtushenko (eds.): Proceedings of the Workshop on Applied Mathematics and Fundamental
Computer Science 2021 , Omsk, Russia, 24-04-2021, published at http://ceur-ws.org
1
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 ∈ Zp . The server generates key materials
for each user.
Key materials for user A are calculated based on numbers x1A , x2A .
k1A = F (x1A ), k2A = F (x2A ).
Key materials for user B are calculated based on numbers x1B , x2B .
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 ).
If user A initiates a communication channel with user B, then he sends him one parts of the secret k1A .
A → B : A, (x1A , 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 .
b0 + b1 x1B + b2 x21B = k1B ,
b0 + b1 x2B + b2 x22B = k2B ,
b0 + b1 x1A + b2 x21A = k1A .
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.
kBA = h(b0 , b1 , b2 ).
User B then sends one part of the secret k1B to user A.
B → A : (x1B , k1B ).
User A compiles and solves a system of linear equations from three unknown c0 , c1 , c2 .
c0 + c1 x1A + c2 x21A = k1A ,
c0 + c1 x2A + c2 x22A = k2A ,
c0 + c1 x1B + c2 x21B = k1B .
User A calculates the common encryption key based on the numbers c0 , c1 , c2 .
kAB = h(c0 , c1 , c2 ).
We prove that both users will receive the same key.
kAB = kBA .
We consider the system of equations for user A.
c0 + c1 x1A + c2 x21A = F (x1A ),
c0 + c1 x2A + c2 x22A = F (x2A ),
c0 + c1 x1B + c2 x21B = F (x1B ).
User A obtains the coefficients of the polynomial F (x) when solving this system of equations.
c0 = a0 , c1 = a1 , c2 = a2 .
2
We consider the system of equations for user B.
b0 + b1 x1B + b2 x21B = F (x1B ),
b0 + b1 x2B + b2 x22B = F (x2B ),
b0 + b1 x1A + b2 x21A = F (x1A ).
User B obtains the coefficients of the polynomial F (x) when solving this system of equations.
b0 = a0 , b1 = a1 , b2 = a2 .
Both users receive the same set of numbers.
b0 = c0 , b1 = c1 , b2 = c2 .
Users receive the same keys.
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 ∈ 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.
F (x, y, z) = F (x, z, y).
This requirement leads to symmetry of polynomials f2 (y, z), f1 (y, z), f0 (y, z) over variables y and z.
f0 (y, z) = f0 (z, y),
f1 (y, z) = f1 (z, y),
f2 (y, z) = f2 (z, y).
The degree of polynomials f2 (y, z), f1 (y, z), f0 (y, z) depends on the number of users. The polynomial coeffi-
cients 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.
r1i (z) = F (x1i , ai , z),
r2i (z) = F (x2i , ai , z).
The server calculates key materials for each user ui (i=1, ..., n). Key materials include two numbers and two
functions.
Key(ui ) = {x1i , x2i , r1i (z), r2i (z)}.
3
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.
q1ij = r1i (aj ),
q2ij = r2i (aj ).
3. The user ui forwards a message to the user uj .
ui → uj : (ui , x1i , q1ij ).
4. The user uj requests ai from the server and calculates two numbers.
q1ji = r1j (ai ),
q2ji = r2j (ai ).
5. The user uj forwards a message to the user ui .
uj → ui : (uj , x1j , q1ji ).
6. The user uj solves a system of linear equations relative to unknown b0 , b1 , b2 .
b2 x21j + b1 x1j + b0 = q1ji ,
b2 x22j + b1 x2j + b0 = q2ji ,
b2 x21i + b1 x1i + b0 = q1ij .
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 .
c2 x21i + c1 x1i + c0 = q1ij ,
c2 x22i + c1 x2i + c0 = q2ij ,
c2 x21j + c1 x1j + c0 = q1ji .
9. The user ui calculates the pair key.
kij = h(c0 , c1 , c2 ).
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 ),
c2 x21i + c1 x1i + c0 = f2 (ai , aj )x21i + f1 (ai , aj )x1i + f0 (ai , aj ),
c2 x22i + c1 x2i + c0 = f2 (ai , aj )x22i + f1 (ai , aj )x2i + f0 (ai , aj ),
c2 x21j + c1 x1j + c0 = f2 (ai , aj )x21j + f1 (ai , aj )x1j + f0 (ai , aj ).
We write this system of equations in matrix form.
2 2
x1i x1i 1 c2 x1i x1i 1 f2 (ai , aj )
x22i x2i 1 c1 = x22i x2i 1 f1 (ai , aj )
x21j x1j 1 c0 x21j x1j 1 f0 (ai , aj )
4
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.
c2 f2 (ai , aj )
c1 = f1 (ai , aj )
c0 f0 (ai , aj )
c2 = f2 (ai , aj ), c1 = f1 (ai , aj ), c0 = f0 (ai , aj ).
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 ),
b2 x21j + b1 x1j + b0 = f2 (aj , ai )x21j + f1 (aj , ai )x1j + f0 (aj , ai ),
b2 x22j + b1 x2j + b0 = f2 (aj , ai )x22j + f1 (aj , ai )x2j + f0 (aj , ai ),
b2 x21i + b1 x1i + b0 = f2 (aj , ai )x21i + f1 (aj , ai )x1i + f0 (aj , ai ).
2
x21j x1j 1 b2 x1j x1j 1 f2 (aj , ai )
x22j x2j 1 b1 = x22j x2j 1 f1 (aj , ai )
x21i x1i 1 b0 x21i x1i 1 f0 (aj , ai )
b2 f2 (aj , ai )
b1 = f1 (aj , ai )
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 .
b0 = c0 = f0 (ai , aj ), b1 = c1 = f1 (ai , aj ), b2 = c2 = f2 (ai , aj ).
Both users receive the same set of numbers. We conclude that the pair keys of both users are equal.
kij = h(c0 , c1 , c2 ) = h(b0 , b1 , b2 ) = kji .
4 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.
References
[1] C.J. Mitchell, . Piper. Key storage in Secure Networks. Discrete and Applied Math, 21:215–228, 1988.
[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.
[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
[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 imple-
mentation. 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.
6