Secure Mobile Agents in eCommerce with Forward-Secure Undetachable Digital Signatures

ETRI Journal.
2015.
May,
37(3):
573-583

- Received : June 03, 2014
- Accepted : March 19, 2015
- Published : May 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

We introduce the idea of a forward-secure undetachable digital signature (FS-UDS) in this paper, which enables mobile agents to generate undetachable digital signatures with forward security of the original signer’s signing key. The definition and security notion of an FS-UDS scheme are given. Then, the construction of a concrete FS-UDS scheme is proposed; and the proof of security for the proposed scheme is also provided. In the proposed scheme, mobile agents need not carry the signing key when they generate digital signatures on behalf of the original signer, so the signing key will not be compromised. At the same time, the encrypted function is combined with the original signer’s requirement; therefore, misuse of the signing algorithm can be prevented. Furthermore, in the case where a hacker has accessed the signing key of the original signer, he/she is not able to forge a signature for any time period prior to when the key was obtained.
mobile agents
and
platforms
. An
agent
is a type of computer software that acts autonomously on behalf of a person or an organization
[1]
.
Platforms that can create, execute, interpret, transfer, and terminate agents are
agent systems
. Mobile agents have a high mobility to transport themselves from one platform in a network to another and can automatically suspend execution on one platform and migrate to another to resume their computations. The ability to travel enables a mobile agent to move to a destination agent system that contains an entity in which the agent wants to interact.
The advent of electronic commerce practices has increased the demand for interoperable applications that allow for the flexible exchange of data across enterprise borders, different IT-platforms, and different information systems. For example, an intelligent trade agent (ITA) that roams a network
[2]
buying and selling goods through three different merchant’s hosts within a network is shown in
Fig. 1
. Moreover, many mobile agent–based technologies have been developed and put into practice, such as those in
[3]
–
[8]
.
ITA roams network buying and selling goods.
The aforementioned applications cannot be realized securely without suitable security technologies. However, the fact is that mobile agents are exposed to serious security threats; for example, malicious hosts might endanger passing mobile agents. As security threats have become a bottleneck in the development and maintenance of mobile agent–based applications
[9]
, there has become an urgent calling for efficient and practical security solutions that can achieve a good balance between security and mobility in mobile agent–related studies.
Security problems of mobile agent systems stemming from the mobility of mobile agents can be categorized into the following two subjects
[10]
: agent-side security and platform-side security. This study focuses on agent-side security and aims to provide a practical security solution under mobility. Furthermore, the study addresses the worst situation of agent-side threats when the agents run in an untrusting environment or, more specifically, the agents are subject to attacks from malicious platforms. Because mobile agents frequently migrate among various hosts (platforms
) due to their mobility, they run the risk of exposing themselves to untrusting environments more often than static agents. In such environments, the proposed forward-secure undetachable digital signature technique can provide the integrity and validity of business contracts, as well as safeguarding the confidentiality of the user’s private signing key.
Segment of Java byte code of agent.
Hence, Sander and Tschudin proposed the idea of undetachable digital signatures
[12]
, which allows a mobile agent to effectively produce a digital signature inside a remote and possibly malicious host without the host being able to deduce the agent’s secret (for example, the signing key) or reuse the implementation of the signing algorithm for arbitrary documents.
The general mathematical description of an undetachable signature function is as follows. Suppose that Sig is the signing algorithm used by
C
(a customer) to produce the digital signature
z
= Sig(
m
) for an arbitrary message
m
. The undetachable signing algorithm
f
_{Signed}
should subject to (1), where
f
is an auxiliary binding function.
(1) $${f}_{\text{Signed}}=\text{Sig}\circ f.$$
To create an undetachable signature on a shop’s server, (2) is computed by calling
f
_{Signed}
from the customer’s mobile agent.
(2) $$z={f}_{\text{Signed}}(m).$$
Although the signature function Sig is not known by others, everyone can verify the validity of message
m
by using a specialized verification algorithm.
Since the first concrete construction of an undetachable digital signature based on RSA
[13]
was published in 2001, a variety of undetachable signature schemes have been proposed
[13]
–
[17]
. The latest one to date,
[18]
, is a threshold version using conic curves, which was proposed in 2013.
At the same time, digital signature schemes also face a significant key leakage problem on the original signer’s local host, while undetachable signatures only protect the signing key from leakage on potentially malicious remote hosts. In the event that the customer’s host is infiltrated by an attacker, there would be a serious security problem because the original private signing key would be compromised.
The possibility of the occurrence of this security problem increases with the fast development of advanced persistent threats (APTs), such as “Operation Aurora” and “Stuxnet Worm.”
Intuitively, a forward-secure signature technique could be used to control this risk. The principles behind forward-secure signature schemes are discussed briefly in
[19]
–
[21]
. In these schemes, the whole lifetime of a cryptosystem is divided into a number of time periods. At the end of each time period, the user computes a new signing key for the next time period using a one-way function and the old key is then erased. In this way, the user’s singing key changes for different time periods, but the public key (verification key) is fixed during the whole lifetime. Each signature is associated with one time period, and the validity of a time period needs to be verified during signature verification. As a result, an adversary cannot forge any signature of any time period prior to the time when they obtained the signing key (for example, via cracking the host of the signer).
Traditional undetachable signature techniques (for example,
[13]
–
[18]
) mainly focus on protecting the signing key from being compromised, as well as preventing the misuse of the signature function/algorithm on malicious shop servers. On the other hand, normal forward-secure signature schemes do not fulfill the undetachable property, which is required to sign a contract securely by using a mobile agent on remote and potentially malicious hosts.
To fix this gap, we introduce the idea of a forward-secure undetachable digital signature (FS-UDS). The definition and security notion of an FS-UDS are given. Then, the construction of a concrete FS-UDS is proposed. The proposed FS-UDS enables mobile agents to generate undetachable digital signatures with forward security of the original signer’s signing key. The main novelties of the scheme are as follows:
To introduce the concrete scheme, we first give the formal definition and security notions of undetachable signature schemes in the next section. These are also contributions to theoretical aspects of mobile agent security.

