# Key-Insulated Undetachable Digital Signature Scheme and Solution for Secure Mobile Agents in Electronic Commerce

Authors: Yang Shi; Jie Lin; Guoyue Xiong; Xiaoping Wang; Hongfei Fan
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Considering the security of both the customers’ hosts and the eShops’ servers, we introduce the idea of a key-insulated undetachable digital signature, enabling mobile agents to generate undetachable digital signatures on remote hosts with the key-insulated property of the original signer’s signing key. From the theoretical perspective, we provide the formal definition and security notion of a key-insulated undetachable digital signature. From the practical perspective, we propose a concrete scheme to secure mobile agents in electronic commerce. The scheme is mainly focused on protecting the signing key from leakage and preventing the misuse of the signature algorithm on malicious servers. Agents do not carry the signing key when they generate digital signatures on behalf of the original signer, so the key is protected on remote servers. Furthermore, if a hacker gains the signing key of the original signer, the hacker is still unable to forge a signature for any time period other than the key being accessed. In addition, the encrypted function is combined with the original signer’s requirement to prevent the misuse of signing algorithm. The scheme is constructed on gap Diffie–Hellman groups with provable security, and the performance testing indicates that the scheme is efficient.


---

## Body

## 1. Introduction

Agents are a type of computer program that acts autonomously on behalf of a person or an organization. Mobile agents can easily transport themselves from one system in a network to another. They can also automatically suspend execution on one platform and migrate to another to resume their computations. Compared with traditional computing models (e.g., client/server), mobile agent technology has several significant advantages in electronic commerce applications, including autonomy and fault tolerance [1, 2].However, these benefits cannot be achieved without suitable security and trust technologies, which are critical for ensuring that all business data has been appropriately protected and business partners can collaborate with integrity and confidence. One significant threat is that malicious hosts might endanger passing agents because the attacks from owners of hosts are too strong to defeat with traditional security countermeasures. As a typical example, a mobile agent needs to sign a contract on behalf of the original signer (the customer) when an appropriate product has been found, while an attacker controlling the host can extract the secret signing key from the agent’s code or even generate a signature on the contract by simply forcefully calling the signing function that is “carried” on the agent. Furthermore, the risk of leakage of the signing key on the customer’s PC may stem from a variety of threats such as the “SSL Heartbleed.”Therefore, in the research field of mobile agent security, it is a challenge to protect the digital signature functionality against attacks from remote malicious hosts and meanwhile control the security risk of signing key leakage on the original signer’s host. Motivated by this security challenge, we propose a category of digital signature schemes for mobile agents, namely, thekey-insulated undetachable digital signature (KIUDS). Major contributions of this work are previewed as follows:(i)
We contributed the novel idea of key-insulated undetachable digital signature, which enables mobile agents to generate undetachable digital signatures on remote hosts with the key-insulated property of the original signer’s signing key.
(ii)
Theoretically, we provided the formal definition and security notion of the KIUDS schemes.
(iii)
Practically, we proposed a concrete KIUDS scheme for securing mobile agents in electronic commerce.
(iv)
We provided the security proof and efficiency analysis of the proposed scheme and conducted the performance testing which has indicated the good efficiency of the scheme.The rest of this paper is organized as follows. Section2 presents backgrounds and preliminaries of this work, including the mobile agent systems and applications in electronic commerce, the undetachable digital signature schemes and the key-insulated signature schemes, and the security analysis of threats on mobile agents from malicious hosts. The formal definition and security notion of KIUDS schemes are provided in Section 3. A concrete KIUDS scheme is described in Section 4, along with the theoretical analysis in terms of security, correctness, and computational costs, as well as a set of experimental results. Comparisons with related works are presented in Section 5. Finally, the paper concludes with a discussion on the findings.


## 2. Backgrounds and Preliminaries

### 2.1. Mobile Agent Systems and Applications in Electronic Commerce

An agent is a software entity that acts autonomously on behalf of a person or organization. Each agent has its own thread of execution, so tasks can be performed on its own initiative. A mobile agent is not bound to the system where it begins execution. It has the capability of transporting itself from one host to another in a network. We briefly introduce the backgrounds of mobile agents and the related system architecture [11] as follows.During an agent’s travel process, the agent state (including the execution state and the attributes) and code are being transported. The agent’s authority identifies the person or organization for which the agent acts. The names of the agents are usually required for identification, management, and locating. Commonly, agents are named by their authority, identity, and agent system type, whose combination can be mapped into a unique value for identifying a particular agent instance within the scope of the authority.By definition, an agent system is an integrated platform that can create, interpret, execute, transfer, and terminate agents. An agent system is usually associated with an authority that identifies the person or organization for which the agent system acts. An agent system is uniquely identified by its name and address, and a host can contain one or more agent systems. An instance of the architecture of mobile agent system is illustrated in Figure1.Figure 1
Mobile agent systems and architecture.Agents transfer themselves betweenplaces over the network, where aplace hereby is a context in which an agent executes. An agent is associated with a location, which consists of the place name and the address of the agent system where the place resides. An agent system may contain one or multiple places while a place can also host a number of agents. If an agent system does not support places, then it acts as a default place. When a client requests for the location of an agent, it retrieves the address of the place where the agent is executing.The agent technology seems an attractive paradigm to support e-commerce applications [12, 13], because agents are capable of acting on behalf of customers to reduce the effort required for performing transactions. Agents are autonomous by nature and therefore can be easily personalized to embody customers’ preferences. In addition, they are adaptive in terms of the capabilities of learning from both past actions and their environment, coping with changing network conditions and evolving user requirements. The above features permit the agent technology to add value to three primary e-commerce dimensions: information filtering, information gathering and retrieval, and dynamic and flexible execution of transactions. As typical applications, agent-based electronic commerce, product recommendation, and decision making have been demonstrated in the recent years [14–16].Furthermore, mobile agents not only can autonomously act and negotiate on behalf of their creators in one host, but also can autonomously decide to move itself from one host to another as necessary [13]. Such mobility achieves better network utilization and allows mobile users to disconnect with their agents roaming in the network, thus reducing connection costs. In the context of electronic marketplaces, for example, the mobility permits the agent to perform all required operations locally in the involved marketplace without reliable connection or bandwidth engagement.Some eShop and e-marketplace applications based on mobile agent technology have been recently proposed. A typical application of mobile agents in electronic commerce is shown in Figure2. The figure illustrates an intelligent trade agent (ITA) that roams the Internet buying goods or services from the servers of three eShops in the network. Other applications include a silicon intellectual property automatic trading platform [17], an agent-based English auction protocol using an elliptic curve cryptosystem for mobile commerce [18], a novel multiagent system architecture to cope with the flexibility requirements of virtual enterprises [19], and an approach aiming to deploy the mobile agent paradigm for mobile business applications [20].Figure 2
ITA roaming a network.


### 2.2. Digital Signature Schemes and Attack Models

Digital signature schemes allow a signer who has established a public key to sign a message such that any other party can verify that the message originated from the signer and was not modified in any way. A digital signature scheme typically consists of three algorithms: the key generation algorithm, the signing algorithm, and the verification algorithm.There are three main attack models according to the capabilities of an adversary to attack cryptosystems [21], for example, a digital signature scheme. The first is the black-box model. It is a traditional attack model where an adversary only has access to the functionality of a cryptosystem. This limited access increases the effort and is time required to start attacks. The second is the grey-box model, which refers to a model where a leakage function is present. In such an attack context, the adversary can deploy side-channel cryptanalysis techniques. Owing to the large variety of leakage functions, the grey-box model can further be classified into several subgroups. The third is the white-box model, where the adversary has total visibility of the software implementation of the cryptosystem and full control over its execution platform.As shown in Figure3, the white-box model is the worst-case model. The white-box model is used to analyze algorithms that are running in a nontrustable environment, that is, an environment in which applications are subject to attacks from the execution platform.Figure 3
Attack models.Secure computing in a white-box model is a challenge because the model assumes that [22] (1) fully privileged attack software shares a host with the cryptographic software, having complete access to the implementation of the algorithms, (2) dynamic execution (with instantiated cryptographic keys) can be observed, and (3) internal details of cryptographic algorithms are both completely visible and alterable.


### 2.3. Attacks and Threats against Mobile Agents and Their Signing Routines

While mobile agent-based technologies are already in use, mobile agents are still exposed to serious security threats. Mobile agent-based applications cannot be successfully implemented without suitable security technologies to ensure that the sensitive business data are appropriately protected and business partners can work together with integrity and confidence. One of the most challenging threats to mobile agent security is attacks from platforms (malicious hosts). In general, there are two main kinds of attacks from malicious hosts [23], eavesdropping attacks and manipulation attacks. A substantial number of attacks are identified in detail in [24], including spying out code, spying out data, spying out control flow, manipulation of code, manipulation of data, manipulation of control flow, incorrect execution of code, masquerading of the host, denial of execution, spying out interaction with other agents, manipulation of interaction with other agents, and returning wrong system call results issued by the agent.Clearly, mobile agents executed on a malicious host are in a white-box attack context. In traditional digital signature schemes, mobile agents must carry the private key when they generate digital signatures on behalf of the original user. Possible attacks from malicious remote hosts endanger the digital signature functionality provided by a mobile agent because the signing algorithm may be misused and the signing key may be compromised. Furthermore, many mobile agent systems are implemented in Java because of the language’s suitable performance across various platforms. Unfortunately, the key in a class file (the Java byte code) is extremely vulnerable, as illustrated in Figure4. Hence, traditional digital signature schemes are not suitable for mobile agents, while new signature techniques are required.Figure 4
Segment of the Java byte code of an agent.Meanwhile, digital signature functionalities also face a significant key leakage problem on the local host of the original signer. A serious security issue is presented in the event that the original signer’s local host is under the control of a hacker because the original private signing key may be compromised.The severity of the potential threats increases with the rapid development of advanced persistent threats (APTs) such as “Operation Aurora” against Gmail accounts, the “Stuxnet Worm” against the control system of nuclear devices in Iran, “Operation Shady RAT” against more than 70 organizations (including several defense contractors), and the recently discovered “Havex” against industrial control systems. An APT is a set of stealthy and continuous hacking processes often orchestrated by people targeting a specific entity. Additionally, security vulnerabilities such as the “SSL Heartbleed,” which was disclosed in April 2014 in the OpenSSL cryptography library, could also enable hackers to extract information from remote hosts.


### 2.4. Undetachable Digital Signatures for Mobile Agents

