Sage Journals: Discover world-class research

Abstract

The mobile agent is functioning as an information exchanger with hosts. In order to reduce the communication time that the host sent to the members of a large system. This article proposes to use a function defined by Lagrange polynomial to compute decryption key. Each host will be given a decryption key to access the confidential document by inputting a secret key into an interpolation function which is generated from Lagrange interpolation. Since tasks are done by the mobile agent, the whole process will be performed within a short time period because there is no physical connection between the end devices. The information exchange occurs at the end hosts.

Keywords

Mobile agent Lagrange interpolation access control key management heterogeneous systems

Introduction

This article tends to develop a security scheme with mobile agents and Lagrange interpolation method. With this scheme, the network delay would be significantly reduced. However, the mobile agents can develop their own protocols to interact with the hosts of other agents and roam across heterogeneous systems. Otherwise, it is able to work across various systems and solve the difficulty of integrating heterogeneous systems.

We have reviewed several published key management designs associated with interpolation polynomials. In addition, the security scheme could reduce the network delay and improve the computation process, ensuring the overall mechanism security. Moreover, this scheme would generate the computation processes’ time curve charts and show the mathematical derivations.

Previous work

From the previous work, Shen and Chen¹ proposed a scheme in 2002 to have each class obtain a public and a private key for access purposes. This scheme was developed based on discrete logarithm² and Newton’s polynomial interpolation.³ However, the scheme is not good enough for security. In the following year, Hsu and Wu⁴ pointed out the security flaws of Shen et al.’s scheme in which if there are two classes with the same immediate successor, any successor is able to access another which is not authorized to obtain the data. Das et al.⁵ proposed a solution in 2005 to remedy the security defects of Shen et al.’s scheme. A lot of related works have been proposed to solve access control problems.^6–8

Based on discrete logarithm and Newton’s interpolation method, Chang et al.⁹ proposed a cryptographic key assignment scheme in 2004 to solve the access control problem in partially ordered user hierarchy. However, double encryption problem occurs in his scheme. The security level is the same as single encryption. For Das et al.’s scheme, it uses an encryption system to generate a secret key SK_i for each security class. If SC_j ≤ SC_i, SC_i can obtain its secret key and derive SC_j’s secret key directly instead of obtaining a decryption key of an authorized file. According to Das et al.’s⁵ scheme, SC_i can use his own secret key SK_i to derive the decryption key DK_j. This approach is extremely insecure and may infringe upon personal privacy. In this article, for example, it derives a file’s decryption key DK_j using the secret key SK_i. The way Das et al. used was suspicious in personal privacy which was extremely insecure.

Based on interpolation polynomial,¹⁰ Das et al.⁵ and Chang et al.⁹ offered key management schemes. Those schemes have to be improved in terms of effectiveness and security performance. In contrast, in this research a scheme that was more efficient is proposed since it needs only fewer modules. The essence of the scheme is that the key generation and derivation require much amount of time to complete.

Proposed scheme

The Lagrange interpolation method will be used to retain the decryption keys for confidential documents by mobile agents for the authorized hosts, which is applied to organizations with no definite hierarchical structure relationships among their departments of sectors. Not only is the Lagrange interpolation an encryption–decryption algorithm, but it also provides a mathematical framework to build a secure key management scheme as well. This mathematical feature is used to establish a set of equations for our proposed scheme. We further implement the ElGamal public key system to enhance security concerns. In our proposed scheme, the mobile agents obtain the encryption key DK_t of a confidential document for an authorized host SC_i by substituting the secret key SK_i of the host SC_i an interpolation function $F_{D K_{t}} (x)$ .

Key generation phase

The mobile agent is designed to obtain and manage the decryption keys DK_t for each confidential file. Besides, the mobile agent is used to check the authenticity of the class’s secret key SK_i for checking the authenticity of the class’s secret key when required. The theme of our scheme is shown as follows:

Step 1. The mobile agent randomly selects a big prime number p = 2p′+1, where p′ is also a big prime number. Then, the chosen g is a root of Galois field GF(p) and makes g, p, and p′ public.