Definition 1.
An FS-UDS FSUSig = (
KGen
,
KUpd
,
Sign
,
Vrfy
,
UndSigFunGen
,
UndSig
,
UndVrfy
) consists of the following seven algorithms:
FSUSig
= (
KGen
,
KUpd
,
Sign
,
Vrfy
,
UndSigFunGen
,
UndSig
,
UndVrfy
). An adversary,
F
, is viewed as functioning in three stages — the chosen message attack and chosen restriction attack phase; the break-in phase (breakin); and the forgery phase (forge). Its success probability in breaking the forward-security of the undetachable signature scheme is evaluated by the following two experiments. Note that we write 1
^{k}
, ... ,
T
as the arguments to the key generation algorithm to indicate the possible presence of extra arguments.

I. Introduction

With the fast development of distributed computing technologies, mobile agent systems and related technologies have attracted great interest. A mobile agent system consists primarily of
PPT Slide

Lager Image

II. Mobile Agent Security and Undetachable Digital Signatures

The protection of a mobile agent from possible attacks by malicious hosts is referred to as the problem of malicious hosts. Hohl
[11]
identified a considerable number of such attacks including spying out code, data, and control flow; manipulation of code, data, and control flow and so on. Thus, threats from potentially malicious hosts have become a great obstacle to the widespread deployment of mobile agent technology–based applications in electronic commerce.
In traditional digital signature schemes, mobile agents need to carry the implementation of the signing algorithm with the private key to generate signatures on behalf of the original user, so an adversary can misuse the signing algorithm or even extract the private signing key from the agent. For example, an attacker who has control of a malicious host can find the signing key from Java byte code, as illustrated in
Fig. 2
(that is, a screen snapshot of a Hex file editor).
PPT Slide

Lager Image

- ■ It takes into account both the security of the customer’s host and the security of shop servers.
- ■ It is the first undetachable digital signature scheme that supports forward-secure key evolvement. Although there are many published forward-secure signature schemes, it is not a trivial work to design a scheme that fulfills the undetachable property given by equation (1).
- ■ It is carefully designed such that the security of the scheme can be reduced to that of solving a hard mathematical problem (that is, the computational co-Diffie–Hellman problem on a co-GDH group pair).

III. Definition and Security Notions

- 1. Definition

In this section, the definition of an FS-UDS is proposed. Furthermore, the security notions of FS-UDS are given. Before the definition, we first list frequently used symbols in
Table 1
.
Frequently used symbols.

Symbol | Description |
---|---|

1^{k} | Security parameter, |

_{0} | Base public key |

_{0} | Base secret key (signing key) |

Index of the time period | |

_{j}_{j−1} | Secret signing key of the time period |

_{j} | Certification (of underlying public key) of the period |

_{C} | Customer |

_{Signedi} | Implementation of undetachable signing function of time period |

Auxiliary function of _{Signedi} | |

Message (usually a contract) | |

Undetachable signature | |

_{j} | Normal signatures |

- ■ The key generation algorithm,KGen, takes as input a security parameter, 1k, wherek∈ ℕ; the total number of periodsTover which the scheme will operate; and possibly other parameters to return a base public key,U0, and corresponding base secret key (signing key),s0. The algorithm is probabilistic.
- ■ The secret key update algorithm,KUpd, takes as input the secret signing key of the previous period,sj–1, to return the secret signing key of the current period,sj. The algorithm is usually deterministic.
- ■ The undetachable signing function generation algorithm,UndSigFunGen, is a probabilistic polynomial-time algorithm, which takes the requirement of a customer,REQ_C; the customer’s identity,IDC; and the customer’s public key and private key of the current period as inputs. The algorithm outputs a pair of functions,f(·) andfSignedj(·).
- ■ The undetachable signing algorithm,FSUndSig, is a polynomial-time algorithm, which takes the contract (or a relative hash value) as input. The algorithm outputs an undetachable digital signaturez=ζj= 〈ζ,j〉.
- ■ The undetachable signature verification algorithm,UndVrfy, is a polynomial-time algorithm, which takes the contract and an undetachable signaturezas input. The algorithm outputs either “Accept” or “Reject,” simply “1” or “0.”
- ■ The signing algorithm,Sign, takes the secret signing key of the current period,sj, and a message,M, to return a signature ofMfor periodj. We write this asσj←Signsj(M). The algorithm might be probabilistic. The signature is always a pair consisting of the valuejof the current period and a tagσ.
- ■ The verification algorithm,Vrfy, takes the public key (PK), message (M), and candidate signature (〈j,σ〉) to return a bit, with “1” meaning accept and “0” meaning reject. We write this asb←VrfyU0(M, 〈j,σ〉).