The idea of the undetachable digital signature was proposed by Sander and Tschudin in [25] based on the reasoning that mobile agents do not have to be executed in clear text form. The undetachable digital signature technique allows a mobile agent to effectively produce a digital signature inside a remote and possibly malicious host without allowing the host to deduce the agent’s secret or to reuse the signature routine for arbitrary documents. A brief introduction to this idea is presented as follows.LetS
i
g be a rational function used by C (a customer) to produce the digital signature S
i
g
(
m
) of an arbitrary message m. Furthermore, suppose the message m is the result of a rational function f applied to some input data x. Finally, the verification function V
e
r that C publishes to allow others to check the validity of the digital signature z is regarded to be a valid signature of m if and only if(1)
z
=
S
i
g
m
.To allow the customer’s mobile agent to create “undetachable” signatures, the following is computed:(2)
f
S
i
g
n
e
d
=
S
i
g
∘
f
,where f is an auxiliary binding function that binds a constraint (e.g., a restriction or a limitation) on the signing function. For example, in the case of electronic commerce, a typical constraint could be “an iPhone 6 costing no more than 916 Dollars.” f
S
i
g
n
e
d and f are then migrated to S (the eShop) with the mobile agent. S evaluates(3)
m
=
f
x
z
=
f
S
i
g
n
e
d
x
.However, Sander and Tschudin did not provide a concrete implementation of the undetachable digital signature scheme. The first undetachable digital signature scheme was proposed by Kotzanikolaou et al. in the form of an RSA implementation [3]. This was improved by Lee et al. [4] with bilateral security, whose scheme provides server’s nonrepudiation because it contains server’s signature at the same time. Han et al. proposed a security scheme for e-transactions using mobile agents with an agent broker [5], while they gave an undetachable signature function pair but without presenting the signing function S
i
g subject to (2). Another undetachable signature scheme based on pairings was proposed in prior work [8], which is based on the short signature scheme proposed in prior work [26]. To solve the problem in which a host may force an agent to commit to a suboptimal transaction, Borselius et al. [6] introduced the notion of undetachable threshold signatures and proposed an RSA-based implementation. In prior work [9], an implementation of undetachable threshold digital signature based on conic curves was proposed, and computational studies indicated that the implementation in [9] was superior to the RSA-based implementation in [6]. The latest published undetachable signature scheme was presented in prior work [10], which provides forward security by following the BLS short signature [26]. However, except for the scheme in [10], none of the proposed undetachable digital signature schemes can simultaneously protect digital signature functionalities against attacks from remote malicious hosts and mitigate the security risk of signing key leakage on the original signer’s host. Moreover, even with the scheme in [10], an adversary can forge any signature during any period after he/she has got the signing key (e.g., via cracking the host of the original signer). Therefore, stronger undetachable digital signature schemes are demanded, which motivate us to develop undetachable signature schemes with the key-insulated property.


### 2.5. Key-Insulated Digital Signatures

The exposure of secret keys is perhaps the most devastating attack on a cryptosystem because it typically leads to a full loss of security. This problem is probably the greatest threat to cryptography in the real world: in practice, it is typically easier for an adversary to obtain a secret key from a naive user than to break the computational assumption on which the system is based. This threat is currently increasing as new APTs are quickly developed.Complete prevention of key exposure—even for the original signer on his local host—usually requires some degree of physical security, which can be expensive and inconvenient. Thus, some security countermeasures assume that key exposure will inevitably occur and therefore focus on minimizing the damage which results when keys are obtained by an attacker.A category of such damage-minimization security countermeasures is key-insulated cryptography [27, 28]. In the security model of key-insulated cryptography, physical security (and hence the secrecy of stored data) is guaranteed for a single device that holds a “master” secret key corresponding to a fixed public key. Day-to-day cryptographic operations such as signing a message, however, are performed by an insecure device (e.g., the customer’s PC) which “refreshes” its private key periodically by interacting with the physically secure device. In a t
,
N-key-insulated cryptosystem, an attacker who compromises the insecure device and obtains secret keys for up to t time periods is unable to violate the security of the cryptosystem for any of the remaining N
-
t periods. The principle of key-insulated signature schemes is illustrated in Figure 5.Figure 5
Principle of the key-insulated signature.


## 2.1. Mobile Agent Systems and Applications in Electronic Commerce

An agent is a software entity that acts autonomously on behalf of a person or organization. Each agent has its own thread of execution, so tasks can be performed on its own initiative. A mobile agent is not bound to the system where it begins execution. It has the capability of transporting itself from one host to another in a network. We briefly introduce the backgrounds of mobile agents and the related system architecture [11] as follows.During an agent’s travel process, the agent state (including the execution state and the attributes) and code are being transported. The agent’s authority identifies the person or organization for which the agent acts. The names of the agents are usually required for identification, management, and locating. Commonly, agents are named by their authority, identity, and agent system type, whose combination can be mapped into a unique value for identifying a particular agent instance within the scope of the authority.By definition, an agent system is an integrated platform that can create, interpret, execute, transfer, and terminate agents. An agent system is usually associated with an authority that identifies the person or organization for which the agent system acts. An agent system is uniquely identified by its name and address, and a host can contain one or more agent systems. An instance of the architecture of mobile agent system is illustrated in Figure1.Figure 1
Mobile agent systems and architecture.Agents transfer themselves betweenplaces over the network, where aplace hereby is a context in which an agent executes. An agent is associated with a location, which consists of the place name and the address of the agent system where the place resides. An agent system may contain one or multiple places while a place can also host a number of agents. If an agent system does not support places, then it acts as a default place. When a client requests for the location of an agent, it retrieves the address of the place where the agent is executing.The agent technology seems an attractive paradigm to support e-commerce applications [12, 13], because agents are capable of acting on behalf of customers to reduce the effort required for performing transactions. Agents are autonomous by nature and therefore can be easily personalized to embody customers’ preferences. In addition, they are adaptive in terms of the capabilities of learning from both past actions and their environment, coping with changing network conditions and evolving user requirements. The above features permit the agent technology to add value to three primary e-commerce dimensions: information filtering, information gathering and retrieval, and dynamic and flexible execution of transactions. As typical applications, agent-based electronic commerce, product recommendation, and decision making have been demonstrated in the recent years [14–16].Furthermore, mobile agents not only can autonomously act and negotiate on behalf of their creators in one host, but also can autonomously decide to move itself from one host to another as necessary [13]. Such mobility achieves better network utilization and allows mobile users to disconnect with their agents roaming in the network, thus reducing connection costs. In the context of electronic marketplaces, for example, the mobility permits the agent to perform all required operations locally in the involved marketplace without reliable connection or bandwidth engagement.Some eShop and e-marketplace applications based on mobile agent technology have been recently proposed. A typical application of mobile agents in electronic commerce is shown in Figure2. The figure illustrates an intelligent trade agent (ITA) that roams the Internet buying goods or services from the servers of three eShops in the network. Other applications include a silicon intellectual property automatic trading platform [17], an agent-based English auction protocol using an elliptic curve cryptosystem for mobile commerce [18], a novel multiagent system architecture to cope with the flexibility requirements of virtual enterprises [19], and an approach aiming to deploy the mobile agent paradigm for mobile business applications [20].Figure 2
ITA roaming a network.


## 2.2. Digital Signature Schemes and Attack Models

Digital signature schemes allow a signer who has established a public key to sign a message such that any other party can verify that the message originated from the signer and was not modified in any way. A digital signature scheme typically consists of three algorithms: the key generation algorithm, the signing algorithm, and the verification algorithm.There are three main attack models according to the capabilities of an adversary to attack cryptosystems [21], for example, a digital signature scheme. The first is the black-box model. It is a traditional attack model where an adversary only has access to the functionality of a cryptosystem. This limited access increases the effort and is time required to start attacks. The second is the grey-box model, which refers to a model where a leakage function is present. In such an attack context, the adversary can deploy side-channel cryptanalysis techniques. Owing to the large variety of leakage functions, the grey-box model can further be classified into several subgroups. The third is the white-box model, where the adversary has total visibility of the software implementation of the cryptosystem and full control over its execution platform.As shown in Figure3, the white-box model is the worst-case model. The white-box model is used to analyze algorithms that are running in a nontrustable environment, that is, an environment in which applications are subject to attacks from the execution platform.Figure 3
Attack models.Secure computing in a white-box model is a challenge because the model assumes that [22] (1) fully privileged attack software shares a host with the cryptographic software, having complete access to the implementation of the algorithms, (2) dynamic execution (with instantiated cryptographic keys) can be observed, and (3) internal details of cryptographic algorithms are both completely visible and alterable.


## 2.3. Attacks and Threats against Mobile Agents and Their Signing Routines

While mobile agent-based technologies are already in use, mobile agents are still exposed to serious security threats. Mobile agent-based applications cannot be successfully implemented without suitable security technologies to ensure that the sensitive business data are appropriately protected and business partners can work together with integrity and confidence. One of the most challenging threats to mobile agent security is attacks from platforms (malicious hosts). In general, there are two main kinds of attacks from malicious hosts [23], eavesdropping attacks and manipulation attacks. A substantial number of attacks are identified in detail in [24], including spying out code, spying out data, spying out control flow, manipulation of code, manipulation of data, manipulation of control flow, incorrect execution of code, masquerading of the host, denial of execution, spying out interaction with other agents, manipulation of interaction with other agents, and returning wrong system call results issued by the agent.Clearly, mobile agents executed on a malicious host are in a white-box attack context. In traditional digital signature schemes, mobile agents must carry the private key when they generate digital signatures on behalf of the original user. Possible attacks from malicious remote hosts endanger the digital signature functionality provided by a mobile agent because the signing algorithm may be misused and the signing key may be compromised. Furthermore, many mobile agent systems are implemented in Java because of the language’s suitable performance across various platforms. Unfortunately, the key in a class file (the Java byte code) is extremely vulnerable, as illustrated in Figure4. Hence, traditional digital signature schemes are not suitable for mobile agents, while new signature techniques are required.Figure 4
Segment of the Java byte code of an agent.Meanwhile, digital signature functionalities also face a significant key leakage problem on the local host of the original signer. A serious security issue is presented in the event that the original signer’s local host is under the control of a hacker because the original private signing key may be compromised.The severity of the potential threats increases with the rapid development of advanced persistent threats (APTs) such as “Operation Aurora” against Gmail accounts, the “Stuxnet Worm” against the control system of nuclear devices in Iran, “Operation Shady RAT” against more than 70 organizations (including several defense contractors), and the recently discovered “Havex” against industrial control systems. An APT is a set of stealthy and continuous hacking processes often orchestrated by people targeting a specific entity. Additionally, security vulnerabilities such as the “SSL Heartbleed,” which was disclosed in April 2014 in the OpenSSL cryptography library, could also enable hackers to extract information from remote hosts.


## 2.4. Undetachable Digital Signatures for Mobile Agents