Step 2. The mobile agent selects different decryption keys DKt (t = 1, 2, …, m, with m being the number of decryption keys in the mobile agent) for each confidential document, where DK_t and p – 1 are relatively prime.

Step 3. The mobile agent selects different secret keys SK_i (i = 1, 2, …, n, with n being the number of visited hosts), where SK_i and p – 1 are relatively prime and SK_i is private.

Step 4. The interpolation function is established as follows

F_{D K_{t}} (x) = x \times D K_{t} \times \sum_{D K_{t} \leq S C_{i}} x_{i, t}^{- 1} l_{i, t} (x)

where $l_{i, j} (x)$ is the Lagrange interpolation polynomial

\begin{array}{l} l_{i, t} (x) = \prod_{s = 1, s \neq i}^{n} \frac{x - x_{s, t}}{x_{i, t} - x_{s, t}} = (\frac{x - x_{1, t}}{x_{i, t} - x_{1, t}}) \\ \dots (\frac{x - x_{s - 1, t}}{x_{i, t} - x_{s - 1, t}}) (\frac{x - x_{s + 1, t}}{x_{i, t} - x_{s + 1, t}}) \\ \dots (\frac{x - x_{n, t}}{x_{i, t} - x_{n, t}}) \end{array}

In the above formula, $D K_{t} \leq S C_{i}$ means that SC_i is authorized to access the confidential document t which is encrypted using the encryption key DK_t; $x_{s, t} = I D_{t} | | g^{S K_{s}} (\mod p)$ , where ID_t is the identity of the confidential document and || is the concatenation operator.

Example

Suppose that a confidential document, the encryption key of which is DK_t that is kept in a mobile agent, is to be transmitted to an assigned department (see Figure 1). A person with authorized access can substitute the secret key, SC_i, into the interpolation function to obtain the corresponding decryption key. The detailed procedure of encryption and decryption is shown below.

Figure 1.

Hierarchical structure in the access control.

In the process of encryption, certificate authority (CA) first establishes and makes public the function $F_{D K_{5}} (x)$ of DK₅, then calculates the interpolation function, and finally substitutes $x_{i, j} = I D_{j} | | g^{S K_{i}} (\mod p)$ into the interpolation function

