Advanced
Secure Mobile Agents in eCommerce with Forward-Secure Undetachable Digital Signatures
Secure Mobile Agents in eCommerce with Forward-Secure Undetachable Digital Signatures
ETRI Journal. 2015. Jun, 37(3): 573-583
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : June 03, 2014
  • Accepted : March 19, 2015
  • Published : June 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Qinpei Zhao
Qin Liu

Abstract
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.
Keywords
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 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] .
PPT Slide
Lager Image
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.
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
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.
f Signed =Sigf.
To create an undetachable signature on a shop’s server, (2) is computed by calling f Signed from the customer’s mobile agent.
z= f 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:
  • ■ 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).
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.
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
1k Security parameter, k ∈ ℕ
U0 Base public key
s0 Base secret key (signing key)
j Index of the time period
sj / sj−1 Secret signing key of the time period j / j − 1
CERTj Certification (of underlying public key) of the period j
REQ_C||IDC Customer C’s requirement and identity
fSignedi Implementation of undetachable signing function of time period j
f Auxiliary function of fSignedi
Msg Message (usually a contract)
Z Undetachable signature
σ, σj Normal signatures
Definition 1. An FS-UDS FSUSig = ( KGen , KUpd , Sign , Vrfy , UndSigFunGen , UndSig , UndVrfy ) consists of the following seven algorithms:
  • ■ 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 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.
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,
L b Sign
and
L b UndSigFunGen
are the query lists coming from the signing query Signsb (•) of period b and the undetachable signature function generation query UndSigFunGenSKb (•) of period b , respectively.
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,
T b Sign
and
T b UndSigFunGen
are the query lists coming from the signing query SignSKb (•) of period b and the undetachable signature function generation query UndSigFunGenSKb (•) of period b , respectively.
Remark 1. RES is a restriction. It is usually in the form of REQ || IDC , where REQ is the requirement of a customer ( C ) and IDC is the customer’s identity.
Definition 2. The insecurity function of FSUndSig is defined as
InSec(FSUndSig, 1 k ,  ...  ,T;τ, q s , q u )= Max F= F 1 , F 2 { Pr[ ( 1=FU-ForgeSig( FSUndSig, F 1 , 1 k ,  ...  ,T ) ) ( 1=FU-ForgeUndSig( FSUndSig, F 2 , 1 k ,  ...  ,T ) ) ] }.
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 qs queries to the signing oracles and at most qu 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.
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.
Remark 3. We suppose that there exists an isomorphism
ψ: G 2 → G 1
with ψ ( P ) = G .
- 2. Mathematical Problems and Computational Assumptions
Definition 3. Decision co-Diffie–Hellman (co-DDH) problem on
( G 1 , G 2 )
: Given P , Pa G 2 and Y , Yb 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 , Pa , Y , Yb ) is a co-Diffie–Hellman tuple (co-DHT).
Assumption 1. We suppose that
e ^
can be effectively computed, so the co-DDH problem on
( G 1 , G 2 )
is easy to solve.
Definition 4. Computational co-Diffie–Hellman (co-CDH) problem on
( G 1 , G 2 )
: Given g 2 , g 2 a
G 2
and h
G 1
as input, the solution of the problem is (to compute) ha
G 1
.
Definition 5. We say that an algorithm ( t ', ε ') -breaks co-CDH on
( G 1 , G 2 )
if the algorithm runs in time (that is, within t ') and successfully solves the co-CDH problem on
( G 1 , G 2 )
with a probability of at least ε '.
Definition 6. Two groups,
( G 1 , G 2 )
, are a ( λ , t ', ε ') gap Diffie–Hellman group pair (co-GDH) if they satisfy the following properties:
  • ■ 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).
Assumption 2. The two order- q groups
( G 1 , G 2 )
in the public setting are a ( λ , t ', ε ') -bilinear group pair; that is, they satisfy the following properties:
  • ■ 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).