The idea of the undetachable digital signature was proposed by Sander and Tschudin in [25] based on the reasoning that mobile agents do not have to be executed in clear text form. The undetachable digital signature technique allows a mobile agent to effectively produce a digital signature inside a remote and possibly malicious host without allowing the host to deduce the agent’s secret or to reuse the signature routine for arbitrary documents. A brief introduction to this idea is presented as follows.LetS
i
g be a rational function used by C (a customer) to produce the digital signature S
i
g
(
m
) of an arbitrary message m. Furthermore, suppose the message m is the result of a rational function f applied to some input data x. Finally, the verification function V
e
r that C publishes to allow others to check the validity of the digital signature z is regarded to be a valid signature of m if and only if(1)
z
=
S
i
g
m
.To allow the customer’s mobile agent to create “undetachable” signatures, the following is computed:(2)
f
S
i
g
n
e
d
=
S
i
g
∘
f
,where f is an auxiliary binding function that binds a constraint (e.g., a restriction or a limitation) on the signing function. For example, in the case of electronic commerce, a typical constraint could be “an iPhone 6 costing no more than 916 Dollars.” f
S
i
g
n
e
d and f are then migrated to S (the eShop) with the mobile agent. S evaluates(3)
m
=
f
x
z
=
f
S
i
g
n
e
d
x
.However, Sander and Tschudin did not provide a concrete implementation of the undetachable digital signature scheme. The first undetachable digital signature scheme was proposed by Kotzanikolaou et al. in the form of an RSA implementation [3]. This was improved by Lee et al. [4] with bilateral security, whose scheme provides server’s nonrepudiation because it contains server’s signature at the same time. Han et al. proposed a security scheme for e-transactions using mobile agents with an agent broker [5], while they gave an undetachable signature function pair but without presenting the signing function S
i
g subject to (2). Another undetachable signature scheme based on pairings was proposed in prior work [8], which is based on the short signature scheme proposed in prior work [26]. To solve the problem in which a host may force an agent to commit to a suboptimal transaction, Borselius et al. [6] introduced the notion of undetachable threshold signatures and proposed an RSA-based implementation. In prior work [9], an implementation of undetachable threshold digital signature based on conic curves was proposed, and computational studies indicated that the implementation in [9] was superior to the RSA-based implementation in [6]. The latest published undetachable signature scheme was presented in prior work [10], which provides forward security by following the BLS short signature [26]. However, except for the scheme in [10], none of the proposed undetachable digital signature schemes can simultaneously protect digital signature functionalities against attacks from remote malicious hosts and mitigate the security risk of signing key leakage on the original signer’s host. Moreover, even with the scheme in [10], an adversary can forge any signature during any period after he/she has got the signing key (e.g., via cracking the host of the original signer). Therefore, stronger undetachable digital signature schemes are demanded, which motivate us to develop undetachable signature schemes with the key-insulated property.


## 2.5. Key-Insulated Digital Signatures

The exposure of secret keys is perhaps the most devastating attack on a cryptosystem because it typically leads to a full loss of security. This problem is probably the greatest threat to cryptography in the real world: in practice, it is typically easier for an adversary to obtain a secret key from a naive user than to break the computational assumption on which the system is based. This threat is currently increasing as new APTs are quickly developed.Complete prevention of key exposure—even for the original signer on his local host—usually requires some degree of physical security, which can be expensive and inconvenient. Thus, some security countermeasures assume that key exposure will inevitably occur and therefore focus on minimizing the damage which results when keys are obtained by an attacker.A category of such damage-minimization security countermeasures is key-insulated cryptography [27, 28]. In the security model of key-insulated cryptography, physical security (and hence the secrecy of stored data) is guaranteed for a single device that holds a “master” secret key corresponding to a fixed public key. Day-to-day cryptographic operations such as signing a message, however, are performed by an insecure device (e.g., the customer’s PC) which “refreshes” its private key periodically by interacting with the physically secure device. In a t
,
N-key-insulated cryptosystem, an attacker who compromises the insecure device and obtains secret keys for up to t time periods is unable to violate the security of the cryptosystem for any of the remaining N
-
t periods. The principle of key-insulated signature schemes is illustrated in Figure 5.Figure 5
Principle of the key-insulated signature.


## 3. Key-Insulated Undetachable Digital Signature

In this section, we propose a novel category of digital signature schemes for mobile agents, the KIUDS scheme. This scheme simultaneously protects the digital signature functionality against attacks from remote malicious hosts and mitigates the security risk of signing key leakage on the original signer’s host. We begin by defining the KIUDS scheme and then provide its security model and security notion.


### 3.1. Definition

A KIUDS schemeK
I
U
D
S
=
K
G
e
n
,
U
p
d
∗
,
U
p
d
,
U
n
d
S
i
g
F
u
n
G
e
n
,
U
n
d
S
i
g
,
U
n
d
V
r
f
y consists of six algorithms as follows:(1)
K
G
e
n, the key generation algorithm, is a probabilistic algorithm taking as input a security parameter 1
k
(
k
∈
N
) and the total number of time periods N. It returns a public key P
p
u
b, a master secret signing key s, and an initial key D
0.
(2)
U
p
d
∗, the device key update algorithm, is a probabilistic algorithm taking as input indices i
,
j for time periods (throughout, we assume 1
≤
i
,
j
≤
N) and the master key D. It returns a partial secret key D
i
,
j
′.
(3)
U
p
d, the user key update algorithm, is a deterministic algorithm taking as input indices i
,
j, a secret key D
i, and a partial secret key D
i
,
j
′. It returns the secret key D
j for time period j.
(4)
U
n
d
S
i
g
F
u
n
G
e
n, the undetachable signing function generation algorithm, is a probabilistic polynomial time algorithm which takes the requirement of a customer R
E
Q
_
C, the customer’s identity I
D
C, and the index of the current time period j as inputs. The algorithm outputs a function f
S
i
g
n
e
d
,
j
(
·
).
(5)
U
n
d
S
i
g, the undetachable signing algorithm, is a polynomial time algorithm which takes the contract (or its hash value) as input. The algorithm outputs an undetachable signature z.
(6)
U
n
d
V
r
f
y, the undetachable signature verification algorithm, is a polynomial time algorithm which takes the contract (or its hash value) and an undetachable signature z as input. The algorithm outputs either “Accept” or “Reject,” simply 1 or 0.To aid in further discussions, the frequently used symbols are listed as follows:1
k: a security parameter, (k
∈
N),
P
p
u
b: the public key,
s: the master secret signing key,
i
,
j: indices of the time period,
D
0: the initial key,
D
j: the secret key for time period j,
D
i
,
j
′: a partial secret key,
B
I
D
_
S
∥
I
D
S: shop S’s bid information and identity,
R
E
Q
_
C
∥
I
D
C: customer C’s requirement and identity,
f
S
i
g
n
e
d
,
j: an implementation of the undetachable signing function for time period j,
f: the auxiliary function of f
S
i
g
n
e
d
,
j,
M
s
g: message (usually a contract),
z: an undetachable signature,
q: a prime number,
G
1, G
2: two cyclic groups whose orders are both q,
P: a generator of G
1,
e
·
,
·: a bilinear pairing from G
1
×
G
1 to G
2.


### 3.2. Workflow of Using a KIUDS Scheme

First, a trusted authority, for example, a certification authority or a key distribution center, should publish all public parameters of the cryptosystem to all participants. The trusted authority then generates cryptographic keys for all participants by running the algorithmK
G
e
n
1
k; and the private key (i.e., the master key and the initial key) of each participant is sent via a correspondingly secure communication channel. The customer stores the private signing key in a physically secure device. Day-to-day cryptographic operations are performed by an insecure device (e.g., the customer’s PC) which periodically refreshes its key by interacting with the secure device using key update algorithms (U
p
d
∗ and U
p
d).When a customer wants a mobile agent to do the shopping, the customer runs theU
n
d
S
i
g
F
u
n
G
e
n algorithm to prepare the mobile agent before it starts migrating. The mobile agent then begins migrating to search for shops that are willing to satisfy the customer’s requirement.Finally, anyone can check the validity of a contract by using theU
n
d
V
r
f
y algorithm.Figure6 illustrates the workflow of using the algorithms in the proposed scheme.Figure 6
Overall workflow of a KIUDS scheme.


### 3.3. Security Model and Security Notion

A KIUDS scheme differs from conventional digital signature schemes, as do its security model and security notion. However, the starting point of the discussion of the security model of KIUDS schemes is still the classical security model of conventional digital signature schemes.There are four subclasses of known-message attacks against digital signature schemes [29]: the plain known-message attack, the generic chosen-message attack, the oriented chosen-message attack, and the adaptively chosen-message attack (ACMA). ACMA is the most dangerous scenario because the adversary is supposed to have such privilege, asking the signer to sign any message that he wants and then adapting his queries according to previous message-signature pairs.The expected results of an attack are classified as follows [30]: (1) disclosing the secret key of the signer; (2) constructing an efficient algorithm which is able to sign any message; and (3) providing a new message-signature pair. The third category is called existential forgery. In many cases this attack is not dangerous because the output message is likely to be meaningless. Nevertheless, a signature scheme which is not existentially unforgeable (and thus that admits existential forgeries) cannot be used to certify random-looking elements such as keys.Besides the attack model of ACMA, the following three security threats must be included in the attack model of KIUDS schemes.(1)
Implementation Exposures. A shop owner S is capable of obtaining the implementation of f
s
i
g
n
e
d
,
j. This corresponds to an attack from malicious hosts. Note that an implementation exposure indicates ACMA because S can run the implementation of the signing algorithm.
(2)
Key Exposures. In some time periods, an attacker may break the defense system of a customer’s computer and extract the corresponding signing key from the disk or memory.
(3)
Adaptively Chosen-Restriction Attack. This attack is an extension of the first threat. Consider the case where a friend (F) of customer C asks C to purchase an item. The restriction of an undetachable signature is probably set up by F instead of C. Then, if F colludes with a shop owner, F is also capable of obtaining the implementation of f
s
i
g
n
e
d
,
j.The first threat is easy to model by giving the adversary the description of the implementation off
s
i
g
n
e
d
,
j.To model the second threat, we give the adversary access to a key exposure oracleO
s
,
D
0
E
x
p
o
s
u
r
e
i that performs the following operations on input i. The oracle first checks whether period i has been “activated”; if so, the oracle returns the value already stored for D
i. Otherwise, the key exposure oracle runs d
0
,
i
′
←
U
p
d
∗
(
0
,
i
,
s
) followed by D
i
←
U
p
d
0
,
i
,
D
0
,
D
0
,
i
′, returns and stores the value D
i, and labels period i as “activated.”To model the third threat, we give the adversary access to a chosen-restriction oracleO
s
,
D
0
Chosen-restriction
i
,
R
E
Q
_
C that performs the following operations on input i
,
R
E
Q
_
C. The oracle first checks whether period i has been “activated”; if so, the oracle returns the output of U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C. Otherwise, the key exposure oracle runs d
0
,
i
′
←
U
p
d
∗
(
0
,
i
,
s
) followed by D
i
←
U
p
d
0
,
i
,
D
0
,
D
0
,
i
′, stores the value D
i, labels period i as “activated,” and returns the output of U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C. Moreover, the first threat is also covered by the chosen-restriction oracle because the chosen-restriction oracle models a stronger adversary rather than a simple malicious eShop owner.Note that storing the values of the secret signing keys for activated time periods is only necessary when the algorithmU
p
d
∗ is probabilistic; when U
p
d
∗ is deterministic, the oracles (O
s
,
D
0
E
x
p
o
s
u
r
e and O
s
,
D
0
Chosen-restriction) may simply run U
p
d
∗ “from scratch” whenever needed to answer a query.Definition 1 ((t,N)-KIUDS scheme).
LetK
I
U
D
S
=
K
G
e
n
,
U
p
d
∗
,
U
p
d
,
U
n
d
S
i
g
F
u
n
G
e
n
,
U
n
d
S
i
g
,
U
n
d
V
r
f
y be a KIUDS scheme. For any adversary A, the probability of a successful attack is defined as follows:(4)
S
u
c
c
A
K
I
U
S
k
=
Pr
⁡
1
⟵
K
I
U
D
S
.
U
n
d
V
r
f
y
z
,
M
s
g
:
P
p
u
b
,
s
,
D
0
⟵
K
I
U
D
S
.
K
G
e
n
1
k
z
,
M
s
g
⟵
A
O
s
,
D
0
E
x
p
o
s
u
r
e
·
,
O
s
,
D
0
Chosen-restriction
·
,
·
P
p
u
b
M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S
O
s
,
D
0
Chosen-restriction
z
,
j
,
R
E
Q
_
C
and
O
s
,
D
0
E
x
p
o
s
u
r
e
j
has  not  been  queried
.We say thatK
I
U
D
S is a (t
,
N)-KIUDS scheme if S
u
c
c
A
K
I
U
S
k is negligible for any probabilistic polynomial time (PPT) adversary A who submits at most t queries to the key exposure oracle O
s
,
D
0
E
x
p
o
s
u
r
e. Moreover, following the convention of key-insulated cryptography, we say K
I
U
S is perfectly key-insulated if t equals N
-
1.