\begin{matrix} l_{1, 5} (x) & = (\frac{x - x_{2, 5}}{x_{1, 5} - x_{2, 5}}) (\frac{x - x_{3, 5}}{x_{1, 5} - x_{3, 5}}) (\frac{x - x_{4, 5}}{x_{1, 5} - x_{4, 5}}) (\frac{x - x_{5, 5}}{x_{1, 5} - x_{5, 5}}) (\frac{x - x_{6, 5}}{x_{1, 5} - x_{6, 5}}) \\ = \frac{x - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{3}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{6}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{6}} (\mod p)} \\ l_{3, 5} (x) & = (\frac{x - x_{1, 5}}{x_{3, 5} - x_{1, 5}}) (\frac{x - x_{2, 5}}{x_{3, 5} - x_{2, 5}}) (\frac{x - x_{4, 5}}{x_{3, 5} - x_{4, 5}}) (\frac{x - x_{5, 5}}{x_{3, 5} - x_{5, 5}}) (\frac{x - x_{6, 5}}{x_{3, 5} - x_{6, 5}}) \\ = \frac{x - I D_{5} | | g^{S K_{1}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{1}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{6}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{6}} (\mod p)} \\ l_{6, 5} (x) & = (\frac{x - x_{1, 5}}{x_{6, 5} - x_{1, 5}}) (\frac{x - x_{2, 5}}{x_{6, 5} - x_{2, 5}}) (\frac{x - x_{3, 5}}{x_{6, 5} - x_{3, 5}}) (\frac{x - x_{4, 5}}{x_{6, 5} - x_{4, 5}}) (\frac{x - x_{5, 5}}{x_{6, 5} - x_{5, 5}}) \\ = & \frac{x - I D_{5} | | g^{S K_{1}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{1}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{3}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)} \times \frac{x - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \\ \times \frac{x - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \end{matrix}

The interpolation function is thus obtaining

F_{D K_{5}} (x) = x \times D K_{5} \times {{(x_{1, 5})}^{- 1} l_{1, 5} (x) + {(x_{3, 5})}^{- 1} l_{3, 5} (x) + {(x_{6, 5})}^{- 1} l_{6, 5} (x)}

When security class 3 wishes to obtain the decryption key DK₅, $x_{3, 5} = I D_{5} | | g^{S K_{3}} (\mod p)$ is substituted into $F_{D K_{5}} (x)$

\begin{matrix} l_{1, 5} (x_{3, 5}) & = (\frac{x_{3, 5} - x_{2, 5}}{x_{1, 5} - x_{2, 5}}) (\frac{x_{3, 5} - x_{3, 5}}{x_{1, 5} - x_{3, 5}}) (\frac{x_{3, 5} - x_{4, 5}}{x_{1, 5} - x_{4, 5}}) (\frac{x_{3, 5} - x_{5, 5}}{x_{1, 5} - x_{5, 5}}) (\frac{x_{3, 5} - x_{6, 5}}{x_{1, 5} - x_{6, 5}}) \\ = \frac{x_{3, 5} - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)} \\ \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \\ \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{6}} (\mod p)}{I D_{5} | | g^{S K_{1}} (\mod p) - I D_{5} | | g^{S K_{6}} (\mod p)} \\ = 0 \\ l_{3, 5} (x_{3, 5}) & = (\frac{x_{3, 5} - x_{1, 5}}{x_{3, 5} - x_{1, 5}}) (\frac{x_{3, 5} - x_{2, 5}}{x_{3, 5} - x_{2, 5}}) (\frac{x_{3, 5} - x_{4, 5}}{x_{3, 5} - x_{4, 5}}) (\frac{x_{3, 5} - x_{5, 5}}{x_{3, 5} - x_{5, 5}}) (\frac{x_{3, 5} - x_{6, 5}}{x_{3, 5} - x_{6, 5}}) \\ = \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{1}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{1}} (\mod p)} \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \\ \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \\ \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{6}} (\mod p)}{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{6}} (\mod p)} \\ = 1 \\ l_{6, 5} (x_{3, 5}) & = (\frac{x_{3, 5} - x_{1, 5}}{x_{6, 5} - x_{1, 5}}) (\frac{x_{3, 5} - x_{2, 5}}{x_{6, 5} - x_{2, 5}}) (\frac{x_{3, 5} - x_{3, 5}}{x_{6, 5} - x_{3, 5}}) (\frac{x_{3, 5} - x_{4, 5}}{x_{6, 5} - x_{4, 5}}) (\frac{x_{3, 5} - x_{5, 5}}{x_{6, 5} - x_{5, 5}}) \\ = \frac{x_{3, 5} - I D_{5} | | g^{S K_{1}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{1}} (\mod p)} \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{2}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{2}} (\mod p)} \\ \times \frac{I D_{5} | | g^{S K_{3}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{3}} (\mod p)} \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{4}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{4}} (\mod p)} \\ \times \frac{x_{3, 5} - I D_{5} | | g^{S K_{5}} (\mod p)}{I D_{5} | | g^{S K_{6}} (\mod p) - I D_{5} | | g^{S K_{5}} (\mod p)} \\ = 0 \end{matrix}

$F_{D K_{5}} (x_{3, 5})$ yields the decryption key DK₅

\begin{matrix} F_{D K_{5}} (x_{3, 5}) & = x_{3, 5} \times D K_{5} \times {{(x_{1, 5})}^{- 1} l_{1, 5} (x) + {(x_{3, 5})}^{- 1} l_{3, 5} (x) + {(x_{6, 5})}^{- 1} l_{6, 5} (x)} \\ = I D_{5} | | g^{S K_{3}} (\mod p) \times D K_{5} \times {\begin{matrix} {(I D_{5} | | g^{S K_{1}} (\mod p))}^{- 1} \times 0 \\ + {(I D_{5} | | g^{S K_{3}} (\mod p))}^{- 1} \times 1 \\ + {(I D_{5} | | g^{S K_{6}} (\mod p))}^{- 1} \times 0 \end{matrix}} \\ = I D_{5} | | g^{S K_{3}} (\mod p) \times D K_{5} \times {(I D_{5} | | g^{S K_{3}} (\mod p))}^{- 1} \\ = D K_{5} \end{matrix}