Because we can efficiently solve the co-DDH problem by computing two bilinear maps, if two groups
( G 1 , G 2 )
are a ( λ , 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.
- 3. Algorithms
The proposed FS-UDS consists of seven algorithms; that is, KGen , KUpd , UndSigFunGen , UndSig , UndVrfy , Sig , and Vrfy , as follows:
Algorithm KGen (1k) s 0 $ Z q * ; U 0 P s 0 For( j=1;jT;j++ ) do ( s j ) $ H 1 ( s j1 ) ; U j P s j CER T j U 0 ,j, U j , H 2 ( U 0 ,j, U j ) s 0 EndFor erase s j ,  j=1,  ...  ,T ; store CER T j ,  j=1,  ...  ,T return U 0 , s 0
Algorithm KUpd (sj−1, CERTj, j, U0) U 0 , j , U j , Λ j CER T j ;  s j H 1 ( s j1 );  U j P s j If( e ̂ ( Λ j ,P ) e ̂ ( H 2 ( U 0 ,j, U j ), U 0 ) ) return erase s j1 return s j
Algorithm UndSigFunGen (REQ_C || IDC, skj, CERTj) H H 2 (REQ_C||I D C ) ; K H s j σ CER T j ,σ ; σ j σ,j setup f(x)= H x f Signed j (x)= CER T j , K x ,j return f(), f Signed j ()
Algorithm UndSig (Msg) h = H1(Msg); return fSignedj(h)
Algorithm UndVrfy (U0, Z, j, Msg, REQ_C || IDC) CER T j , Z ,j Z;  U 0 , j , U j , Λ j CER T j If( ( U 0 U 0 )( j j ) )   return   0 If( Msg does not satisfy REQ_C )   return   0 If( e ̂ ( Λ j ,P ) e ̂ ( H 2 ( U 0 , j , U j ), U 0 ) )   return   0 If( e ̂ ( Z ,P ) e ̂ ( H 2 ( REQ_C||I D C ) H 1 ( Msg ) , U j ) )  return   0 else   return   1
Algorithm Sign (sj, j, Msg) σ H 2 ( Msg ) s j ; σ CER T j ,σ ; σ j σ,j return σ j
Algorithm Vrfy (U0, σ, j, Msg) CER T j , σ σ;  U 0 , j , U j , Λ j CER T j If( ( U 0 U 0 )( j j ) )   return   0 If( e ̂ ( Λ j ,P ) e ̂ ( H 2 ( U 0 , j , U j ), U 0 ) )   return   0 If( e ̂ ( σ ,P ) e ̂ ( H 2 ( Msg ), U j ) )  return   0 Else   return   1
- 4. Proof of Correctness
The following proposition shows that the proposed scheme is a “correct” FS-UDS scheme.
Proposition 1. Let Sigsj, j ( x ) = 〈〈 CERTj , xsj 〉, 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
(Si g s j ,j f)(x)=Si g s j ,j ( H x )= CER T j , ( H x ) s j ,j = CER T j , ( H s j ) x ,j = CER T j , K x ,j = f Signe d j (x).
It is not difficult to validate the correctness of UndVrfy and Vrfy , so we omit the proofs.
- 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
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] .
Results of performance tests.
Algorithm Time (ms) Size (byte)
PC Server Input Output
Ours KGen (T=10) 663 610 2 148
KUpd 66 65 534 20
Sign 46 44 149 514
Vrfy 101 101 771 1
UndSigFunGen 46 43 535 642
UndSig 15 13 128 514
UndVrfy 115 114 901 1
[16] KGen 17 15 2 148
Sign 52 50 148 128
Vrfy 57 56 384 1
UndSigFunGen 56 51 150 256
UndSig 16 15 128 128
UndVrfy 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.
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).
InSec(FSUndSig, 1 k ,  ...  ,T;τ, q s , q u )              e( q s (1) + q s (2) + q u (1) + q u (2) +1)ε.
Proof. The first step of this proof is to adapt the forgery experiments to the proposed concrete construction as follows:
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
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 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:
Algorithm C2.NB(〈ζ, b〉, RES, M) CER T j , ζ ,j ζ;h O H 1 ( M ); σ CER T j , h 1 ζ ,j return   ( σ,b ,RES )
Algorithm Ci.ZB(RES, skj, CERTj) i = 1, 2 H O FSSig. H 2 (RES) ; Δ O FSSig.Sig (RES); CER T j ,K,j Δ setup f(x)= H x f Signed (x)= CER T j , K x ,j return f(), f Signed ()
PPT Slide
Lager Image
C1 plays between F1 and A.
PPT Slide
Lager Image
C2 plays between F2 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 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 
return 1 Else return 0
Similar to the second step, the third step involves the intermediate player A playing the game F-ForgeSign with Ci ( 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:
Algorithm A.Init(T, 1k) t $ { 1,  ...  ,T } ; b $ { 1,  ...  ,t } HashList ; SKeyList ; PKeyList For( i=0,  it;  i++ ) do SKeyList[i] $ Z q * ; PKeyList[i] P SKeyList[i] EndFor U b U* For( i=t+1,  iT;i++ ) do SKeyList[i]B.ZB_H( s i1 ) ; PKeyList[i] P SKeyList[i] EndFor store all SKeyList,PKeyList
Algorithm A.ZB_S(j, Msg) If(b=j) return O Sign.Sig (Msg) Else retur n     H 2 (Msg) SKeyList[j]
Algorithm A.ZB_H(x) If( y, x,y HashList ) retur n  y y $ Z q * ; HashListHashList{ x,y } ; return y
PPT Slide
Lager Image
A plays between Ci 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 Fi ( i = 1 or 2) can win the game that queries O FSUndSig.H1(•) , O FSUndSig.H2 (·), OIDSig (·,·), O H3 (·), and O H2 (·) at most
q H 1 ( i )
,
q H 2 ( i )
,
q u ( i )
, and
q s ( i )
times, respectively, and has a running time of τi and an advantage εi . That is, F 1 is a
〈 τ 1 , ε 1 , q H 1 (1) , q H 2 (1) , q s (1) , q u (1) 〉
-forger of FSUndSig.Sig or F 2 is a
〈 τ 2 , ε 2 , q H 1 (2) , q H 2 (2) , q s (2) , q u (2) 〉
-forger of FSUndSig.UndSig .
Let c exp be the time of computing an exponentiation in
G 1
or
G 2
, and let crng be the time of generating a random element of
Z q *
. We obtain the main result as follows, by calculating the number of operations in the game:
For any τ , if
τ( t c exp ( 2( q H 2 (1) + q H 2 (2) + q u (1) + q u (2) ) +  3( q s (1) + q s (2) + q u (1) + q u (2) )+2T ) ( 2T+ q H 1 (1) + q H 1 (2) ) c rng ),
then
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 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 .
PPT Slide
Lager Image
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 , CERTj , 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 || IDC . A screen capture of the output is shown in Fig. 8 .
PPT Slide
Lager Image
Successful forgery of CERTj.
PPT Slide
Lager Image
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.
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
[13] Factorization of big integer No
[17] Factorization of big integer No
[14] q-Strong Diffie-Hellman problem No
[15] Discrete logarithm on elliptic curves No
[16] co-CDH No
[18] 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.
In the study, host and platform are used interchangeably to refer a place where mobile agents operate.
BIO
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.
References
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