## 3.1. Definition

A KIUDS schemeK
I
U
D
S
=
K
G
e
n
,
U
p
d
∗
,
U
p
d
,
U
n
d
S
i
g
F
u
n
G
e
n
,
U
n
d
S
i
g
,
U
n
d
V
r
f
y consists of six algorithms as follows:(1)
K
G
e
n, the key generation algorithm, is a probabilistic algorithm taking as input a security parameter 1
k
(
k
∈
N
) and the total number of time periods N. It returns a public key P
p
u
b, a master secret signing key s, and an initial key D
0.
(2)
U
p
d
∗, the device key update algorithm, is a probabilistic algorithm taking as input indices i
,
j for time periods (throughout, we assume 1
≤
i
,
j
≤
N) and the master key D. It returns a partial secret key D
i
,
j
′.
(3)
U
p
d, the user key update algorithm, is a deterministic algorithm taking as input indices i
,
j, a secret key D
i, and a partial secret key D
i
,
j
′. It returns the secret key D
j for time period j.
(4)
U
n
d
S
i
g
F
u
n
G
e
n, the undetachable signing function generation algorithm, is a probabilistic polynomial time algorithm which takes the requirement of a customer R
E
Q
_
C, the customer’s identity I
D
C, and the index of the current time period j as inputs. The algorithm outputs a function f
S
i
g
n
e
d
,
j
(
·
).
(5)
U
n
d
S
i
g, the undetachable signing algorithm, is a polynomial time algorithm which takes the contract (or its hash value) as input. The algorithm outputs an undetachable signature z.
(6)
U
n
d
V
r
f
y, the undetachable signature verification algorithm, is a polynomial time algorithm which takes the contract (or its hash value) and an undetachable signature z as input. The algorithm outputs either “Accept” or “Reject,” simply 1 or 0.To aid in further discussions, the frequently used symbols are listed as follows:1
k: a security parameter, (k
∈
N),
P
p
u
b: the public key,
s: the master secret signing key,
i
,
j: indices of the time period,
D
0: the initial key,
D
j: the secret key for time period j,
D
i
,
j
′: a partial secret key,
B
I
D
_
S
∥
I
D
S: shop S’s bid information and identity,
R
E
Q
_
C
∥
I
D
C: customer C’s requirement and identity,
f
S
i
g
n
e
d
,
j: an implementation of the undetachable signing function for time period j,
f: the auxiliary function of f
S
i
g
n
e
d
,
j,
M
s
g: message (usually a contract),
z: an undetachable signature,
q: a prime number,
G
1, G
2: two cyclic groups whose orders are both q,
P: a generator of G
1,
e
·
,
·: a bilinear pairing from G
1
×
G
1 to G
2.


## 3.2. Workflow of Using a KIUDS Scheme

First, a trusted authority, for example, a certification authority or a key distribution center, should publish all public parameters of the cryptosystem to all participants. The trusted authority then generates cryptographic keys for all participants by running the algorithmK
G
e
n
1
k; and the private key (i.e., the master key and the initial key) of each participant is sent via a correspondingly secure communication channel. The customer stores the private signing key in a physically secure device. Day-to-day cryptographic operations are performed by an insecure device (e.g., the customer’s PC) which periodically refreshes its key by interacting with the secure device using key update algorithms (U
p
d
∗ and U
p
d).When a customer wants a mobile agent to do the shopping, the customer runs theU
n
d
S
i
g
F
u
n
G
e
n algorithm to prepare the mobile agent before it starts migrating. The mobile agent then begins migrating to search for shops that are willing to satisfy the customer’s requirement.Finally, anyone can check the validity of a contract by using theU
n
d
V
r
f
y algorithm.Figure6 illustrates the workflow of using the algorithms in the proposed scheme.Figure 6
Overall workflow of a KIUDS scheme.


## 3.3. Security Model and Security Notion

A KIUDS scheme differs from conventional digital signature schemes, as do its security model and security notion. However, the starting point of the discussion of the security model of KIUDS schemes is still the classical security model of conventional digital signature schemes.There are four subclasses of known-message attacks against digital signature schemes [29]: the plain known-message attack, the generic chosen-message attack, the oriented chosen-message attack, and the adaptively chosen-message attack (ACMA). ACMA is the most dangerous scenario because the adversary is supposed to have such privilege, asking the signer to sign any message that he wants and then adapting his queries according to previous message-signature pairs.The expected results of an attack are classified as follows [30]: (1) disclosing the secret key of the signer; (2) constructing an efficient algorithm which is able to sign any message; and (3) providing a new message-signature pair. The third category is called existential forgery. In many cases this attack is not dangerous because the output message is likely to be meaningless. Nevertheless, a signature scheme which is not existentially unforgeable (and thus that admits existential forgeries) cannot be used to certify random-looking elements such as keys.Besides the attack model of ACMA, the following three security threats must be included in the attack model of KIUDS schemes.(1)
Implementation Exposures. A shop owner S is capable of obtaining the implementation of f
s
i
g
n
e
d
,
j. This corresponds to an attack from malicious hosts. Note that an implementation exposure indicates ACMA because S can run the implementation of the signing algorithm.
(2)
Key Exposures. In some time periods, an attacker may break the defense system of a customer’s computer and extract the corresponding signing key from the disk or memory.
(3)
Adaptively Chosen-Restriction Attack. This attack is an extension of the first threat. Consider the case where a friend (F) of customer C asks C to purchase an item. The restriction of an undetachable signature is probably set up by F instead of C. Then, if F colludes with a shop owner, F is also capable of obtaining the implementation of f
s
i
g
n
e
d
,
j.The first threat is easy to model by giving the adversary the description of the implementation off
s
i
g
n
e
d
,
j.To model the second threat, we give the adversary access to a key exposure oracleO
s
,
D
0
E
x
p
o
s
u
r
e
i that performs the following operations on input i. The oracle first checks whether period i has been “activated”; if so, the oracle returns the value already stored for D
i. Otherwise, the key exposure oracle runs d
0
,
i
′
←
U
p
d
∗
(
0
,
i
,
s
) followed by D
i
←
U
p
d
0
,
i
,
D
0
,
D
0
,
i
′, returns and stores the value D
i, and labels period i as “activated.”To model the third threat, we give the adversary access to a chosen-restriction oracleO
s
,
D
0
Chosen-restriction
i
,
R
E
Q
_
C that performs the following operations on input i
,
R
E
Q
_
C. The oracle first checks whether period i has been “activated”; if so, the oracle returns the output of U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C. Otherwise, the key exposure oracle runs d
0
,
i
′
←
U
p
d
∗
(
0
,
i
,
s
) followed by D
i
←
U
p
d
0
,
i
,
D
0
,
D
0
,
i
′, stores the value D
i, labels period i as “activated,” and returns the output of U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C. Moreover, the first threat is also covered by the chosen-restriction oracle because the chosen-restriction oracle models a stronger adversary rather than a simple malicious eShop owner.Note that storing the values of the secret signing keys for activated time periods is only necessary when the algorithmU
p
d
∗ is probabilistic; when U
p
d
∗ is deterministic, the oracles (O
s
,
D
0
E
x
p
o
s
u
r
e and O
s
,
D
0
Chosen-restriction) may simply run U
p
d
∗ “from scratch” whenever needed to answer a query.Definition 1 ((t,N)-KIUDS scheme).
LetK
I
U
D
S
=
K
G
e
n
,
U
p
d
∗
,
U
p
d
,
U
n
d
S
i
g
F
u
n
G
e
n
,
U
n
d
S
i
g
,
U
n
d
V
r
f
y be a KIUDS scheme. For any adversary A, the probability of a successful attack is defined as follows:(4)
S
u
c
c
A
K
I
U
S
k
=
Pr
⁡
1
⟵
K
I
U
D
S
.
U
n
d
V
r
f
y
z
,
M
s
g
:
P
p
u
b
,
s
,
D
0
⟵
K
I
U
D
S
.
K
G
e
n
1
k
z
,
M
s
g
⟵
A
O
s
,
D
0
E
x
p
o
s
u
r
e
·
,
O
s
,
D
0
Chosen-restriction
·
,
·
P
p
u
b
M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S
O
s
,
D
0
Chosen-restriction
z
,
j
,
R
E
Q
_
C
and
O
s
,
D
0
E
x
p
o
s
u
r
e
j
has  not  been  queried
.We say thatK
I
U
D
S is a (t
,
N)-KIUDS scheme if S
u
c
c
A
K
I
U
S
k is negligible for any probabilistic polynomial time (PPT) adversary A who submits at most t queries to the key exposure oracle O
s
,
D
0
E
x
p
o
s
u
r
e. Moreover, following the convention of key-insulated cryptography, we say K
I
U
S is perfectly key-insulated if t equals N
-
1.


## 4. A Concrete Scheme

In this section, we propose a construction of a KIUDS scheme and provide the proofs of correctness and security. In addition, we present the results of the complexity analysis and performance testing. Note that the proposed scheme utilizes the signature scheme in [31] as a building block.


### 4.1. The Algorithms

