In distributed information systems, secure communication between subscribers is implemented using encryption of communication channels. The encryption key exchange problem occurs in this case. Public key encryption algorithms can provide such secure communication. But they require more computing resources and work slowly.Therefore, symmetric encryption schemes are very common. Pairwise key schemes are used to maximize information protection. These schemes use their own key for each subscriber pair. This approach creates additional difficulties in storing and using keys for systems with a large number of subscribers. There are also problems with the scalability the network. Key pre-distribution schemes are used for such systems. In these schemes, the key distribution server sends private key materials to network subscribers via secure channels. Additional subscriber information is in the public domain. Encryption keys are computable. The encryption key is calculated on the basis of closed key materials and open information about subscribers. The existing key pre-distribution schemes are based on the principle of enabling each subscriber to interact with each. However, in most distributed systems, there are restrictions on the transmission of information. As a rule, such restrictions are presented in the form of a ban on the interaction for some subscriber pairs. Such a security policy may be represented as a discretionary access control access matrix. Two key pre-distribution schemes have become most common: the Blom's scheme [1] and the KDP-scheme [2]. These two schemes use a different mathematical approach. The Blom's scheme is based on calculating the values for symmetric polynomial over a finite ring. The KDP-scheme uses finite sets. Blom's scheme is widely
used to secure wireless networks [
The authors have previously modified the key pre-predistribution scheme for mandatory access control [
We are looking at a distributed network with n subscribers. Setting of task consists in organization of secure interaction of network subscribers. Additional conditions are imposed on the interaction of network members. Some subscribers pairs are not allowed to exchange information. For allowed subscriber pairs, messages are exchanged using data encryption. All authorized information channels are two-way. Strict recording this access control is carried out using the access matrix. Rows and columns correspond to network subscribers. The access matrix cells contain one if the channel is allowed and zero if the channel is denied. The task is to generate and distribute closed key materials in such a way that for allowed channels both parties can calculate a common encryption key, and for banned channels the encryption key is zero. We’re putting a limit on the length of the key. The key must be m bits long.
In the basic Blom’s scheme [1], the key distribution server generates a symmetric polynomial f (x; y) of degree 2l with random coefficients. All calculations are performed on the deduction ring ZM . This polynomial is stored in secret on the key generation server and is used to generate key materials. Polynomial degree restrictions are associated with the number of subscribers in the network. If the number of participants is n, then inequality must be performed for the polynomial degree l < n. In addition to secret key materials, the scheme uses open information that is provided by the key distribution server at the subscribers request. The server generates a unique number ri (i = 1; :::; n) for each network subscriber. The numbers ri (i = 1; :::; n) are open. Secure key materials are produced individually for each subscriber. In this scheme, the key materials for the user ui is the polynomial coefficient vector gi(x) = f (x; ri). Secret key materials are transmitted via a secure channel. The value for the function gi(x) is calculated at the point rj to generate the encryption key kij between the subscribers ui and uj (kij = gi(rj )). Subscriber uj performs similar operation (kji = gj (ri)). The equality kij = kji is executed because the polynomial f (x; y) is symmetric. Both members of the information channel receive the same encryption key.
The main security problem of the key pre-distribution scheme is resistance to compromising. ompromising is the ability to obtain the remaining keys by a limited set of known pair encryption keys. The usual Blom scheme is resistant to compromising l keys[1].
. It is necessary that for permitted information channels kij ̸= 0, and for banned kij = 0. A zero key encryption ban is set on the system. This automatically results the discretionary security policy.
We use the list L of subscriber pairs numbers (i; j), for which a ban on creating information channels has been introduced. The total number of ban information channels is denoted s. We are modifying the symmetric polynomial used to produce key materials. We use a polynomial F (x; y) equal to the product of two symmetric polynomials.
F (x; y) = d(x; y)f (x; y): f (x; y) is arbitrary symmetric polynomial with degree 2l.
The symmetric polynomial d(x; y) satisfies a set of requirements.
d(ri; rj ) = 0; d(rj ; ri) = 0; f or (i; j) ∈ L; and d(ri; rj ) ̸= 0; d(rj ; ri) ̸= 0; f or (i; j) ̸∈ L: The polynomial d(x; y) is equal to the product of the polynomials dij (x; y) = 0.
The equality dij (x; y) = 0 is performed only under the condition ((x = ri)∧(y = rj ))∨((x = rj )∧(y = ri)) = 1. From the requirement of symmetry for polynomials dij (x; y) it follows that they are representative through elementary symmetric polynomials. A quadratic function with two roots satisfies the necessary requirements.
dij( 1; 2) = ( 1(x; y) − 1(r1; r2))2 + ( 2(x; y) − 2(r1; r2))2;
Substituting expressions for elementary symmetric polynomials, we obtain the representation the polynomial through the original variables.
dij (x; y) = (x + y − ri − rj )2 + (xy − rirj )2: We write an expression for the polynomial d(x; y).
((x + y − ri − rj )2 + (xy − rirj )2) :
Further work is carried out according to the usual Blom’s scheme algorithm with the replacement the polynomial f (x; y) to the polynomial F (x; y). The degree of the polynomial d(x; y) is determined by the total number banned information channels s. (5) (6) (7) (8) (9) (10) (11) deg d(x; y) = 4s:
Theorem 1. If the key pre-distribution scheme is based on the polynomial f (x; y) of degree 2l and the number of banned information channels is s, then the scheme is resistant to compromising l + 2s key materials.
Theorem 2. If the key pre-distribution scheme is based on the polynomial f (x; y) of degree 2l and the number of banned information channels is s, then compromising the list of protected information channels is possible when compromising at least l + 2s key materials. 3
We consider solving the same problem using a modified KDP-scheme. In a common KDP scheme, the key distribution server sends out a key set K = {k1; :::; km} to all participants over secure channels. This key set is kept secret. A family of subsets S = {S1; :::; Sn} sets {1; 2; :::; n} is stored in open form. Each member of this set family is mapped to one subscribers. If the user ui initiates an information channel with the user uj , then he asks the server subsets Si and Sj . User ui defines the set of elements included in the intersection of sets.
A family of sets S built using such an algorithm meets the security policy requirements.
n Si = ∪ M D[i; j]; (i = 1; :::; n): j=1 Sij = Si ∩ Sj : kij = ⊕ kl:
l2Sij
The set Sij defines the element numbers of the set K used to calculate the pair encryption key. The encryption key is defined as a bitwise XOR operation applied to selected elements of the set K.
All operations are symmetrical, so both participants will receive the same pair key.
The discretionary security policy is described using the access matrix M . Rows and columns of this matrix are associated with network subscribers. The allowed data channels correspond to the unit values in the cells of the access matrix, and the forbidden values are zero. The elements of the subsets family S are selected so that at M [i; j] = 0, the equality Sij = ∅ is fulfilled, and at M [i; j] = 1, Sij ̸= ∅ is performed.
We use the auxiliary set of subsets D to build a family S with the desired properties. The number of elements in the set D is equal to half the number unit elements in the access matrix M . The matrix M is symmetric, therefore, we limit ourselves only to considering the elements above the main diagonal. The elements of the set D are constructed as disjoint subsets of the set {1; 2; :::; n}. The number of elements in D = {D1; :::; Dm} is determined by the number of unit elements above the main diagonal in the matrix M. Enter an additional M D matrix over the set of subsets of the set {1; 2; :::; n}. The value of the elements is determined by the following rule: if M [i; j] = 1, then M D[i; j] = Dk, and M D[j; i] = Dk, if M [i; j] = 0, then M D[i; j] = ∅, and M D[j; i] = ∅. The sets Si are determined based on the elements of the matrix M D arranged in the i-th row.
Modifications the Blom’s and KDP key pre-distribution schemes allow the discretionary security policy implementation for distributed systems. The rights to create information channels are checked automatically when calculating encryption keys and do not require activation the centralized server. The disadvantage of the proposed system is an increase the key materials size in the Blom’s scheme. Key materials contain additional information about banned information channels. [1] 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.