Key derivation phase

Step 1. Set the right of the host S_i to access a certain DK_t.

Step 2.The security class SC_i uses its secret key SK_i and the public function F_DKt(x) to obtain DK_t.

Analysis of security

We would go over the security analyses of the Lagrange interpolation method in the context of common external attacks, reversed attacks, cooperative attacks, and many other sources of attacks. In addition, we would discuss from the viewpoint of attackers to compromise the proposed scheme to ensure that the method is secure.

External attacks

The attackers steal from outside. They hack valuable information to accumulate money. This situation could result in the divulgence of confidential information and damages. Accordingly, this becomes a serious issue in the process of security analyses.

Regarding external attack, attackers with the knowledge of public parameters are not able to obtain any decryption key DK_t and, consequently, are not able to obtain any confidential file. If the external attackers wish to extract the secret key SK_i from the interpolation function parameters $x_{i, j} = I D_{j} | | g^{S K_{i}} (\mod p)$ , then they have to solve the discrete logarithm problem, which is known to be computationally infeasible since p is a large prime.

The interpolation function $F_{D K_{5}} (x)$ itself must have certain security levels since the function $F_{D K_{5}} (x)$ is used to generate the decryption key DK_t for authorized hosts. We assume that the attacker tends to obtain the decryption key DK₂ by solving the interpolation function. The attacker may first study the $l_{1, 2} (x)$ component of $F_{D K_{2}} (x)$ . Since the public parameters p and g are the only known information to the attackers, they cannot so successfully hack the information. Thus, the attacker gets nothing from the study of $l_{1, 2} (x)$ . Similarly, the attacker gains nothing by studying the other components of $F_{D K_{2}} (x)$ ; in other words, there is built-in security in the interpolation function $F_{D K_{5}} (x)$ and an analysis of $F_{D K_{5}} (x)$ reveals no information about the secret key SK_i and the decryption key DK_t.

Reversed attacks

The reversed attack is defined as a process in which the user with lower authority intends to access the higher level. Referring to Figure 2, SC_j stands for a user with lower authority and SC_i is the user with higher authority. If a user successfully carries out a reversed attack on a user who has higher authority, then the attacker could illegally obtain the secret key to access to the confidential documents. After hacking the information successfully, the attackers may tend to sell it which would result in loss to the organization. It is thus important to prevent reversed attack.

Figure 2.

Reversed attacks.

Regarding the method proposed, we note that

l_{i, t} (x) = Π_{s = 1, s \neq i}^{n} \frac{x - x_{s, t}}{x_{i, t} - x_{s, t}} = (\frac{x - x_{1, t}}{x_{i, t} - x_{1, t}}) \dots (\frac{x - x_{s - 1, t}}{x_{i, t} - x_{s - 1, t}}) (\frac{x - x_{s + 1, t}}{x_{i, t} - x_{s + 1, t}}) \dots (\frac{x - x_{n, t}}{x_{i, t} - x_{n, t}})

Since the secret keys SK_i in the parameters $x_{i, t} = I D_{t} | | g^{S K_{i}} (\mod p)$ are not related, the user with lower authority does not have the knowledge of enough parameters to derive the secret key of a user of higher authority.

Cooperative attacks

Cooperative attack means that a group of users try to cooperatively obtain the secret key of a user with higher access in the organization. Referring to Figure 3, SC_j and SC_k stand for users with lower authority and SC_i for users with higher authority. Cooperative attack can therefore be concerned as several reversed attacks assembled together. Comparing with reversed attacks, there is more internal participation involved since attacks can pool the knowledge of their own secret keys.