LetG
1 be a cyclic group generated by a generator P, whose order is a prime number q, and let G
2 be a cyclic multiplicative group of the same order q. Suppose that discrete logarithm problems in both G
1 and G
2 are hard. Let e
:
G
1
×
G
1
→
G
2 be a pairing that satisfies the following three conditions.Bilinear. Equations (5) and (6) together or (7) are as follows:(5)
e
P
1
+
P
2
,
Q
=
e
P
1
,
Q
e
P
2
,
Q
,
(6)
e
P
,
Q
1
+
Q
2
=
e
P
,
Q
1
e
P
,
Q
2
,
(7)
e
a
P
,
b
Q
=
e
P
,
Q
a
b
,where {
a
,
b
}
⊆
Z
q
∗.Nondegenerate. There exist P
∈
G
1 and Q
∈
G
1 subject to(8)
e
P
,
Q
≠
1
.Computability. There is an efficient algorithm to compute e
P
,
Q for all {
P
,
Q
}
⊆
G
1.We note that the Weil and Tate pairings associated with supersingular elliptic curves or abelian varieties can be modified to create such bilinear maps.Suppose thatG is an additive group. Four well-known mathematical problems are defined as follows.(1)
Discrete Logarithm Problem (DLP). Given two group elements P and Q, and an integer n, (9) is satisfied whenever such an integer exists:(9)
Q
=
n
P
.
(2)
Decision Diffie–Hellman Problem (DDHP). For {
a
,
b
,
c
}
⊆
Z
q
∗, given P
,
a
P
,
b
P
,
c
P decide whether(10)
c
≡
a
b
m
o
d
q
.
(3)
Computational Diffie–Hellman Problem (CDHP). For {
a
,
b
}
⊆
Z
q
∗, given P
,
a
P
,
b
P compute a
b
P without any knowledge about the value of either a or b.
(4)
Gap Diffie–Hellman Problem.We assume throughout this paper that CDHP and DLP are intractable, meaning that there is no polynomial time algorithm to solve CDHP or DLP with nonnegligible probability. When the DDHP is easy but the CDHP is hard on groupG
1, G
1 is called a gap Diffie–Hellman (GDH) group. Our scheme can be built on any GDH group. Further mathematical background can be found in [32, 33].We now define some system parameters. LetP be a generator of G
1. Suppose that the total number of time periods N is a shared public value. Two secure hash functions are given here: H
1
:
{
0,1
}
∗
→
Z
q and H
2
:
{
0,1
}
∗
→
G
1. The implementations of these hash functions can be found in works such as [34–36].The public parametersΩ
=
G
1
,
G
2
,
e
(
·
,
·
)
,
q
,
P
,
H
1
,
H
2 should be published to all participants by the trusted authority. Moreover, a public function V
a
l
i
d
T
u
p
l
e that outputs 1 when the input is a valid Diffie–Hellman tuple and outputs 0 otherwise is shared among all parties.(i) The Key Generation Algorithm
K
G
e
n. It takes a security parameter 1
k where k
∈
N as input and returns the public key P
p
u
b and the master secret key s as shown in Algorithm 1.Algorithm 1:
K
G
e
n
1
k.
Begin
s
←
$
Z
q
∗
P
p
u
b
←
s
P
returns
,
P
p
u
b
EndBecause the total number of time periodsN is already a system-wide public value and the initial key D
0 is not demanded in the proposed scheme, we omit them in the input and output, respectively.(ii) The Device Key Update Algorithm
U
p
d
∗
. In the proposed scheme, the device key update algorithm U
p
d
∗ updates the signing key directly as shown in Algorithm 2.Algorithm 2:
U
p
d
∗
s
,
j.
Begin
returns
⋅
H
2
j
End(iii) The User Key Update Algorithm
U
p
d. The user key update algorithm U
p
d can be defined as an identical transformation to fulfill the definition as shown in Algorithm 3.Algorithm 3:
U
p
d
D
j
′
Begin
returnD
j
′
End(iv) The Undetachable Signing Function Generation Algorithm
U
n
d
S
i
g
F
u
n
G
e
n. First, the customer C generates the description of his/her requirement R
E
Q
_
C. Next, the customer should run the U
n
d
S
i
g
F
u
n
G
e
n algorithm to prepare his/her mobile agent before the agent starts migrating. The process is illustrated in Figure 7 and the algorithm is presented as shown in Algorithm 4.Algorithm 4:
U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C.
Begin
r
←
$
Z
q
∗
U
←
r
H
2
j
h
←
H
1
R
E
Q
_
C
∥
I
D
C
,
U
V
←
r
+
h
D
j
Q
←
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
return a functionf
s
i
g
n
e
d
,
j
x as follows.
Begin
t
←
$
Z
q
R
′
←
t
Q
W
′
←
t
V
returnU
,
V
,
R
′
,
x
V
+
W
′
End
EndFigure 7
Preparation of a mobile agent for migration.(v) The Undetachable Signing Algorithm
U
n
d
S
i
g
n. If a shop owner is going to make a deal with the customer, he/she should generate bid information B
I
D
_
S satisfying R
E
Q
_
C and run the U
n
d
S
i
g
n algorithm on input M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S to sign a contract (see Algorithm 5).Algorithm 5:
U
n
d
S
i
g
n
M
s
g
,
j.
Begin
x
←
H
1
M
s
g
returnz
=
f
S
i
g
n
e
d
,
j
(
x
)
,
j
End(vi) The Undetachable Signature Verification Algorithm
U
n
d
V
r
f
y. Anyone can verify a contract by running the U
n
d
V
r
f
y algorithm that works as shown in Algorithm 6.Algorithm 6:
U
n
d
V
r
f
y
z
,
M
s
g.
Begin
I
D
C
∥
R
E
Q
_
C
∥
B
I
D
_
S
←
M
s
g
U
,
V
,
R
′
,
Z
′
,
j
←
z
If (B
I
D
_
S does NOT satisfy R
E
Q
_
C)
return 0
If0
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
,
V
return 0
Q
¯
←
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
x
¯
←
H
1
M
s
g
If1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
⋅
Q
¯
,
Z
′
return 1
Else
return 0
End


### 4.2. Correctness of the Scheme

First, we prove the correctness of the verification algorithm.Proposition 2.
Ifz
=
U
,
V
,
R
′
,
Z
′
,
j is generated by the undetachable signing algorithm U
n
d
S
i
g
n on M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S and j, and B
I
D
_
S satisfies R
E
Q
_
C, then the verification algorithm U
n
d
V
r
f
y
z
,
M
s
g outputs 1.Proof.
SinceP is a generator of G
1, ∃
k
k
∈
Z
q
∗
∧
k
P
=
H
2
j.
Although it is difficult to calculate the value ofk, the following equations hold:(11)
P
p
u
b
=
s
P
(12)
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
r
H
2
j
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
r
+
h
k
P
(13)
V
=
r
+
h
D
j
=
r
+
h
s
H
2
j
,where(14)
h
=
H
1
R
E
Q
_
C
∥
I
D
C
,
U
.
Thus, according to (11), (12), and (13), we have(15)
1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
,
V
.
Moreover,(16)
R
′
+
x
¯
·
Q
¯
=
R
′
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
+
H
1
M
s
g
·
r
+
h
·
H
2
j
Z
′
=
H
1
M
s
g
V
+
W
′
=
H
1
M
s
g
V
+
t
V
=
H
1
M
s
g
+
t
r
+
h
D
j
=
H
1
M
s
g
+
t
r
+
h
s
H
2
j
.
Because of (11) and (16), we have(17)
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
·
Q
¯
,
Z
′
=
1
.
Hence, the verification algorithmU
n
d
V
r
f
y outputs 1. This completes the proof.The next proposition indicates that the proposed scheme satisfies (2) in Section 2.3.Proposition 3.
LetS
i
g
j
(
x
)
=
R
′
,
x
D
j
+
W
′ and f
x
=
r
+
H
1
R
E
Q
_
C
∥
I
D
C
x; then f
S
i
g
n
e
d
,
j
(
x
)
=
S
i
g
j
∘
f
(
x
).Proof.
Consider the following:(18)
f
S
i
g
n
e
d
x
=
R
′
,
x
V
+
W
′
=
R
′
,
x
r
+
H
1
R
E
Q
_
C
∥
I
D
C
D
j
+
W
′
=
R
′
,
f
x
D
j
+
W
′
=
S
i
g
∘
f
x
.


### 4.3. Security of the Scheme