- 2. Security Notions

For the formalization of the security definition, we set up a fixed key-evolving undetachable signature scheme
Experiment FU-ForgeSig(FSUndSig,F, 1 k , ... ,T) ( U 0 , s 0 ) ← $ KGen( 1 k , ... ,T) ; j←0 Repeat j←j+1 ; s j ←KUpd( s j−1 ) d← F Sig n s j (⋅),UndSigFunGe n s j (⋅) (CMA−CRA, U 0 ) Until( ( d=breakin )∨( j=T ) ) If( ( d≠breakin )∧( j=T ) ) j←T+1 ( 〈 σ,b 〉,M )←F( forge, s j ) If( ( Vrf y U 0 ( 〈 σ,b 〉,M )=1 )∧( 1≤b
In the experiment FU-ForgeSig,
Sign_{sb}
(•) of period
b
and the undetachable signature function generation query
UndSigFunGen_{SKb}
(•) of period
b
, respectively.

L b Sign

and
L b UndSigFunGen

are the query lists coming from the signing query
Experiment FU-ForgeUndSig(FSUndSig,F, 1 k , ... ,T) ( U 0 , s 0 ) ← $ KGen( 1 k , ... ,T) ; j←0 Repeat j←j+1 ; s j ←KUpd( s j−1 ) d← F Sig n s j (⋅),UndSigFunGe n s j (⋅) (CMA−CRA, U 0 ) Until( ( d=breakin )∨( j=T ) ) If( ( d≠breakin )∧( j=T ) ) j←T+1 ( 〈 ζ,b 〉,RES,M )←F( forge, s j ) If( ( UndVrf y U 0 ( 〈 ζ,b 〉,RES,M )=1 )∧( 1≤b
In the experiment FU-ForgeUndSig,
Sign_{SKb}
(•) of period
b
and the undetachable signature function generation query
UndSigFunGen_{SKb}
(•) of period
b
, respectively.
Remark 1.
RES
is a restriction. It is usually in the form of
REQ
||
ID_{C}
, where
REQ
is the requirement of a customer (
C
) and
ID_{C}
is the customer’s identity.
Definition 2.
The insecurity function of
FSUndSig
is defined as
(3) $$\begin{array}{l}\text{InSec}(FSUndSig,{1}^{k},\text{\hspace{0.17em}\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}\hspace{0.17em}},T;\tau ,{q}_{s},{q}_{u})=\underset{F=\langle {F}_{1},{F}_{2}\rangle}{\text{Max}}\\ \left\{\mathrm{Pr}\left[\begin{array}{l}\left(1=\text{FU-ForgeSig}\left(FSUndSig,{F}_{1},{1}^{k},\text{\hspace{0.17em}\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}\hspace{0.17em}},T\right)\right)\vee \\ \left(1=\text{FU-ForgeUndSig}\left(FSUndSig,{F}_{2},{1}^{k},\text{\hspace{0.17em}\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}\hspace{0.17em}},T\right)\right)\end{array}\right]\right\}.\end{array}$$
The maximum here is over all
F
= 〈
F
_{1}
,
F
_{2}
〉 for which the following are true: the execution time of the above two experiments, plus the size of the code of
F
, is at most
t
;
F
makes a total of at most
q_{s}
queries to the signing oracles and at most
q_{u}
queries to the undetachable signature function generation oracles across all the stages in all experiments.
Remark 2.
The execution time is that of the entire experiment, not just that of
F
. So, it includes, in particular, the time to compute answers to oracle queries.
Remark 3.
We suppose that there exists an isomorphism
ψ
(
P
) =
G
.
Definition 3.
Decision co-Diffie–Hellman (co-DDH) problem on
P
,
P^{a}
∈
G
_{2}
and
Y
,
Y^{b}
∈
G
_{1}
as input, the solution of the problem is “yes” if
a
=
b
, otherwise it is “no.” Note that when the solution is “yes,” we say that (
P
,
P^{a}
,
Y
,
Y^{b}
) is a co-Diffie–Hellman tuple (co-DHT).
Assumption 1.
We suppose that
Definition 4.
Computational co-Diffie–Hellman (co-CDH) problem on
g
_{2}
,
g
_{2}
^{a}
∈
h
∈
h^{a}
∈
Definition 5.
We say that an algorithm (
t
',
ε
') -breaks co-CDH on
t
') and successfully solves the co-CDH problem on
ε
'.
Definition 6.
Two groups,
λ
,
t
',
ε
') gap Diffie–Hellman group pair (co-GDH) if they satisfy the following properties:
Assumption 2.
The two order-
q
groups
λ
,
t
',
ε
') -bilinear group pair; that is, they satisfy the following properties:
Because we can efficiently solve the co-DDH problem by computing two bilinear maps, if two groups
λ
,
t
',
ε
') -bilinear group pair, then they are also a (2
λ
,
t
',
ε
') -co-GDH group pair.
Based on the above computational assumption, we propose a concrete and effective FS-UDS. The short signature scheme in
[22]
and the forward-secure signatures generation technique in
[23]
are used as building blocks in the proposed scheme.
KGen
,
KUpd
,
UndSigFunGen
,
UndSig
,
UndVrfy
,
Sig
, and
Vrfy
, as follows:
Proposition 1.
Let
Sig_{sj, j}
(
x
) = 〈〈
CERT_{j}
,
x^{sj}
〉,
j
〉, for each
j
∈ {1, 2, ... ,
T
} , then the function pair
f
_{Signedj}
and
f
generated by
UndSigFunGen
satisfies (1).
Proof.
For any
j
∈ {1, 2, ... ,
T
} , we have
$$\begin{array}{l}(Si{g}_{{s}_{j},j}\circ f)(x)=Si{g}_{{s}_{j},j}({H}^{x})=\langle \langle CER{T}_{j},{({H}^{x})}^{{s}_{j}}\rangle ,j\rangle \\ =\langle \langle CER{T}_{j},{({H}^{{s}_{j}})}^{x}\rangle ,j\rangle =\langle \langle CER{T}_{j},{K}^{x}\rangle ,j\rangle ={f}_{Signe{d}_{j}}(x).\end{array}$$
It is not difficult to validate the correctness of
UndVrfy
and
Vrfy
, so we omit the proofs.

The performance results of the proposed algorithms on the platforms are listed in
Table 3
. The input and output sizes of the algorithms are also provided. Moreover, results of another undetectable digital signature scheme
[16]
without forward security is appended at the end of the table for comparison.
According to
Table 3
, all the algorithms in both schemes work fine on either a PC or a server. For algorithms that are frequently used in both schemes (that is,
Sign
,
Vrfy
,
UndSigFunGen
,
UndSig
, and
UndVrfy
), although the time and space cost of the proposed algorithms are a little more than the ones in
[16]
, the largest difference is only 45 ms on time cost and 387 bytes on space cost. Importantly, the sacrifice of these small costs brings the forward-security. The new forward-secure signature scheme is capable of protecting the signing key in both the original signer’s host and the remote servers. As for the
KeyGen
algorithm, it is only used once for each user in the initialization stage. Therefore, it brings little burden to the mobile agent system, even though the
KeyGen
algorithm needs more time than the one in
[16]
.

Theorem 1.
Suppose that Assumption 2 is true, then for the proposed FS-UDS scheme, and for any
τ
<
t
', the insecurity function that is defined in (3) satisfies (4).
(3) $$\begin{array}{l}\text{InSec}(FSUndSig,{1}^{k},\text{\hspace{0.17em}\hspace{0.17em}}\mathrm{...}\text{\hspace{0.17em}\hspace{0.17em}},T;\tau ,{q}_{s},{q}_{u})\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}\le e({q}_{s}^{(1)}+{q}_{s}^{(2)}+{q}_{u}^{(1)}+{q}_{u}^{(2)}+1)\cdot {\epsilon}^{\ufe32}.\end{array}$$
Proof.
The first step of this proof is to adapt the forgery experiments to the proposed concrete construction as follows:

T b Sign

and
T b UndSigFunGen

are the query lists coming from the signing query
IV. Concrete Construction

- 1. Public Setting

The pubic setting
Ω=( G 1 , G 2 , e ^ (⋅,⋅),q,P, H 1 (⋅), H 2 (⋅) )

consists of the following components and algorithms:
- ■G1is a multiplicative cyclic group of prime orderq,G2is also a multiplicative cyclic group of the same order.
- ■GandPare fixed generators ofG1andG2, respectively.
- ■e^:G1×G2→GTis a bilinear map.
- ■H1:{0,1}*→Zq*andH2:{0,1}*→G1are two specialized hash maps.

ψ: G 2 → G 1

with
- 2. Mathematical Problems and Computational Assumptions

( G 1 , G 2 )

: Given
e ^

can be effectively computed, so the co-DDH problem on
( G 1 , G 2 )

is easy to solve.
( G 1 , G 2 )

: Given
G 2

and
G 1

as input, the solution of the problem is (to compute)
G 1

.
( G 1 , G 2 )

if the algorithm runs in time (that is, within
( G 1 , G 2 )

with a probability of at least
( G 1 , G 2 )

, are a (
- ■ The group operation on bothG1andG2and the mapψfromG2toG1can be computed in at most timeλ.
- ■ The co-DDH problem on(G1,G2)can be solved in at most timeλ.
- ■ No algorithm (t',ε') breaks the co-CDH problem on(G1,G2).

( G 1 , G 2 )

in the public setting are a (
- ■ The group operation on bothG1andG2and the mapψfromG2toG1can be computed in at most timeλ.
- ■ A groupGTof orderqand a bilinear mape^:G1×G2→GTexist, ande^is computable in at most timeλ.
- ■ No algorithm (t',ε') -breaks the co-CDH problem on(G1,G2).

( G 1 , G 2 )

are a (
- 3. Algorithms

The proposed FS-UDS consists of seven algorithms; that is,
- 4. Proof of Correctness

The following proposition shows that the proposed scheme is a “correct” FS-UDS scheme.
- 5. Experimental Performance Analysis

We have implemented the algorithms in Java. Java has been used instead of C/C++ because many mobile agent platforms are developed in Java. An open-source Java Pairing-Based Cryptography Library (JPBC)
[24]
is used in our implementation. The performance is tested on both a portable PC and a server. The configurations of these platforms are listed in
Table 2
.
Configurations of testing platforms.

Platform | CPU | RAM | OS | JDK |
---|---|---|---|---|

PC | 1.7 G 2Cores | 4 GB | Win7 | 7.0 |

Server | 2.5 G 6Cores × 2 | 96 GB | WinServ2008 | 7.0 |

Results of performance tests.

Algorithm | Time (ms) | Size (byte) | |||
---|---|---|---|---|---|

PC | Server | Input | Output | ||

Ours | 663 | 610 | 2 | 148 | |

66 | 65 | 534 | 20 | ||

46 | 44 | 149 | 514 | ||

101 | 101 | 771 | 1 | ||

46 | 43 | 535 | 642 | ||

15 | 13 | 128 | 514 | ||

115 | 114 | 901 | 1 | ||

17 | 15 | 2 | 148 | ||

52 | 50 | 148 | 128 | ||

57 | 56 | 384 | 1 | ||

56 | 51 | 150 | 256 | ||

16 | 15 | 128 | 128 | ||

76 | 72 | 514 | 1 |

- 6. Theoretical Security Analysis

In this subsection, we prove the security of the proposed scheme based on Assumption 2. The co-CDH problem is computationally infeasible in many algebra structures, such as Weil pairings; so, Assumption 2 is widely used in security schemes. We use this assumption as a mathematical basis for the proposed FS-UDS scheme.
Game FU-ForgeSig( FSUndSig[ 1 k ,r,T], F 1 ) , 〈 U 0 , s 0 〉←KGen( 1 k ,r,T) ; j←0 Repeat j←j+1 ; s j ←KUpd( s j−1 ); d← F 1 [ O FSUndSig.Sig n s j ( ⋅ ) , O FSUndSig.UndSigFunGe n s j ( ⋅ ) ]( CMA−CRA, U 0 ) Until( ( d=breakin )∨( j=T ) )

If( ( d≠breakin )∧( j=T ) ) j←T+1 ( 〈 σ,b 〉,M )← F 1 ( forge, s j )

If( ( FSUndSig.Vrfy( U 0 ,〈 σ,b 〉,M )=1 ) ∧( 1≤b
C
_{1}
plays the game FU-ForgeSig with
F
_{1}
as shown in the left part of
Fig. 3
and plays the game F-ForgeSig with another intermediate player
A
as shown in the right part of
Fig. 3
. Similarly, an intermediate
C
_{2}
plays the game FU-ForgeUndSig with
F
_{1}
as shown in the left part of
Fig. 4
and plays the game F-ForgeSig with another intermediate player
A
as shown in the right part of
Fig. 4
.
As shown in
Figs. 3
and
4
, the intermediate players
C
_{1}
and
C
_{2}
have some algorithms that help them to play the games. The descriptions of these algorithms are as follows:
C _{1} plays between F _{1} and A .
C _{2} plays between F _{2} and A .
Moreover, the game F-ForgeSign is the normal security game that is widely used in the research of forward-secure signature schemes. F-ForgeSign proceeds as follows:

Game FU-ForgeUndSig( FSUndSig[ 1 k ,r,T ], F 2 ) 〈 U 0 , s 0 〉←KGen( 1 k ,r,T ) ; j←0 Repeat j←j+1 ; s j ←KUpd( s j−1 ); d← F 1 [ O FSUndSig.Sig n s j ( ⋅ ) , O FSUndSig.UndSigFunGe n s j ( ⋅ ) ]( CMA−CRA, U 0 )

Until( ( d=breakin )∨( j=T ) ) If( ( d≠breakin )∧( j=T ) ) j←T+1 ( 〈 ζ,b 〉,RES,M )← F 2 ( forge, s j ) If( ( UndVrfy( U 0 ,〈 ζ,b 〉,RES,M )=1 )∧( 1 ≤ b < j ) ∧( RES∉ T b Sign )∧( RES∉ T b UndSigFunGen ) )return 1 Else return 0

The second step proceeds with the help of some intermediate players and transitivity security games. An intermediate player
PPT Slide

Lager Image

PPT Slide

Lager Image

Game F-ForgeSign( FSSig[ 1 k ,r,T], C i ) //i = 1,2 〈 U 0 , s 0 〉←FSSig.KGen( 1 k ,r,T) ; j←0 Repeat j←j+1 ; s j ←FSSig.KUpd( s j−1 ); d← C i [ O FSSig.Si g s j ( ⋅ ) ]( CMA, U 0 ) Until( ( d=breakin )∨( j=T ) ) If( ( d≠breakin )∧( j=T ) ) j←T+1 ( 〈 σ,b 〉,M )← C i (forge, s j ) If( ( FSSig.Vrfy( U 0 ,〈 σ,b 〉,M ) = 1 )∧( 1 ≤ b
A
playing the game F-ForgeSign with
C_{i}
(
i
= 1 or 2) as shown in the left part of
Fig. 5
and playing the game CMA with another player
S
as shown in the right part of
Fig. 5
. CMA is a standard message attack game, so we omit the description of this game. As shown in
Fig. 5
, the intermediate player
A
has some algorithms to help him play the games. The descriptions of these algorithms are as follows:
A plays between C_{i} and S .
After these steps, we can immediately find that a successful forgery of
F
can be reduced to a successful forgery of the BLS signature. Finally, we estimate the cost and probability of a successful forgery.
Suppose that
F_{i}
(
i
= 1 or 2) can win the game that queries
O
^{FSUndSig.H1(•)}
,
O
^{FSUndSig.H2}
(·),
O^{IDSig}
(·,·),
O
^{H3}
(·), and
O
^{H2}
(·) at most
τ_{i}
and an advantage
ε_{i}
. That is,
F
_{1}
is a
FSUndSig.Sig
or
F
_{2}
is a
FSUndSig.UndSig
.
Let
c
_{exp}
be the time of computing an exponentiation in
c_{rng}
be the time of generating a random element of
τ
, if
$$\tau \le \left(\begin{array}{l}{t}^{\ufe32}-{c}_{\mathrm{exp}}\left(\begin{array}{l}2\left({q}_{{H}_{2}}^{(1)}+{q}_{{H}_{2}}^{(2)}+{q}_{u}^{(1)}+{q}_{u}^{(2)}\right)\\ +\text{\hspace{0.17em}\hspace{0.17em}}3\left({q}_{s}^{(1)}+{q}_{s}^{(2)}+{q}_{u}^{(1)}+{q}_{u}^{(2)}\right)+2T\end{array}\right)\\ -\left(2T+{q}_{{H}_{1}}^{(1)}+{q}_{{H}_{1}}^{(2)}\right)\cdot {c}_{rng}\end{array}\right),$$
then
UndVrfy
), then the attacker is also capable of breaking the BLS signature scheme (that is, successfully forge a signature generated by the BLS signing algorithm). Secondly, we perform an experiment to show that a forgery of the BLS signature can support someone else to solve the co-CDH problem. The sketch of experimental security analysis is illustrated in
Fig. 6
.
Sketch of security experiments.
In practical applications, sufficiently large security parameters should be used. In fact, in performance testing, we also use sufficiently large security parameters. However, to enable “an attacker” to successfully break the proposed scheme, very small security parameters (toy parameters) are used in the attacking experiments. Only in this way can the attacker break the scheme by brute-force guessing with limited computational capability.
The first experiment can be divided into two branches. One branch is where the attacker has forged a certification of the fake underlying public key of period
j
, then the attacker uses the fake signing key to generate a “valid” undetachable digital signature. A screen capture of the output is shown in
Fig. 7
. It is easy to verify that the value of “sig” in the blue rectangle is just a BLS signature on the hash value of the message in the upper rectangle. Another branch is where the attacker directly generates an undetachable digital signature. The certification of period
j
,
CERT_{j}
, is “real and valid.” Thus, the attacker must generate a “valid”
K
that is used inv, otherwise the verification process would fail. Note that
K
is also a BLS signature on
REQ_C
||
ID_{C}
. A screen capture of the output is shown in
Fig. 8
.
Successful forgery of CERT_{j} .
Successful forgery of K .
According to the series of experiments, if an attacker is capable of breaking the proposed scheme, then the co-CDH problem could be solved. Hence, for sufficiently large security parameters, the proposed scheme is secure.

1) In the study, host and platform are used interchangeably to refer a place where mobile agents operate.
shiyang@tongji.edu.cn
Yang Shi received his BS degree in electronic engineering from Hefei University of Technology, China, in 1999 and his MS degree in pattern recognition and intelligence systems from Kunming University of Science and Technology, China, in 2002. He obtained his PhD degree in pattern recognition and intelligent systems from Tongji University, Shanghai, China, in 2005. From 2005 to 2011, he worked for Pudong CS&S Co. Ltd., Shanghai, China. Since 2012, he has been an associate professor with the School of Software Engineering, Tongji University, His research interests include information security, software privacy, and data engineering.
qinpeizhao@tongji.edu.cn
Qinpei Zhao received her BS degree in automation technology from Xi’dian University, China, in 2004. She received her MS degree in pattern recognition and image processing from Shanghai Jiaotong University, China, in 2007. She obtained her PhD degree in computer science from the School of Computing, University of Eastern Finland, Joensuu, Finland, in 2012. Since 2013, she has been a lecturer at the School of Software Engineering, Tongji University, Shanghai, China. Her current research interests include clustering algorithms and multimedia processing; location-based services; and security.
Corresponding Author sse508lab@126.com
Qin Liu received her BS degree in industrial automation from Dalian University of Technology and Science, China, in 1998; her MS degree in software engineering from Southampton Solent University, UK, in 2001; and her PhD degree in software engineering from Northumbria University, Newcastle, UK, in 2006. Since 2007, she has been with the School of Software Engineering, Tongji University, Shanghai, China. Currently, she is both a professor and the executive dean of the School of Software Engineering, Tongji University. Her research interests include software measurement; information security and privacy; data mining; and data analysis.

return 1 Else return 0

Similar to the second step, the third step involves the intermediate player
PPT Slide

Lager Image

q H 1 ( i )

,
q H 2 ( i )

,
q u ( i )

, and
q s ( i )

times, respectively, and has a running time of
〈 τ 1 , ε 1 , q H 1 (1) , q H 2 (1) , q s (1) , q u (1) 〉

-forger of
〈 τ 2 , ε 2 , q H 1 (2) , q H 2 (2) , q s (2) , q u (2) 〉

-forger of
G 1

or
G 2

, and let
Z q *

. We obtain the main result as follows, by calculating the number of operations in the game:
For any
InSec(FSUndSig, 1 k , ... ,T;τ, q s , q u ) ≤e( q s (1) + q s (2) + q u (1) + q u (2) +1)⋅ε︲.

■
- 7. Experimental Security Analysis

Besides the theoretical proof of security, experimental security analysis is provided to show that the security of the proposed scheme relies on the difficulty in solving the co-CDH problem. Actually, the analysis consists of two experiments. We firstly perform an experiment to show that if an attacker can break our scheme (that is, successfully forge an undetachable signature that can pass the verification of the undetachable signature verification algorithm
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

V. Comparison with Relative Works

The first implementation of an undetachable signature is the RSA-based version presented by Kotzanikolaou and others
[13]
. This was improved by Lee and others in
[17]
and by Shi and others in
[15]
. Han and others proposed a security scheme for e-Transactions using mobile agents with an agent broker
[14]
. They gave an undetachable signature function pair but did not present the signing function Sig subject to (1). Another undetachable signature scheme from pairings was proposed by Shi and others in
[16]
, which is also based on the short signature scheme proposed in
[22]
. However, this proposed scheme provides forward security, which is not provided by the scheme in
[16]
. The latest published undetachable signature scheme was presented in 2013. The scheme
[18]
uses a cryptosystem based on conic curves and is in the form of a threshold digital signature.
As shown in
Table 4
, different schemes are based on different problems; however, most significantly, only the proposed scheme is forward-secure.
Comparison of proposed scheme with other undetachable signature schemes.

Scheme | Computational infeasible problem | Forward-secure |
---|---|---|

Factorization of big integer | No | |

Factorization of big integer | No | |

No | ||

Discrete logarithm on elliptic curves | No | |

co-CDH | No | |

Factorization of big integer and discrete logarithm on conic curves | No | |

Ours | co-CDH | Yes |

VI. Conclusion

In this paper, we proposed the idea of a forward-secure undetachable digital signature (FS-UDS) so that mobile agents can perform forward-secure signing operations on behalf of the original signers securely, even while they are running in a malicious host. We gave the formal definition of an FS-UDS scheme. Then, we provided the security notion of forward-secure undetachable signature schemes as a theoretical basis. A concrete scheme with provable security was proposed for protecting mobile agents in electronic commerce. The proposed scheme is constructed on co-GDH group pairs, and its security relies on the infeasibility in solving computational co-Diffie–Hellman problems.
An implementation of the proposed undetachable signature algorithm can securely migrate with mobile agents from one host to another without the signing algorithm being at risk from misuse or the signing key being compromised. Moreover, even though a customer’s signing key (in a given time period) has been compromised, any adversary cannot forge any contracts that were signed before the compromising because this scheme is forward-secure.
BIO

Milojicic D.
1998
“MASIF: The OMG Mobile Agent System Interoperability Facility,”
Personal Technol.
2
(2)
117 -
129
** DOI : 10.1007/BF01324942**

von Solms S.H.
1998
“Electronic Commerce with Secure Intelligent Trade Agents,”
Comput. Security
17
(5)
435 -
446
** DOI : 10.1016/S0167-4048(98)00012-1**

Chung Y.-F.
2011
“An Agent-Based English Auction Protocol Using Elliptic Curve Cryptosystem for Mobile Commerce,”
Expert Syst. Appl.
38
(8)
9900 -
9907
** DOI : 10.1016/j.eswa.2011.02.039**

Trappey A.J.C.
,
Trappey C.V.
,
Lin F.T.L.
2006
“Automated Silicon Intellectual Property Trade Using Mobile Agent Technology,”
Robot. Comput.-Integr. Manuf.
22
(3)
189 -
202
** DOI : 10.1016/j.rcim.2005.03.003**

Wang G.
,
Wong T.N.
,
Wang X.H.
2014
“A Hybrid Multi-agent Negotiation Protocol Supporting Agent Mobility in Virtual Enterprises,”
Inf. Sci.
282
(20)
1 -
14
** DOI : 10.1016/j.ins.2014.06.021**

Du T.C.
,
Li E.Y.
,
Wei E.
2005
“Mobile Agents for a Brokering Service in the Electronic Marketplace,”
Decision Support Syst.
39
(3)
371 -
383
** DOI : 10.1016/j.dss.2004.01.003**

Aloui A.
,
Zerdoumi O.
,
Kazar O.
“Architecture for Mobile Business Based on Mobile Agent,”
Tangier, Morocco
Multimedia Comput. Syst.
May 10–12, 2012
954 -
958

Wong T.N.
,
Fang F.
2010
“A Multi-agent Protocol for Multilateral Negotiations in Supply Chain Management,”
Int. J. Production Res.
48
(1)
271 -
299
** DOI : 10.1080/00207540802425393**

Knight S.
,
Buffett S.
,
Hung P.C.K.
2007
“The International Journal of Information Security Special Issue on Privacy, Security and Trust Technologies and E-Business Services - Guest Editors’ Introduction,”
Int. J. Inf. Security
6
(5)
285 -
286
** DOI : 10.1007/s10207-007-0036-8**

Jung Y.
2012
“A Survey of Security Issue in Multi-agent Systems,”
Artif. Intell. Rev.
37
(3)
239 -
260
** DOI : 10.1007/s10462-011-9228-8**

Hohl F.
1998
“Time Limited Blackbox Security: Protecting Mobile Agents from Malicious Hosts,”
Springer
Mobile Agents Security
Berlin, Germany
92 -
113

Sander T.
,
Tschudin C.
1998
“Protecting Mobile Agents against Malicious Hosts,”
Springer
Mobile Agents Security
Berlin, Germany
44 -
60

Kotzanikolaou P.
,
Burmester M.
,
Chrissikopoulos V.
2000
“Secure Transactions with Mobile Agents in Hostile Environments,”
Springer
Information Security Privacy
Berlin, Germany
289 -
297

Han S.
,
Chang E.
,
Dillon T.
“Secure E-Transactions Using Mobile Agents with Agent Broker,”
Int. Conf. Services Syst. Services Manag.
Chongqing, China
June 13–15, 2005
849 -
855

Shi Y.
,
Cao L.
,
Wang X.
“A Security Scheme of Electronic Commerce for Mobile Agents Uses Undetachable Digital Signatures,”
Int. Conf. Inf. Security
Shanghai, China
Nov. 14–15, 2004
242 -
243

Shi Y.
“Secure Mobile Agents in Electronic Commerce by Using Undetachable Signatures from Pairings,”
Int. Conf. Electron. Business
Beijing, China
Dec. 5–9, 2004
1038 -
1043

Lee B.
,
Kim H.
,
Kim K.
2001
“Secure Mobile Agent Using Strong Non-designated Proxy Signature,”
Springer
Information Security Privacy
Berlin, Germany
474 -
486

Shi Y.
,
Xiong G.Y.
2013
“An Undetachable Threshold Digital Signature Scheme Based on Conic Curves,”
Appl. Math. Inf. Sci.
7
(2)
823 -
828
** DOI : 10.12785/amis/070254**

Yu J.
2011
“Forward-Secure Identity-Based Signature: Security Notions and Construction,”
Inf. Sci.
181
(3)
648 -
660
** DOI : 10.1016/j.ins.2010.09.034**

Yu Y.-C.
,
Huang T.-Y.
,
Hou T.-W.
2012
“Forward Secure Digital Signature for Electronic Medical Records,”
J. Med. Syst.
36
(2)
399 -
406
** DOI : 10.1007/s10916-010-9484-1**

Fan C.-I.
,
Lin Y.-H.
,
Hsu R.-H.
2013
“Complete EAP Method: User Efficient and Forward Secure Authentication Protocol for IEEE 802.11 Wireless LANs,”
IEEE Trans. Parallel Distrib. Syst.
24
(4)
672 -
680
** DOI : 10.1109/TPDS.2012.164**

Boneh D.
,
Lynn B.
,
Shacham H.
2004
“Short Signatures from the Weil Pairing,”
J. Cryptology
17
(4)
297 -
319

Krawczyk H.
“Simple Forward-Secure Signatures from Any Signature Scheme,”
ACM Conf. Comput. Commun. Security
Athens, Greece
Nov. 1–4, 2000
108 -
115

De Caro A.
,
Iovino V.
“JPBC: Java Pairing Based Cryptography,”
IEEE Symp. Comput. Commun.
Kerkyra, Greece
June 28–July 1, 2011
850 -
855

Citing 'Secure Mobile Agents in eCommerce with Forward-Secure Undetachable Digital Signatures
'

@article{ HJTODO_2015_v37n3_573}
,title={Secure Mobile Agents in eCommerce with Forward-Secure Undetachable Digital Signatures}
,volume={3}
, url={http://dx.doi.org/10.4218/etrij.15.0114.0657}, DOI={10.4218/etrij.15.0114.0657}
, number= {3}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Zhao, Qinpei
and
Liu, Qin}
, year={2015}
, month={May}