Figure 3.

Cooperative attacks.

As far as this problem is concerned, the secret keys should be randomly selected. It could remove the regularity among the secret keys and the possibility of deriving the secret key based on the knowledge of a set of other secret keys.

Since the method proposed applies to the organization without a definite hierarchical structure, the security classes can be viewed as independent units, so that the secret key of one security class cannot be obtained by a reversed attack carried out by a single user or by a cooperative attack carried out by a group of users.

By an analysis of the interpolation function $F_{D K_{t}} (x) = xD K_{t} \sum_{D K_{t} \leq S_{i}} x_{i, j}^{- 1} l_{i, j} (x)$ , it is seen that a compromise in security is most likely to lie in the parameter $l_{i, t} (x)$ . Taking $l_{1, 2} (x)$ , for example, we have

\begin{matrix} l_{1, 2} (x) & = (\frac{x - x_{2, 2}}{x_{1, 2} - x_{2, 2}}) (\frac{x - x_{3, 2}}{x_{1, 2} - x_{3, 2}}) (\frac{x - x_{4, 2}}{x_{1, 2} - x_{4, 2}}) \\ (\frac{x - x_{5, 2}}{x_{1, 2} - x_{5, 2}}) (\frac{x - x_{6, 2}}{x_{1, 2} - x_{6, 2}}) \\ = \frac{x - I D_{2} | | g^{S K_{2}} (\mod p)}{I D_{2} | | g^{S K_{1}} (\mod p) - I D_{2} | | g^{S K_{2}} (\mod p)} \\ \times \frac{x - I D_{2} | | g^{S K_{3}} (\mod p)}{I D_{2} | | g^{S K_{1}} (\mod p) - I D_{2} | | g^{S K_{3}} (\mod p)} \\ \times \frac{x - I D_{2} | | g^{S K_{4}} (\mod p)}{I D_{2} | | g^{S K_{1}} (\mod p) - I D_{2} | | g^{S K_{4}} (\mod p)} \\ \times \frac{x - I D_{2} | | g^{S K_{5}} (\mod p)}{I D_{2} | | g^{S K_{1}} (\mod p) - I D_{2} | | g^{S K_{5}} (\mod p)} \\ \times \frac{x - I D_{2} | | g^{S K_{6}} (\mod p)}{I D_{2} | | g^{S K_{1}} (\mod p) - I D_{2} | | g^{S K_{6}} (\mod p)} \end{matrix}

In the above expression, SK₂, …, SK₆ are unknown to the attackers. Suppose that SK₂ stands for the secret key that cooperative attackers wish to obtain. Assume that the owners of SK₃, …, SK₆ are the cooperative attackers. With the knowledge of SK₃, …, SK₆, the cooperative attackers are not able to extract SK₂ from $x_{2, 2} = I D_{2} | | g^{S K_{2}} (\mod p)$ due to the difficulty of solving a discrete logarithm problem. Hence, using a large prime p in the formation of $g^{S K_{i}} \mod p$ , our proposed method is secure and the cooperative attacks can be prevented effectively.

Equation attacks

In an equation attack, the attackers attempt to obtain the secret key of a user by analyzing a known equation.

Referring to Figure 3, SC₁ and SC₂ can derive the key DK₂ through the interpolation function $F_{D K_{2}} (x)$ by replacing x with x_1,2 and x_2,2, respectively. We now consider if SC₂ can derive the secret key SK₁ of SC₁ by utilizing the knowledge of public parameters, his own secret key SK₂, and analyzing the interpolation function $F_{D K_{2}} (x)$ . An analysis of the interpolation function $F_{D K_{2}} (x)$ yields