Theorem 4.
The proposed scheme is a perfectly KIUDS scheme.Proof.
First, we construct a security game which consists of two subgames (Game 1 and Game 2), as shown in Figure8. In this security game, there are three players: A, F, and a simulator of the signature scheme in [31] called C
C
S
(
S
i
m
). The game proceeds in the random oracle model (ROM). A is a PPT adversary against the proposed key-insulated undetachable signature scheme. The message is in the form of M
s
g
=
m
1
,
m
2. The forger F plays between A and C
C
S
S
i
m. A is capable of making queries O
s
,
D
0
E
x
p
o
s
u
r
e
·, O
s
,
D
0
Chosen-restriction
·
,
·, O
H
1
·, and O
H
2
·. F is responsible for answering these queries with the help of C
C
S
(
S
i
m
). C
C
S
(
S
i
m
) should answer queries C
C
S
.
E
x
t
r
a
c
t
·, C
C
S
.
S
i
g
n
·
,
·, C
C
S
.
H
1
·, and C
C
S
.
H
2
·, from F. Note that the input parameter of C
C
S
.
K
G
e
n is the unitary form l
∈
N, where l is the order of P.
Algorithms7 and 8 are used by the forger F to answer queries from the adversary A in the security game.
At the end of the security game, the algorithmF
.
F
o
r
g
e is used to forge a signature of C
C
S
(
S
i
m
) from the output of A. The algorithm F
.
F
o
r
g
e proceeds as shown in Algorithm 9.
Clearly, in the security game that is illustrated in Figure8, we have(19)
S
u
c
c
A
K
I
U
S
k
=
Pr
⁡
1
⟵
K
I
U
D
S
.
U
n
d
V
r
f
y
z
,
M
s
g
=
1
-
Pr
⁡
⊥
⟵
F
.
F
o
r
g
e
z
,
M
s
g
.
Suppose that the adversaryA can win Game 1 that queries O
s
,
D
0
E
x
p
o
s
u
r
e
·, O
s
,
D
0
Chosen-restriction
·
,
·, O
H
1
·, and O
H
2
· at most q
E, q
C, q
O
1, and q
O
2 times, respectively, and has a running time of T
0 and an advantage ε
0. Then, F can win Game 2 with queries C
C
S
.
E
x
t
r
a
c
t
·, C
C
S
.
S
i
g
n
·
,
·, H
1
·, and H
2
· at most q
E, q
C, q
O
1
+
q
C
+
3, and q
O
2
+
q
E
+
q
C
+
2 times, respectively, and has a running time of T
=
T
0
+
c
F and an advantage ε
0
=
S
u
c
c
A
K
I
U
S
k. Recall that the simulator C
C
S
(
S
i
m
) simulates the signature scheme in [31], and therefore Game 2 depicts attacks against the signature scheme in Section 3.1 of [31] in an equivalence form. Based on Lemma  4 in [30] (the Forking Lemma), Theorem  3 in [31] stated that “if there is an algorithm for an adaptively chosen message and ID attack to our scheme which queries H
1, H
2 and Sign and Extract at most q
H
1, q
H
2, q
S, and q
E times, respectively, and has running time t
0 and advantage(20)
ε
0
≥
10
q
S
+
1
q
S
+
q
H
1
q
H
2
l
-
1
,
then the CDHP can be solved with probability≥
1
/
9 and within running time(21)
23
×
q
H
1
×
q
H
2
×
t
0
ε
0
1
-
1
/
l
.
”
By substitutingq
H
1
=
q
O
1
+
q
C
+
3, q
H
2
=
q
O
2
+
q
E
+
q
C
+
2, q
S
=
q
C, q
E
=
q
E, and t
0
=
T
0
+
c
F into (20) and (21), we have that if(22)
ε
0
≥
10
q
C
+
1
2
q
C
+
q
O
1
+
3
q
O
2
+
q
E
+
q
C
+
2
l
-
1
,then the CDHP can be solved with probability no less than 1/9 and within running time(23)
23
q
O
1
+
q
C
+
3
q
O
2
+
q
E
+
q
C
+
2
T
0
+
c
F
ε
0
1
-
1
/
l
.According to the assumption that CDHP is hard, ε
0 is negligible with respect to the value of l, and so is S
u
c
c
A
K
I
U
S
k. This completes the proof.Algorithm 7:
F
.
O
r
a
E
x
p
o(i).
Begin
returnC
C
S
.
E
x
t
r
a
c
t
(
i
)
EndAlgorithm 8:
F
.
O
r
a
C
R(i, R
E
Q
_
C).
Begin
U
,
V
←
C
C
S
.
S
i
g
n
i
,
R
E
Q
_
C
∥
I
D
C
Q
←
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U  C
C
S
.
H
2
j
return a functionf
s
i
g
n
e
d
,
j
x as follows.
Begin
t
←
$
Z
q
R
′
←
t
Q
W
′
←
t
V
returnU
,
V
,
R
′
,
x
V
+
W
′
End
EndAlgorithm 9:
F
.
F
o
r
g
e
(
z
,
M
s
g
).
Begin
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S
←
M
s
g
U
,
V
,
R
′
,
Z
′
,
j
←
z
If (B
I
D
_
S does NOT satisfy R
E
Q
_
C)
retrun ⊥
If0
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U
C
C
S
.
H
2
j
,
V
retrun⊥
Q
¯
←
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U
C
C
S
.
H
2
j
x
¯
←
C
C
S
.
H
1
M
s
g
If1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
⋅
Q
¯
,
Z
′
returnj
,
R
E
Q
_
C
∥
I
D
C
,
U
,
V
Else
return ⊥
EndFigure 8
The security game.


### 4.4. Complexity Analysis

The mathematical operations used in this scheme are mainly scalar addition (SA;Z
q
∗
,
Z
q
∗
→
Z
q
∗), random selection (RS; ←
$
Z
q
∗), scalar multiplication (SM; Z
q
∗
,
G
1
→
G
1), point addition (PA; G
1
,
G
1
→
G
1), bilinear map (BM; e, G
1
×
G
1
→
G
2), and the two hash functions H
1 and H
2. All of these operations are polynomial-bounded and can be computed efficiently.Letq be the size of an element in Z
q
∗ and let S
G
1 be the size of an element in G
1. Let r
e
s be the length of R
E
Q
_
C
∥
I
D
C, m
s
g the length of the M
s
g, and i
m
p
l the size of the implementation of f
s
i
g
n
e
d
,
j without U, V, and Q. In Table 1, we show the numbers of operations needed for the algorithms proposed in Section 4.1.Table 1
The number of operations and size of the input/output of the proposed algorithms.
Algorithm
Complexity
Size of input
Size of output
1
RS + SM
N/A
q   +  S
G
1
2
H
2 + SM
Z
q + log
2
⁡
N
S
G
1
3
N/A
N/A
N/A
4
H
1 + H
2 + SA + RS + 3SM + PA
S
G
1 + |res|
3S
G
1 + |impl|
5
H
1 + RS + SM + PA
|msg| +log
2
⁡
N
4S
G
1 + log
2
⁡
N
6
3H
1 + 2H
2 + 3SM + 3PA + 4BM
4S
G
1 + log
2
⁡
N + |msg|
1


## 4.1. The Algorithms

LetG
1 be a cyclic group generated by a generator P, whose order is a prime number q, and let G
2 be a cyclic multiplicative group of the same order q. Suppose that discrete logarithm problems in both G
1 and G
2 are hard. Let e
:
G
1
×
G
1
→
G
2 be a pairing that satisfies the following three conditions.Bilinear. Equations (5) and (6) together or (7) are as follows:(5)
e
P
1
+
P
2
,
Q
=
e
P
1
,
Q
e
P
2
,
Q
,
(6)
e
P
,
Q
1
+
Q
2
=
e
P
,
Q
1
e
P
,
Q
2
,
(7)
e
a
P
,
b
Q
=
e
P
,
Q
a
b
,where {
a
,
b
}
⊆
Z
q
∗.Nondegenerate. There exist P
∈
G
1 and Q
∈
G
1 subject to(8)
e
P
,
Q
≠
1
.Computability. There is an efficient algorithm to compute e
P
,
Q for all {
P
,
Q
}
⊆
G
1.We note that the Weil and Tate pairings associated with supersingular elliptic curves or abelian varieties can be modified to create such bilinear maps.Suppose thatG is an additive group. Four well-known mathematical problems are defined as follows.(1)
Discrete Logarithm Problem (DLP). Given two group elements P and Q, and an integer n, (9) is satisfied whenever such an integer exists:(9)
Q
=
n
P
.
(2)
Decision Diffie–Hellman Problem (DDHP). For {
a
,
b
,
c
}
⊆
Z
q
∗, given P
,
a
P
,
b
P
,
c
P decide whether(10)
c
≡
a
b
m
o
d
q
.
(3)
Computational Diffie–Hellman Problem (CDHP). For {
a
,
b
}
⊆
Z
q
∗, given P
,
a
P
,
b
P compute a
b
P without any knowledge about the value of either a or b.
(4)
Gap Diffie–Hellman Problem.We assume throughout this paper that CDHP and DLP are intractable, meaning that there is no polynomial time algorithm to solve CDHP or DLP with nonnegligible probability. When the DDHP is easy but the CDHP is hard on groupG
1, G
1 is called a gap Diffie–Hellman (GDH) group. Our scheme can be built on any GDH group. Further mathematical background can be found in [32, 33].We now define some system parameters. LetP be a generator of G
1. Suppose that the total number of time periods N is a shared public value. Two secure hash functions are given here: H
1
:
{
0,1
}
∗
→
Z
q and H
2
:
{
0,1
}
∗
→
G
1. The implementations of these hash functions can be found in works such as [34–36].The public parametersΩ
=
G
1
,
G
2
,
e
(
·
,
·
)
,
q
,
P
,
H
1
,
H
2 should be published to all participants by the trusted authority. Moreover, a public function V
a
l
i
d
T
u
p
l
e that outputs 1 when the input is a valid Diffie–Hellman tuple and outputs 0 otherwise is shared among all parties.(i) The Key Generation Algorithm
K
G
e
n. It takes a security parameter 1
k where k
∈
N as input and returns the public key P
p
u
b and the master secret key s as shown in Algorithm 1.Algorithm 1:
K
G
e
n
1
k.
Begin
s
←
$
Z
q
∗
P
p
u
b
←
s
P
returns
,
P
p
u
b
EndBecause the total number of time periodsN is already a system-wide public value and the initial key D
0 is not demanded in the proposed scheme, we omit them in the input and output, respectively.(ii) The Device Key Update Algorithm
U
p
d
∗
. In the proposed scheme, the device key update algorithm U
p
d
∗ updates the signing key directly as shown in Algorithm 2.Algorithm 2:
U
p
d
∗
s
,
j.
Begin
returns
⋅
H
2
j
End(iii) The User Key Update Algorithm
U
p
d. The user key update algorithm U
p
d can be defined as an identical transformation to fulfill the definition as shown in Algorithm 3.Algorithm 3:
U
p
d
D
j
′
Begin
returnD
j
′
End(iv) The Undetachable Signing Function Generation Algorithm
U
n
d
S
i
g
F
u
n
G
e
n. First, the customer C generates the description of his/her requirement R
E
Q
_
C. Next, the customer should run the U
n
d
S
i
g
F
u
n
G
e
n algorithm to prepare his/her mobile agent before the agent starts migrating. The process is illustrated in Figure 7 and the algorithm is presented as shown in Algorithm 4.Algorithm 4:
U
n
d
S
i
g
F
u
n
G
e
n
D
j
,
R
E
Q
_
C
∥
I
D
C.
Begin
r
←
$
Z
q
∗
U
←
r
H
2
j
h
←
H
1
R
E
Q
_
C
∥
I
D
C
,
U
V
←
r
+
h
D
j
Q
←
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
return a functionf
s
i
g
n
e
d
,
j
x as follows.
Begin
t
←
$
Z
q
R
′
←
t
Q
W
′
←
t
V
returnU
,
V
,
R
′
,
x
V
+
W
′
End
EndFigure 7
Preparation of a mobile agent for migration.(v) The Undetachable Signing Algorithm
U
n
d
S
i
g
n. If a shop owner is going to make a deal with the customer, he/she should generate bid information B
I
D
_
S satisfying R
E
Q
_
C and run the U
n
d
S
i
g
n algorithm on input M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S to sign a contract (see Algorithm 5).Algorithm 5:
U
n
d
S
i
g
n
M
s
g
,
j.
Begin
x
←
H
1
M
s
g
returnz
=
f
S
i
g
n
e
d
,
j
(
x
)
,
j
End(vi) The Undetachable Signature Verification Algorithm
U
n
d
V
r
f
y. Anyone can verify a contract by running the U
n
d
V
r
f
y algorithm that works as shown in Algorithm 6.Algorithm 6:
U
n
d
V
r
f
y
z
,
M
s
g.
Begin
I
D
C
∥
R
E
Q
_
C
∥
B
I
D
_
S
←
M
s
g
U
,
V
,
R
′
,
Z
′
,
j
←
z
If (B
I
D
_
S does NOT satisfy R
E
Q
_
C)
return 0
If0
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
,
V
return 0
Q
¯
←
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
x
¯
←
H
1
M
s
g
If1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
⋅
Q
¯
,
Z
′
return 1
Else
return 0
End


## 4.2. Correctness of the Scheme

First, we prove the correctness of the verification algorithm.Proposition 2.
Ifz
=
U
,
V
,
R
′
,
Z
′
,
j is generated by the undetachable signing algorithm U
n
d
S
i
g
n on M
s
g
=
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S and j, and B
I
D
_
S satisfies R
E
Q
_
C, then the verification algorithm U
n
d
V
r
f
y
z
,
M
s
g outputs 1.Proof.
SinceP is a generator of G
1, ∃
k
k
∈
Z
q
∗
∧
k
P
=
H
2
j.
Although it is difficult to calculate the value ofk, the following equations hold:(11)
P
p
u
b
=
s
P
(12)
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
r
H
2
j
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
r
+
h
k
P
(13)
V
=
r
+
h
D
j
=
r
+
h
s
H
2
j
,where(14)
h
=
H
1
R
E
Q
_
C
∥
I
D
C
,
U
.
Thus, according to (11), (12), and (13), we have(15)
1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
,
V
.
Moreover,(16)
R
′
+
x
¯
·
Q
¯
=
R
′
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
+
H
1
M
s
g
·
U
+
H
1
R
E
Q
_
C
∥
I
D
C
,
U
H
2
j
=
t
+
H
1
M
s
g
·
r
+
h
·
H
2
j
Z
′
=
H
1
M
s
g
V
+
W
′
=
H
1
M
s
g
V
+
t
V
=
H
1
M
s
g
+
t
r
+
h
D
j
=
H
1
M
s
g
+
t
r
+
h
s
H
2
j
.
Because of (11) and (16), we have(17)
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
·
Q
¯
,
Z
′
=
1
.
Hence, the verification algorithmU
n
d
V
r
f
y outputs 1. This completes the proof.The next proposition indicates that the proposed scheme satisfies (2) in Section 2.3.Proposition 3.
LetS
i
g
j
(
x
)
=
R
′
,
x
D
j
+
W
′ and f
x
=
r
+
H
1
R
E
Q
_
C
∥
I
D
C
x; then f
S
i
g
n
e
d
,
j
(
x
)
=
S
i
g
j
∘
f
(
x
).Proof.
Consider the following:(18)
f
S
i
g
n
e
d
x
=
R
′
,
x
V
+
W
′
=
R
′
,
x
r
+
H
1
R
E
Q
_
C
∥
I
D
C
D
j
+
W
′
=
R
′
,
f
x
D
j
+
W
′
=
S
i
g
∘
f
x
.


## 4.3. Security of the Scheme

Theorem 4.
The proposed scheme is a perfectly KIUDS scheme.Proof.
First, we construct a security game which consists of two subgames (Game 1 and Game 2), as shown in Figure8. In this security game, there are three players: A, F, and a simulator of the signature scheme in [31] called C
C
S
(
S
i
m
). The game proceeds in the random oracle model (ROM). A is a PPT adversary against the proposed key-insulated undetachable signature scheme. The message is in the form of M
s
g
=
m
1
,
m
2. The forger F plays between A and C
C
S
S
i
m. A is capable of making queries O
s
,
D
0
E
x
p
o
s
u
r
e
·, O
s
,
D
0
Chosen-restriction
·
,
·, O
H
1
·, and O
H
2
·. F is responsible for answering these queries with the help of C
C
S
(
S
i
m
). C
C
S
(
S
i
m
) should answer queries C
C
S
.
E
x
t
r
a
c
t
·, C
C
S
.
S
i
g
n
·
,
·, C
C
S
.
H
1
·, and C
C
S
.
H
2
·, from F. Note that the input parameter of C
C
S
.
K
G
e
n is the unitary form l
∈
N, where l is the order of P.
Algorithms7 and 8 are used by the forger F to answer queries from the adversary A in the security game.
At the end of the security game, the algorithmF
.
F
o
r
g
e is used to forge a signature of C
C
S
(
S
i
m
) from the output of A. The algorithm F
.
F
o
r
g
e proceeds as shown in Algorithm 9.
Clearly, in the security game that is illustrated in Figure8, we have(19)
S
u
c
c
A
K
I
U
S
k
=
Pr
⁡
1
⟵
K
I
U
D
S
.
U
n
d
V
r
f
y
z
,
M
s
g
=
1
-
Pr
⁡
⊥
⟵
F
.
F
o
r
g
e
z
,
M
s
g
.
Suppose that the adversaryA can win Game 1 that queries O
s
,
D
0
E
x
p
o
s
u
r
e
·, O
s
,
D
0
Chosen-restriction
·
,
·, O
H
1
·, and O
H
2
· at most q
E, q
C, q
O
1, and q
O
2 times, respectively, and has a running time of T
0 and an advantage ε
0. Then, F can win Game 2 with queries C
C
S
.
E
x
t
r
a
c
t
·, C
C
S
.
S
i
g
n
·
,
·, H
1
·, and H
2
· at most q
E, q
C, q
O
1
+
q
C
+
3, and q
O
2
+
q
E
+
q
C
+
2 times, respectively, and has a running time of T
=
T
0
+
c
F and an advantage ε
0
=
S
u
c
c
A
K
I
U
S
k. Recall that the simulator C
C
S
(
S
i
m
) simulates the signature scheme in [31], and therefore Game 2 depicts attacks against the signature scheme in Section 3.1 of [31] in an equivalence form. Based on Lemma  4 in [30] (the Forking Lemma), Theorem  3 in [31] stated that “if there is an algorithm for an adaptively chosen message and ID attack to our scheme which queries H
1, H
2 and Sign and Extract at most q
H
1, q
H
2, q
S, and q
E times, respectively, and has running time t
0 and advantage(20)
ε
0
≥
10
q
S
+
1
q
S
+
q
H
1
q
H
2
l
-
1
,
then the CDHP can be solved with probability≥
1
/
9 and within running time(21)
23
×
q
H
1
×
q
H
2
×
t
0
ε
0
1
-
1
/
l
.
”
By substitutingq
H
1
=
q
O
1
+
q
C
+
3, q
H
2
=
q
O
2
+
q
E
+
q
C
+
2, q
S
=
q
C, q
E
=
q
E, and t
0
=
T
0
+
c
F into (20) and (21), we have that if(22)
ε
0
≥
10
q
C
+
1
2
q
C
+
q
O
1
+
3
q
O
2
+
q
E
+
q
C
+
2
l
-
1
,then the CDHP can be solved with probability no less than 1/9 and within running time(23)
23
q
O
1
+
q
C
+
3
q
O
2
+
q
E
+
q
C
+
2
T
0
+
c
F
ε
0
1
-
1
/
l
.According to the assumption that CDHP is hard, ε
0 is negligible with respect to the value of l, and so is S
u
c
c
A
K
I
U
S
k. This completes the proof.Algorithm 7:
F
.
O
r
a
E
x
p
o(i).
Begin
returnC
C
S
.
E
x
t
r
a
c
t
(
i
)
EndAlgorithm 8:
F
.
O
r
a
C
R(i, R
E
Q
_
C).
Begin
U
,
V
←
C
C
S
.
S
i
g
n
i
,
R
E
Q
_
C
∥
I
D
C
Q
←
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U  C
C
S
.
H
2
j
return a functionf
s
i
g
n
e
d
,
j
x as follows.
Begin
t
←
$
Z
q
R
′
←
t
Q
W
′
←
t
V
returnU
,
V
,
R
′
,
x
V
+
W
′
End
EndAlgorithm 9:
F
.
F
o
r
g
e
(
z
,
M
s
g
).
Begin
I
D
C
∥
R
E
Q
_
C
∥
I
D
S
∥
B
I
D
_
S
←
M
s
g
U
,
V
,
R
′
,
Z
′
,
j
←
z
If (B
I
D
_
S does NOT satisfy R
E
Q
_
C)
retrun ⊥
If0
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U
C
C
S
.
H
2
j
,
V
retrun⊥
Q
¯
←
U
+
C
C
S
.
H
1
R
E
Q
_
C
∥
I
D
C
,
U
C
C
S
.
H
2
j
x
¯
←
C
C
S
.
H
1
M
s
g
If1
=
V
a
l
i
d
T
u
p
l
e
P
,
P
p
u
b
,
R
′
+
x
¯
⋅
Q
¯
,
Z
′
returnj
,
R
E
Q
_
C
∥
I
D
C
,
U
,
V
Else
return ⊥
EndFigure 8
The security game.


## 4.4. Complexity Analysis

The mathematical operations used in this scheme are mainly scalar addition (SA;Z
q
∗
,
Z
q
∗
→
Z
q
∗), random selection (RS; ←
$
Z
q
∗), scalar multiplication (SM; Z
q
∗
,
G
1
→
G
1), point addition (PA; G
1
,
G
1
→
G
1), bilinear map (BM; e, G
1
×
G
1
→
G
2), and the two hash functions H
1 and H
2. All of these operations are polynomial-bounded and can be computed efficiently.Letq be the size of an element in Z
q
∗ and let S
G
1 be the size of an element in G
1. Let r
e
s be the length of R
E
Q
_
C
∥
I
D
C, m
s
g the length of the M
s
g, and i
m
p
l the size of the implementation of f
s
i
g
n
e
d
,
j without U, V, and Q. In Table 1, we show the numbers of operations needed for the algorithms proposed in Section 4.1.Table 1
The number of operations and size of the input/output of the proposed algorithms.
Algorithm
Complexity
Size of input
Size of output
1
RS + SM
N/A
q   +  S
G
1
2
H
2 + SM
Z
q + log
2
⁡
N
S
G
1
3
N/A
N/A
N/A
4
H
1 + H
2 + SA + RS + 3SM + PA
S
G
1 + |res|
3S
G
1 + |impl|
5
H
1 + RS + SM + PA
|msg| +log
2
⁡
N
4S
G
1 + log
2
⁡
N
6
3H
1 + 2H
2 + 3SM + 3PA + 4BM
4S
G
1 + log
2
⁡
N + |msg|
1


## 5. Theoretical Comparison with Related Work