\begin{matrix} F_{D K_{2}} (x_{2, 2}) = x_{2, 2} D K_{2} \sum_{D K_{2} \leq S C_{i}} x_{i, 2}^{- 1} l_{i, 2} (x_{2, 2}) \\ \Rightarrow F_{D K_{2}} (x_{2, 2}) {DK}_{2}^{- 1} = x_{2, 2} \sum_{D K_{2} \leq S C_{i}} {(x_{i, 2})}^{- 1} l_{i, 2} (x_{2, 2}) \\ \Rightarrow F_{D K_{2}} (x_{2, 2}) {DK}_{2}^{- 1} \\ = x_{2, 2} {{(x_{1, 2})}^{- 1} l_{1, 2} (x_{2, 2}) + {(x_{2, 2})}^{- 1} l_{2, 2} (x_{2, 2}) + {(x_{4, 2})}^{- 1} l_{4, 2} (x_{2, 2})} \end{matrix}

On the right-hand side of the above equation, only the $l_{2, 2} (x_{2, 2})$ term is 1 and the other two terms are 0. SC₂ cannot obtain the parameter $x_{1, 2} = I D_{2} | | g^{S K_{1}} (\mod p)$ from the equation of $F_{D K_{2}} (x)$ . Even if SC₂ somehow manages to obtain the value of x_1,2, it still has to solve the difficult problem of extracting SK₁. This analysis shows that our proposed method is secure against equation attack.

Analysis of performance

We would address the computational overheads and storage in this subsection. Most of the published schemes associated with the Lagrange interpolation method did not follow an environment structure adopted by our proposed scheme. As a result, we compare our proposed scheme with those of Das et al.⁵ and Chang et al.⁹ since these two schemes follow a similar structure. It is shown in Knuth¹¹ that the process of interpolation (k+1) points using Newton’s formula requires (k²+k)/2 divisions and k²+k subtractions, where k is the degree of the interpolating polynomial.

As for the evaluation of the polynomial to derive the successor’s secret key, we can base on the knowledge of Knuth;¹¹ (2k – 1) multiplications, 2k additions, and one modular operation are demanded by applying Horner’s rule.

Therefore, our proposed scheme requires a computation time of $2 T_{MUL} + \sum_{1 \leq i \leq k} v_{i} (T_{l} + T_{INV}) + k T_{\exp}$ to generate the access functions F_DKt(x) in the key generation phase, where T_l is the computation time for evaluating an interpolating polynomial. In the key derivation phase of our proposed scheme, a computation time of v_iTexp is required for computing $g^{S K_{i}} \mod p$ and a computing time of mT_l is required for evaluating F_DKt(x). Hence, a computation time of v_iT_exp+mT_l is required in the key derivation phase. A computation time for $(k + \sum_{1 \leq i \leq k} v_{i}) T_{\exp} + (\sum_{1 \leq i \leq k} v_{i} + m) T_{l} + \sum_{1 \leq i \leq k} v_{i} T_{INV} + 2 T_{MUL}$ is thus required for the key generation phase and the key derivation phase of our proposed scheme.

The scheme of Chang et al.,⁹ which utilizes Newton’s interpolation formula, requires a computation time of $\sum_{1 \leq i \leq k} v_{i} T_{l} + (2 \sum_{1 \leq i \leq k} v_{i} + k) T_{\exp} + k T_{INV}$ to create the interpolating polynomials H_i(x) and the parameters $V_{i} = E_{i}^{K_{i}^{- 1}} (\mod p)$ in the key generation phase. In the key derivation phase, a computation time of $v_{i} T_{\exp} + k T_{l}$ is required for computing $x_{j} = K_{i}^{- I D_{i}} (\mod p)$ and $y_{j} = H_{i} (x_{j})$ and a computation time of $v_{i} T_{\exp} + m T_{\exp}$ is required for computing $K_{j} = y_{j}^{K_{i}} (\mod p)$ and $E_{j} = V_{j}^{K_{j}} (\mod p)$ . Hence, a computation time of $(4 \sum_{1 \leq i \leq k} v_{i} + k + m) T_{\exp} + (\sum_{1 \leq i \leq k} v_{i} + k) T_{l} + k T_{INV}$ is required for the key generation phase and the key derivation phase of the scheme of Chang et al. We notice that the most time-consuming operation used in constructing the scheme of Chang et al. is modular exponentiation.