Since the first implementation of undetachable digital signatures was proposed by Kotzanikolaou et al. [3], several concrete constructions of undetachable digital signature schemes have been proposed from 2001 to 2015 [4, 5, 7–10]. Compared with these prior undetachable digital signature schemes, the most significant feature of our proposed scheme lies in its key-insulation property. Different from most of prior studies, we have formally proved the security of the scheme. Moreover, the security of related schemes depends on a variety of diverse assumptions on the computational infeasibility of mathematical problems. Comprehensive comparisons in terms of the above three factors are summarized in Table 2.Table 2
Comparisons of undetachable digital signature schemes.
Scheme
Extra security feature
Formal proof of security
Computational infeasible problem
[3]
No
No
Factorization of big integer
[4]
Bilateral security
No
Factorization of big integer
[5]
No
No
q-Strong Diffie–Hellman problem
[6]
Threshold security
No
Factorization of big integer
[7]
No
No
Discrete logarithm on elliptic curves
[8]
No
No
Computational co-Diffie–Hellman problem
[9]
Threshold security
No
Discrete logarithm on conic curves
[10]
Forward-secure
Yes
Computational co-Diffie–Hellman problem
This work
Key-insulated
Yes
Computational Diffie–Hellman problemThe forward-secure undetachable digital signature (FSUDS) scheme in prior work [10] is currently the latest published study on undetachable signatures. In terms of the security, the “perfectly key-insulated” property implies the “forward-secure” property, but the inverse is not valid. Therefore, the proposed KIUDS scheme is stronger than the FSUDS scheme.Compared with other key-insulated signature schemes, the proposed scheme is undetachable. The private key of the original signer (i.e., the customer) will hardly be compromised, even in a white-box attack context (e.g., a malicious host). For attackers, the misuse of signing functions carried with mobile agents is also infeasible even in white-box attack contexts, because the related restriction is combined with the “encrypted” signing function.We further present the comparison in the field of software obfuscation. Obfuscation is a process that transforms a program into an unintelligible one without changing the original functionalities. If the signing algorithm has been obfuscated, the attacker cannot extract the signing key from the obfuscated implementation. However, it is still an open research problem that whether there exists an obfuscator for the signing algorithm in a digital signature scheme. Some obfuscators for specialized encrypted signatures have been developed since Hada’s work was reported in EuroCrypt 2010 [37]. For example, an obfuscator for encrypted verifiably encrypted signatures [38] and an obfuscator for encrypted group signatures [39] were presented in recent years. However, obfuscated implementation of the generation algorithm of encrypted signatures cannot prevent misusing attacks, (i.e., an attacker can call the algorithm to generate a signature). Therefore, compared with obfuscation approaches for encrypted signatures, the proposed scheme is capable of providing further protection against misuse of the signing algorithm.


## 6. Experimental Results and Comparison

### 6.1. Performance Testing

We have implemented the algorithms in Java. Java has been used instead of C/C++ because many mobile agent platforms are developed in Java, although C/C++ is known to be more efficient. We used an open source Java Pairing-Based Cryptography Library (JPBC) [40] in our implementation. The configurations of the testing platforms are listed in Table 3, and the experimental results are shown in Figures 9 and 10.Table 3
Configurations of testing platforms.
Platform
CPU
RAM
OS
JDK
PC1
Intel Core i5-4200M @ 2.50 GHz
8 GB
Win7
7.0
PC2
Intel Core i5-M480 @ 2.67 Hz
4 GB
Win8
7.0
Server
Intel E5 2.5 G 6Cores∗ 2
96 GB
WinServ2008
7.0Figure 9
Running time (ms) on PC1 and PC2 for each algorithm in the proposed scheme.Figure 10
Number of operations per second on the server for each algorithm in the proposed scheme.When the computing platform is a PC, we focus on the speed of the algorithms. In Figure9, we show the speed of the algorithms on two different portable computers in single-thread mode. When the computing platform is a server, the most important index of performance is the number of transactions that can be processed in a short time span (e.g., a second). Hence, Figure 10 shows the number of operations of each algorithm on a PC server in multithread mode. The experimental results indicate that the algorithms in the proposed scheme are quite efficient.


### 6.2. Experimental Comparison with Related Work

With regard to the standard undetachable digital signature scheme based on bilinear pairings [8] and the FSUDS scheme [10], a group of experimental comparisons on computational costs has been performed on the server described in Table 3. The scheme in [8] has been selected for comparison because it is based on the same mathematical structure as the proposed scheme is. As the standard scheme does not include a key update algorithm, we use “0” to fill the data form. In Figure 11, the result shows that the algorithms of the proposed scheme execute faster than those of the FSUDS scheme, except for the U
n
d
S
i
g
F
u
n
G
e
n algorithm. In particular, the key generation algorithm K
G
e
n of the proposed scheme executes approximately 50 times faster than that of the FSUDS scheme. Furthermore, the performance of the proposed KIUDS scheme is similar to that of the standard scheme (denoted as Std in the figure), but the KIUDS scheme offers higher-level security than the standard scheme does.Figure 11
Comparison on performance of algorithms between the KIUDS and the FSUDS.The sizes of the input/output of the three algorithms (KI, FS, and Std) have also been compared. The result is obtained by analyzing and testing the software implementations of the schemes. As shown in Figure12, most of the algorithms of the KIUDS scheme have smaller inputs and outputs than those of the FSUDS scheme. Furthermore, although the sizes of the inputs of U
n
d
S
i
g
F
u
n
G
e
n and U
n
d
V
r
f
y and the output of U
n
d
S
i
g
F
u
n
G
e
n of the KIUDS scheme are larger than those of the standard scheme, the increased cost is acceptable in consideration of acquiring extra key-insulated security.Figure 12
Comparisons on sizes of inputs/outputs of algorithms (in byte).


### 6.3. An Example of KIUDS Implementation

To further demonstrate the feasibility of the proposed scheme in practice, we have implemented a KIUDS solution for purchasing/selling books with mobile agents as a concrete example. The implementation is based on theJava Agent DEvelopment Framework (JADE) [41], which is an open source software framework that supports implementation of multiagent systems through a middleware complying with the FIPA specifications [42] and a set of tools supporting debugging and deployment phases. A JADE-based system can be distributed across various hosts while the configuration can be controlled via remote connections. The configuration can even be modified at run-time by moving agents from one host to another as necessary.As an example, we created three instances of e-bookstores that sell books and a buyer agent that represents a customer who purchases books. Each e-bookstore has a number of books for sale with specified prices. The buyer agent aims to purchase the cheapest copy of the book titled “Thinking in Java” by visiting the three e-bookstores in an autonomous manner and comparing the prices retrieved. When the buyer agent purchases the book, a KIUDS is generated to sign the contract. Figure 13 illustrates the process of the book purchasing example.Figure 13
An example of buying and selling books.The implementation has demonstrated the feasibility of the KIUDS scheme and solution, which serves as a proof-of-concept that complements the theoretical analysis and comparisons in previous sections. We also plan to further apply the KIUDS solution in more domains and identify more research issues that are worth in-depth exploration and study in future work.


## 6.1. Performance Testing

We have implemented the algorithms in Java. Java has been used instead of C/C++ because many mobile agent platforms are developed in Java, although C/C++ is known to be more efficient. We used an open source Java Pairing-Based Cryptography Library (JPBC) [40] in our implementation. The configurations of the testing platforms are listed in Table 3, and the experimental results are shown in Figures 9 and 10.Table 3
Configurations of testing platforms.
Platform
CPU
RAM
OS
JDK
PC1
Intel Core i5-4200M @ 2.50 GHz
8 GB
Win7
7.0
PC2
Intel Core i5-M480 @ 2.67 Hz
4 GB
Win8
7.0
Server
Intel E5 2.5 G 6Cores∗ 2
96 GB
WinServ2008
7.0Figure 9
Running time (ms) on PC1 and PC2 for each algorithm in the proposed scheme.Figure 10
Number of operations per second on the server for each algorithm in the proposed scheme.When the computing platform is a PC, we focus on the speed of the algorithms. In Figure9, we show the speed of the algorithms on two different portable computers in single-thread mode. When the computing platform is a server, the most important index of performance is the number of transactions that can be processed in a short time span (e.g., a second). Hence, Figure 10 shows the number of operations of each algorithm on a PC server in multithread mode. The experimental results indicate that the algorithms in the proposed scheme are quite efficient.


## 6.2. Experimental Comparison with Related Work

With regard to the standard undetachable digital signature scheme based on bilinear pairings [8] and the FSUDS scheme [10], a group of experimental comparisons on computational costs has been performed on the server described in Table 3. The scheme in [8] has been selected for comparison because it is based on the same mathematical structure as the proposed scheme is. As the standard scheme does not include a key update algorithm, we use “0” to fill the data form. In Figure 11, the result shows that the algorithms of the proposed scheme execute faster than those of the FSUDS scheme, except for the U
n
d
S
i
g
F
u
n
G
e
n algorithm. In particular, the key generation algorithm K
G
e
n of the proposed scheme executes approximately 50 times faster than that of the FSUDS scheme. Furthermore, the performance of the proposed KIUDS scheme is similar to that of the standard scheme (denoted as Std in the figure), but the KIUDS scheme offers higher-level security than the standard scheme does.Figure 11
Comparison on performance of algorithms between the KIUDS and the FSUDS.The sizes of the input/output of the three algorithms (KI, FS, and Std) have also been compared. The result is obtained by analyzing and testing the software implementations of the schemes. As shown in Figure12, most of the algorithms of the KIUDS scheme have smaller inputs and outputs than those of the FSUDS scheme. Furthermore, although the sizes of the inputs of U
n
d
S
i
g
F
u
n
G
e
n and U
n
d
V
r
f
y and the output of U
n
d
S
i
g
F
u
n
G
e
n of the KIUDS scheme are larger than those of the standard scheme, the increased cost is acceptable in consideration of acquiring extra key-insulated security.Figure 12
Comparisons on sizes of inputs/outputs of algorithms (in byte).


## 6.3. An Example of KIUDS Implementation

To further demonstrate the feasibility of the proposed scheme in practice, we have implemented a KIUDS solution for purchasing/selling books with mobile agents as a concrete example. The implementation is based on theJava Agent DEvelopment Framework (JADE) [41], which is an open source software framework that supports implementation of multiagent systems through a middleware complying with the FIPA specifications [42] and a set of tools supporting debugging and deployment phases. A JADE-based system can be distributed across various hosts while the configuration can be controlled via remote connections. The configuration can even be modified at run-time by moving agents from one host to another as necessary.As an example, we created three instances of e-bookstores that sell books and a buyer agent that represents a customer who purchases books. Each e-bookstore has a number of books for sale with specified prices. The buyer agent aims to purchase the cheapest copy of the book titled “Thinking in Java” by visiting the three e-bookstores in an autonomous manner and comparing the prices retrieved. When the buyer agent purchases the book, a KIUDS is generated to sign the contract. Figure 13 illustrates the process of the book purchasing example.Figure 13
An example of buying and selling books.The implementation has demonstrated the feasibility of the KIUDS scheme and solution, which serves as a proof-of-concept that complements the theoretical analysis and comparisons in previous sections. We also plan to further apply the KIUDS solution in more domains and identify more research issues that are worth in-depth exploration and study in future work.


## 7. Conclusion

In this paper, we introduce the definition and provide the security model and security notion of KIUDS schemes. KIUDS schemes are capable of protecting the digital signature functionality against attacks from remote malicious hosts and controlling the security risk of signing key leakage on the original signer’s host at the same time. Practically, a concrete KIUDS scheme with provable security is proposed for secure mobile agents in electronic commerce. The scheme is constructed on bilinear pairings and the security of the scheme is proven to rely on the hardness of the computational Diffie–Hellman problem on gap Diffie–Hellman groups which is infeasible to solve in practice. Our experimental results have demonstrated that the proposed scheme is efficient.



---

*Source: 4375072-2016-06-20.xml*