Following the same line of reasoning, the computation times for the key generation phase and the key derivation phase of the scheme of Das et al.⁵ are given, respectively, by $(\sum_{1 \leq i \leq k} v_{i}) T_{l} + \sum_{1 \leq i \leq k} v_{i} T_{INV} + (\sum_{1 \leq i \leq k} v_{i}) T_{hash}$ and $k T_{l} + v_{i} T_{hash}$ . Hence, a computation time of $(\sum_{1 \leq i \leq k} v_{i} + k) T_{l} + \sum_{1 \leq i \leq k} v_{i} T_{INV} + (3 \sum_{1 \leq i \leq k} v_{i}) T_{hash}$ is required for the key generation phase and derivation phase of the scheme of Das et al.⁵

We now consider the storage space required by each of the three schemes under comparison. For our proposed scheme, a storage space of (m+2)len is required for the public parameters and a storage space of len is required for each private key SK_i of user SC_i. For the scheme of Chang et al., a storage space of (2k+1)len is required for the public parameters V_i, H_i(x), and p. A storage space of length len is required for each private key K_i.

For the scheme of Das et al.,⁵ a storage space of (k+m)len is needed for the public parameters ID_j and H_i(x) and a storage space of len is required for each private key. Since the number of security classes (k) is larger than the number of confidential files (m), our proposed scheme requires a smaller storage space than the other two schemes for most of the time.

We notice that the key operation^12–14 used in constructing the three schemes under comparison is the same: modular exponentiation. The computational complexity of the schemes by Chang et al.⁹ and Das et al.⁵ is O(k²) in the number of modular hashing. The computational complexity of our proposed scheme is O(k²) in the number of modular exponentiation. The complexity and the storage requirement of the three schemes under comparison are listed in Table 1.

Table 1.

Analysis of computational complexity.

	Key generation/derivation	Complexity	Storage of public parameters	Storage of private keys
Chang et al.⁹	$\begin{matrix} (4 \sum_{1 \leq i \leq k} v_{i} + k + m) T_{\exp} \\ + (\sum_{1 \leq i \leq k} v_{i} + k) T_{l} + k T_{INV} \end{matrix}$	O(k²) in modular exponentiation	(2k + 1)len	len
Das et al.⁵	$\begin{matrix} (\sum_{1 \leq i \leq k} v_{i} + k) T_{l} \\ + \sum_{1 \leq i \leq k} v_{i} T_{INV} + (2 \sum_{1 \leq i \leq k} v_{i}) T_{hash} \end{matrix}$	O(k²) in hashing	(k + m)len	len
The proposed scheme	$\begin{matrix} (k + \sum_{1 \leq i \leq k} v_{i} \sum_{1 \leq i \leq k} v_{i}) T_{\exp} \\ + (\sum_{1 \leq i \leq k} v_{i} + m) T_{l} \\ + \sum_{1 \leq i \leq k} v_{i} T_{INV} + 2 T_{MUL} \end{matrix}$	O(k²) in modular exponentiation	(m + 2)len	len

We now conduct a numerical experiment to compare the performance in terms of the computation time required by the key generation and derivation phases. Figure 4 shows the different computation times for the key generation phase of the three schemes versus the number of members of the hierarchy. The computation times for the proposed scheme, the scheme of Das et al., and the scheme of Chang et al. are shown using red, blue, and green lines, respectively. As the number of members reaches 1200, the computation times for the proposed scheme, the scheme of Das et al., and the scheme of Chang et al. are, respectively, 33.76, 29.94, and 43.02 s. We notice that the scheme of Das et al. consistently requires a smaller computation time than the proposed scheme, but the proposed scheme is better than the scheme of Chang et al.’s. This can be explained by the fact that the scheme of Das et al. uses a symmetric encryption/decryption algorithm to protect the secret keys and the proposed method and, on the other hand, uses an asymmetric encryption/decryption algorithm. Since a symmetric encryption/decryption algorithm is “faster” than an asymmetric encryption/decryption algorithm, it does not come as a surprise that the scheme of Das et al. outperforms the proposed scheme. However, we remark that an asymmetric encryption/decryption algorithm generally provides better security than a symmetric encryption/decryption algorithm.

Figure 4.

Key generation phase.

We now consider the computation times required by the key derivation phase for the three schemes under comparison. The plots of the computation times that follow a structure similar to that shown in Figure 4 are presented in Figure 5. Again, the scheme of Chang et al. always required the highest computation time. The proposed scheme is slightly better than the scheme of Das et al. As explained in the previous paragraph, this is due to the difference in the efficiency of a symmetric encryption/decryption algorithm and an asymmetric encryption/decryption algorithm.

Figure 5.

Key derivation phase.

Conclusion

We tend to develop a key management scheme to improve the security concern in data access. With the technology of mobile agents, we can easily build a hierarchical access control. On the other hand, the Lagrange interpolation and access control schemes provide management ability, and the classification and control of secure hierarchy are carried out. Moreover, the Lagrange interpolation method provides features of easy calculation and compromise resistance. To secure data access management efficiently, we implement mobile agents to confidential files across the system. Certain types of attacks are addressed. It is shown that our proposed method is secure against external attacks, reverse attacks, cooperative attacks, and equation attacks.

Footnotes

Handling Editor: Pascal Lorenz

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Science & Technology Planning Fund of Quanzhou (No. 2016T009) and the Natural Science Foundation of Fujian Province of China (No. 2017J01109).

ORCID iD

Tsung-Chih Hsiao

References

Shen

VRL

Chen

. A novel key management scheme based on discrete logarithms and polynomial interpolations. Comput Secur 2002; 21(2): 164–171.

Diffie

Hellman

ME.

New directions in cryptography. Inform Theory 1976; 22(6): 644–654.

Scarborough

Hilsenrath

. Numerical mathematical analysis. Baltimore: Johns Hopkins Press, 1955.

Hsu

TS.

Cryptanalyses and improvements of two cryptographic key assignment schemes for dynamic access control in a user hierarchy. Comput Secur 2003; 22(5): 453–456.

Das

Saxena

Gulati

et al . Hierarchical key management scheme using polynomial interpolation. SIGOPS Oper Syst Rev 2005; 39(1): 40–47.

Chao

Tsai

Hwang

MS.

An improved key-management scheme for hierarchical access control. Int J Network Secur 2017; 19(4): 639–643.

Tang

Huang

et al . Achieving simple, secure and efficient hierarchical access control in cloud computing. IEEE T Comput 2016; 65(7): 2325–2331.

Castiglione

Santis

Masucci

et al . Cryptographic hierarchical access control for dynamic structures. IEEE T Inf Foren Sec 2016; 11(10): 2349–2364.

SChang

Lin

Tsai

et al . A key assignment scheme for controlling access in partially ordered user hierarchies. In: Proceedings of the international conference on advanced information networking and application (AINA’04), vol. 2, Fukuoka, Japan, 29–31 March 2004, pp.376–379. New York: IEEE.

10.

Subramanian

Korah

A framework of secured embedding scheme using vector discrete wavelet transformation and Lagrange interpolation. J Comput Networks Comm 2018; 2018: 1–9.

11.

Knuth

DE.

The art of computer programming. 3rd ed. Reading, MA: Addison-Wesley, 1998.

12.

Hsiao

Chen

Liu

et al . Quality control of lead-acid battery according to its condition test for UPS supplier and manufacturers. Math Probl Eng 2014; 2014: 910820.

13.

Chung

Hsiao

Chen

SC.

The application of RFID monitoring technology to patrol management system in petrochemical industry. Wireless Pers Commun 2014; 79(2): 1063–1088.

14.

Stallings

Cryptography and network security: principles and practice. 4th ed. Upper Saddle River, NJ: Prentice Hall, 2005.

A hierarchical access control scheme based on Lagrange interpolation for mobile agents

Abstract

Keywords

Introduction

Previous work

Proposed scheme

Key generation phase

Example

Key derivation phase

Analysis of security

External attacks

Reversed attacks

Cooperative attacks

Equation attacks

Analysis of performance

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References