# Secure Mobile Agent from Leakage-Resilient Proxy Signatures

Authors: Fei Tang; Hongda Li; Qihua Niu; Bei Liang
Journal: Mobile Information Systems
 (2015)

---

## Abstract

A mobile agent can sign a message in a remote server on behalf of a customer without exposing its secret key; it can be used not only to search for special products or services, but also to make a contract with a remote server. Hence a mobile agent system can be used for electronic commerce as an important key technology. In order to realize such a system, Lee et al. showed that a secure mobile agent can be constructed using proxy signatures. Intuitively, a proxy signature permits an entity (delegator) to delegate its signing right to another entity (proxy) to sign some specified messages on behalf of the delegator. However, the proxy signatures are often used in scenarios where the signing is done in an insecure environment, for example, the remote server of a mobile agent system. In such setting, an adversary could launch side-channel attacks to exploit some leakage information about the proxy key or even other secret states. The proxy signatures which are secure in the traditional security models obviously cannot provide such security. Based on this consideration, in this paper, we design a leakage-resilient proxy signature scheme for the secure mobile agent systems.


---

## Body

## 1. Introduction

Mobile agents [1–3] are designed as some autonomous software entities which are able to sign some messages in a remote server on behalf of a customer without exposing its secret key. Therefore, a mobile agent system can be used for electronic commerce in many ways such as negotiating something with other entities, searching and buying special products or services on behalf of a customer, and selling products on behalf of a shopping server. As shown by previous works, a mobile agent system can be constructed using some proxy signature schemes; for example, Lee et al. [4] used a strong nondesignated proxy signature scheme; they also provided an RSA-based and Schnorr-based constructions of secure mobile agent.Proxy Signatures. This notion was first introduced by Mambo et al. [5] in 1996. In a proxy signature scheme, an entity called delegator may delegate its signing right to another entity called proxy who can then sign some specified messages on behalf of the delegator; we call such signatures as proxy signatures. Finally, the verifier can be convinced from the proxy signatures that the original signer’s agreement on the signed message and such proxy signatures must be computed by the proxy rather than the delegator. Obviously, proxy signatures are very useful in many application scenarios, for example, mobile agents [3, 6–9] and mobile communications [10, 11]. In the existing proxy signature schemes, the model of delegation by warrant [5] (a signed warrant, e.g., W
∶
=
I
D
proxy
∥
M
∥
indate
∥
⋯, used to describe the validity of the delegation) has received the most attention. Kim et al. [12] suggested that a proxy key should be generated from such warrant. After Mambo et al.’s seminal work, many variants or improved schemes have been proposed (e.g., see [4, 11, 13–17]).BPW Transformation. Boldyreva et al. [13] (henceforth called BPW) have given a secure generic construction of proxy schemes in the model of delegation by warrant from any secure ordinary signature scheme. Informally, to generate a proxy key, the original signer first signs a concatenation of the proxy’s public key and a warrant with a specific way to obtain a delegation certificate. Then the proxy could set up the proxy key by himself using this delegation certificate. Finally, the proxy could sign some messages that are described in the warrant on behalf of the original signer (cf. Section 4 of [13] for detailed description).Multilevel Proxy Model. Malkin et al. [14] extended the general proxy signatures to the scenario of multilevel proxy, where the proxy can also delegate the proxy signing right to another proxy (in such setting the former proxy also is a delegator); similarly, the second proxy also can delegate its proxy signing right to another, and so on. We call the identities that the original signer and all proxies construct a delegation chain, that is, (original  signer)-(1th proxy)-(2th proxy)-⋯-(jth proxy)-⋯.Security Models for Proxy Signatures. Due to the additional property of the proxy signatures, how to define the security for the proxy signatures is more complicated than the standard signatures [18]. In [19], Mambo et al. introduced several security notions (then enhanced by Lee et al. [4]) for the proxy signatures (here we omit them; please refer to [4, 19] for detailed description). These notions provide some intuitive security requirements for the proxy signatures, but corresponding security definitions are unclear (i.e., lacking of formal definitions), so many constructions were shown to be insecure and then fixed and finally to be shown insecure again (e.g., [4, 19, 20]). Subsequently, Boldyreva et al. [13] first presented a well-defined security model for the proxy signatures. In their model, the adversary is allowed to corrupt an arbitrary number of users and learn their secret keys. Moreover, the adversary can also register some public keys on behalf of new users. Then, the adversary interacts with honest users playing the role of a delegator or a proxy and it can see the transcripts of all executions of the delegation protocol between the honest users. It is a rather strong security model. Malkin et al. [14] later extended this model to allow multilevel proxy signatures; they also showed that proxy signatures are equivalent to key-insulated signatures [21]. The models of [13, 14] both are registered key models, which means that it is required that the adversary submits the secret and public keys of all users used in the model except a single challenging user. Schuldt et al. [15] got rid of this requirement and gave a new security model, existential unforgeability under adaptive chosen message attack with proxy key exposure (EU-CMA-PKE). In this model, adversary directly controls all user’s secret keys of the delegation chain except the challenging user; furthermore, the adversary can corrupt some user to obtain the proxy keys (see Section 4 of [15] for more detailed description).Black-Box Assumption versus Reality. In the security model of cryptographic schemes, traditionally, it is assumed that the secret internal state (secret key, randomness, etc.) of the schemes is completely hidden to the adversary, and hence the adversary in the traditional black-box model only can access an oracle to learn the input and output behaviors about the scheme. Unfortunately, many cryptographic engineers have shown that this assumption is not true in real world applications. They have designed a large class of realistic attacks, called side-channel attacks, to detect some leakage information about the secret state, for example, timing attacks [22], power consumption [23], and fault attacks [24, 25]. Therefore, if we implement a mobile agent system from a secure proxy signature that is in the traditional security model, it may be also insecure if the device of mobile agent encounters the side-channel attacks.Leakage-Resilient Cryptography. To resist such side-channel attacks, cryptographers have proposed many countermeasures in the past few years. Leakage-resilient cryptography is one of them, which means that a cryptosystem is also secure; even the adversary obtains some bounded (even arbitrary) leakage information about the secret internal state.To model the security of cryptographic schemes in the leakage-resilient cryptography setting with a formal way,considering an adversary attacks a scheme besides the ordinary queries (as in the black-box model), it also can adaptively choose arbitrary polynomial time computable functions (named leakage functions)f
i
:
{
0,1
}
*
→
{
0,1
}
λ to obtain some information about the secret internal state. The restrictions of the input and output for such leakage functions depend on the leakage models. Here, we briefly present some of them.(i)
Only computation leaks model, introduced by Micali and Reyzin [26]: in this model, leakage is assumed to only occur on values that are currently accessed during the computation. Therefore, the input of the leakage function f
i is confined to theactive part of the internal secret state, while the passive part of the secret state is not taken as input to the leakage function.
(ii)
Bounded leakage model: the overall amount of the leakage should be bounded on a prespecified valueλ.
(iii)
Continual-leakage model, introduced by Brakerski et al. [27] and Dodis et al. [28], independently: in this model, the secret key is allowed to be refreshed, while the corresponding public key remains fixed. Then the amount of the leakage is bounded only in between any two successive key refreshes and the overall amount can be unbounded.Many cryptographic schemes have been proposed in the leakage-resilient cryptography setting based on different leakage models, for example, leakage-resilient stream ciphers [29], leakage-resilient zero knowledge [30], leakage-resilient PKE [31, 32], leakage-resilient IBE [33, 34], and leakage-resilient signatures [35–40].Leakage-Resilient Signatures. In this paper, we focus on the construction of leakage-resilient signature schemes. Alwen et al. [35] gave a construction of leakage-resilient signature scheme in the random oracle model which may tolerate leakage of up to half the secret key. Then Katz and Vaikuntanathan [38] constructed a bounded leakage-resilient signature scheme in the standard model which can tolerate leakage of up to l
-
l
ϵ (l denotes the bit-length of the secret key) bits of information about the secret key. In the same paper, they also introduced the notion of fully leakage-resilient signatures which means that it is EU-CMA secure even the adversary may obtain leakage information on all internal state values that are used throughout the lifetime of the scheme. Boyle et al. [36] then improved their scheme to a full one which can be resilient to any leakage of length (
1
-
o
(
1
)
)
l bits. Faust et al. [37] constructed a tree-based leakage-resilient signature scheme (in the model of “only computation leaks”) which can be instantiated with any 3-time bounded leakage-resilient signature. Their scheme resilient to λ
=
λ
′
/
3 bits per signing process, where λ
′ is size of the underlying 3-time signature scheme, can leak in total.Our Contribution. Proxy signatures are often proposed for use in applications where signing is done in a potentially hostile environment; for example, if we use a proxy signature to realize a mobile agent system, then the proxy key is stored in a laptop, or even an IC card, which might become infected by malware. In such setting, an adversary who launches side-channel attacks can detect some leakage information about the proxy key or even other internal states. Based on this consideration, we construct a proxy signature scheme in the setting of leakage-resilient cryptography, the leakage-resilient proxy signature (LRPS), for the first time. The proposed LRPS scheme maintains the properties of these two primitives, leakage-resilient cryptography and proxy signatures.To define the security notion to the LRPS scheme, we combine the existing security models of proxy signatures and leakage-resilient cryptography to put forward the security model of existential unforgeability against the adaptive chosen message and leakage attacks (EU-CMLA (We also introduce the notion of EU-CMLA-PKE which is extended from EU-CMA-PKE in [15] for the full construction of the LRPS in Appendices.)). Furthermore, we also construct a concrete LRPS scheme under the delegation by warrant and multilevel proxy models, it can be regarded as a concrete implementation of the BPW transformation in the setting of leakage-resilient cryptography. We use a tree-based signature scheme to construct the proxy signature scheme, which is different than the method that [13, 15] adopted; they both adopted an aggregate signature [41]. Hence our construction provides an alternative method to the construction of the proxy signatures. The concrete construction of the LRPS scheme is based on Faust et al.’s [37] (henceforth called FKPR, in TCC 2010) leakage-resilient signature scheme.


## 2. Definitions

In this section, we present some basic definitions for this paper: the notion of the stateful signatures and its security in the black-box model and in the presence of leakage, respectively.


### 2.1. Notations

1
k denotes the string of k ones for k
∈
N. x denotes the length of the bit string x if x is a bit string; S denotes the number of the entries in the set S. s
←
$
S means randomly choosing an element s from the set S. We write y
←
A
(
x
) to indicate that running the algorithm A with input x and then outputs y and y
←
$
A
(
x
) has the same indication except that A is a probabilistic algorithm. We use the notation s
1
∥
s
2 to denote the concatenation of the bit strings s
1 and s
2; if they are not strings, we assume that they will be encoded as a string before the concatenation takes place. Lastly we write PPT for the probabilistic polynomial time.


### 2.2. Stateful Signatures

A signature schemeS
I
G consists of three algorithms, key generation, signing, and verification denoted by K
g, S
i
g
n, and V
f
y, respectively. We say that a signature scheme is stateful if theSign algorithm is stateful, which means that the secret key will be refreshed after (or before) each signing process, while its corresponding public key remains fixed. That is to say, S
I
G = (K
g, S
i
g
n, V
f
y) is a stateful signature scheme if it satisfies the following.(i)
K
g is a PPT algorithm that takes as input a security parameter k and then outputs the signer’s initial secret key SK
0 and public key PK. We write it (
SK
0
,
PK
)
←
$
K
g
(
1
k
).
(ii)
S
i
g
n is a PPT algorithm run by the signer who takes as input its stateful secret key SK
i
-
1 and a message m
i and then outputs a signature Σ
i and the next stateful secret key SK
i. We write it (
Σ
i
,
SK
i
)
←
$
S
i
g
n
(
SK
i
-
1
,
m
i
).
(iii)
V
f
y is a deterministic algorithm run by the verifier who takes as input the signer’s public key PK, the signed message m
i, and the corresponding signature Σ
i and then outputs 1 if it is valid; else it outputs 0. We write it 1
/
0
←
V
f
y
(
PK
,
m
i
,
Σ
i
).


### 2.3. Security of Stateful Signatures in the Black-Box Model

The definition of existential unforgeability against adaptive chosen message attack (EU-CMA) for the stateful signatures is defined by the following experimentE
x
p
S
I
G
,
A
eu-cma which is played by a EU-CMA adversary A and a challenger B.(i)
B runs (
SK
0
*
,
PK
*
)
←
$
K
g
(
1
k
) and gives P
K
* to A.
(ii)
A can adaptively ask B for the following:
signing queryS
Q: m
i
B runs (
Σ
i
,
SK
i
*
)
←
$
S
i
g
n
(
SK
i
-
1
*
,
m
i
) and returns Σ
i to A.
(iii)
At some point,A outputs (
m
*
,
Σ
*
).We say that A wins the above experiment E
x
p
S
I
G
,
A
eu-cma if 1
←
V
f
y
(
PK
*
,
m
*
,
Σ
*
) and m
* was not submitted to the signing query. We denote the probability of A succeeded by A
d
v
S
I
G
,
A
eu-cma. We saySIG is EU-CMA secure if A
d
v
S
I
G
,
A
eu-cma is negligible for every PPT adversary A.


### 2.4. Security of Stateful Signatures in the Presence of Leakage

In the setting of the leakage-resilient cryptography, adversaryA can obtain λ bits of leakage information with every signing query. With the ith signing query, the adversary A adaptively chooses any computable leakage function f
i
:
{
0,1
}
*
→
{
0,1
}
λ to the leakage query and then obtains the output Λ
i of f
i which takes as input the active part SK
i
-
1
*
+ of the stateful secret key and the randomness r
i used in the signing phase. Formally, the model of existential unforgeability against adaptive chosen message and leakage attacks (EU-CMLA) is defined by the following experiment E
x
p
S
I
G
,
A
eu-cmla which is played by a EU-CMLA adversary A and a challenger B.(i)
B runs (
SK
0
*
,
PK
*
)
←
$
K
g
(
1
k
) and gives PK
* to A.
(ii)
A can adaptively ask B for the following:
(a)
signing queryS
Q: m
i
B runs (
Σ
i
,
SK
i
*
)
←
$
S
i
g
n
(
SK
i
-
1
*
,
m
i
,
r
i
) and returns Σ
i to A;
(b)
leakage queryL
Q: f
i
B runs Λ
i
←
f
i
(
SK
i
-
1
*
+
,
r
i
) and if Λ
i
≠
λ then it returns ⊥; else it returns Λ
i to A.
(iii)
At some point,A outputs (
m
*
,
Σ
*
).We say that A wins the above experiment E
x
p
S
I
G
,
A
eu-cmla if 1
←
V
f
y
(
PK
,
m
*
,
Σ
*
) and m
* was not submitted to the signing query. We denote the probability of A succeeded by A
d
v
S
I
G
,
A
eu-cmla. We saySIG is EU-CMA secure if A
d
v
S
I
G
,
A
eu-cmla is negligible for every PPT adversary A.


## 2.1. Notations

1
k denotes the string of k ones for k
∈
N. x denotes the length of the bit string x if x is a bit string; S denotes the number of the entries in the set S. s
←
$
S means randomly choosing an element s from the set S. We write y
←
A
(
x
) to indicate that running the algorithm A with input x and then outputs y and y
←
$
A
(
x
) has the same indication except that A is a probabilistic algorithm. We use the notation s
1
∥
s
2 to denote the concatenation of the bit strings s
1 and s
2; if they are not strings, we assume that they will be encoded as a string before the concatenation takes place. Lastly we write PPT for the probabilistic polynomial time.


## 2.2. Stateful Signatures

A signature schemeS
I
G consists of three algorithms, key generation, signing, and verification denoted by K
g, S
i
g
n, and V
f
y, respectively. We say that a signature scheme is stateful if theSign algorithm is stateful, which means that the secret key will be refreshed after (or before) each signing process, while its corresponding public key remains fixed. That is to say, S
I
G = (K
g, S
i
g
n, V
f
y) is a stateful signature scheme if it satisfies the following.(i)
K
g is a PPT algorithm that takes as input a security parameter k and then outputs the signer’s initial secret key SK
0 and public key PK. We write it (
SK
0
,
PK
)
←
$
K
g
(
1
k
).
(ii)
S
i
g
n is a PPT algorithm run by the signer who takes as input its stateful secret key SK
i
-
1 and a message m
i and then outputs a signature Σ
i and the next stateful secret key SK
i. We write it (
Σ
i
,
SK
i
)
←
$
S
i
g
n
(
SK
i
-
1
,
m
i
).
(iii)
V
f
y is a deterministic algorithm run by the verifier who takes as input the signer’s public key PK, the signed message m
i, and the corresponding signature Σ
i and then outputs 1 if it is valid; else it outputs 0. We write it 1
/
0
←
V
f
y
(
PK
,
m
i
,
Σ
i
).


## 2.3. Security of Stateful Signatures in the Black-Box Model

The definition of existential unforgeability against adaptive chosen message attack (EU-CMA) for the stateful signatures is defined by the following experimentE
x
p
S
I
G
,
A
eu-cma which is played by a EU-CMA adversary A and a challenger B.(i)
B runs (
SK
0
*
,
PK
*
)
←
$
K
g
(
1
k
) and gives P
K
* to A.
(ii)
A can adaptively ask B for the following:
signing queryS
Q: m
i
B runs (
Σ
i
,
SK
i
*
)
←
$
S
i
g
n
(
SK
i
-
1
*
,
m
i
) and returns Σ
i to A.
(iii)
At some point,A outputs (
m
*
,
Σ
*
).We say that A wins the above experiment E
x
p
S
I
G
,
A
eu-cma if 1
←
V
f
y
(
PK
*
,
m
*
,
Σ
*
) and m
* was not submitted to the signing query. We denote the probability of A succeeded by A
d
v
S
I
G
,
A
eu-cma. We saySIG is EU-CMA secure if A
d
v
S
I
G
,
A
eu-cma is negligible for every PPT adversary A.


## 2.4. Security of Stateful Signatures in the Presence of Leakage

In the setting of the leakage-resilient cryptography, adversaryA can obtain λ bits of leakage information with every signing query. With the ith signing query, the adversary A adaptively chooses any computable leakage function f
i
:
{
0,1
}
*
→
{
0,1
}
λ to the leakage query and then obtains the output Λ
i of f
i which takes as input the active part SK
i
-
1
*
+ of the stateful secret key and the randomness r
i used in the signing phase. Formally, the model of existential unforgeability against adaptive chosen message and leakage attacks (EU-CMLA) is defined by the following experiment E
x
p
S
I
G
,
A
eu-cmla which is played by a EU-CMLA adversary A and a challenger B.(i)
B runs (
SK
0
*
,
PK
*
)
←
$
K
g
(
1
k
) and gives PK
* to A.
(ii)
A can adaptively ask B for the following:
(a)
signing queryS
Q: m
i
B runs (
Σ
i
,
SK
i
*
)
←
$
S
i
g
n
(
SK
i
-
1
*
,
m
i
,
r
i
) and returns Σ
i to A;
(b)
leakage queryL
Q: f
i
B runs Λ
i
←
f
i
(
SK
i
-
1
*
+
,
r
i
) and if Λ
i
≠
λ then it returns ⊥; else it returns Λ
i to A.
(iii)
At some point,A outputs (
m
*
,
Σ
*
).We say that A wins the above experiment E
x
p
S
I
G
,
A
eu-cmla if 1
←
V
f
y
(
PK
,
m
*
,
Σ
*
) and m
* was not submitted to the signing query. We denote the probability of A succeeded by A
d
v
S
I
G
,
A
eu-cmla. We saySIG is EU-CMA secure if A
d
v
S
I
G
,
A
eu-cmla is negligible for every PPT adversary A.


## 3. Leakage-Resilient Proxy Signatures

As outlined in the Introduction, there exists three entities in a proxy signature scheme: an original signer, a (or multi) proxy signer, and a verifier. A delegator, whether it is the original signer or a proxy signer, wants to delegate its signing right, whether original signing is right (i.e., the delegator is the original signer) or proxy signing is right (i.e., the delegator is a proxy signer) to a proxy. Finally, the verifier can be convinced with the original signer’s agreement on the signed message and the identities of the proxy signers from the proxy signatures.In the multilevel proxy model, a delegation chain, (original  signer)-(1th proxy)-(2th proxy)-⋯-(jth proxy)-⋯, consists of an original signer and j (or more) proxy signers. To identify them, we require a list P
K of their public keys in the proxy signatures.In the BPW transformation, the delegator will sign its proxy’s public key and corresponding warrant to obtain a certificate to generate the proxy key. Therefore, to verify the validity of the delegation, it is also required that the proxy signatures contain a listW of the warrants and C of the certificates of the delegations.


### 3.1. Syntax

Formally, we define the stateful proxy signatures (under the BPW transformation) as follows. That is to say,S
I
G
*
=
(
K
g
*
,
S
i
g
n
*
,
V
f
y
*
,
D
e
l
*
,
P
K
g
*
,
P
S
i
g
n
*
,
P
V
f
y
*
) is a stateful proxy signature scheme if the first three algorithms are defined as K
g, S
i
g
n, and V
f
y of the scheme S
I
G, respectively, and the latter three algorithms satisfy the following.(i)
D
e
l
*
,
P
K
g
* is a pair of interactive PPT delegation protocol which means that the delegator D  whose stateful key is (
S
K
D
(
i
-
1
)
,
P
K
D
) delegates its signing right to a proxy P who has a stateful key pair (
S
K
P
(
i
′
-
1
)
,
P
K
P
).
(a)
D
e
l
* is run by the delegator with input (
S
K
D
(
i
-
1
), P
K
P, P
K, W, C, j, W
j
), where P
K, W, and C are the lists of public keys, warrants, and delegation certificates of the previous delegators, respectively, j describes the current proxy is the jth proxy in the delegation chain (j
=
0 means that the delegator is the original signer), and W
j is the warrant for the current delegation.
(b)
P
K
g
* is run by the proxy with input (
S
K
P
(
i
′
-
1
), P
K
P, P
K
D
) to generate its proxy key.As a result of this interactive algorithm, the algorithm D
e
l
* has no local output except that the delegator’s next stateful key S
K
D
i. The local output of P
K
g
* is the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
S
K
P
(
i
′
-
1
)
), where P
K
′, W
′, and C
′ are the lists of public keys, warrants, and certificates in the delegation chain extended with the public key of the proxy and warrant and certificate of the current delegation, respectively. We write it (S
K
D
i, P
K
′, W
′, C
′, j
,
S
K
P
(
i
′
-
1
)
)
←
$
D
e
l
*
(
S
K
D
(
i
-
1
)
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
), P
K
g
*
(
S
K
P
(
i
′
-
1
)
,
P
K
P
,
P
K
D
). (ii)
P
S
i
g
n
* is a PPT algorithm run by a proxy that takes as input its delegation information (
P
K, W, C, j, S
K
P
(
i
′
-
1
)
) and a message m
i and then outputs a proxy signature (
P
K
,
W
,
C
,
j
,
P
Σ
i
) on behalf of the delegator and its next stateful key S
K
P
i
′. We write it (
P
K, W, C, j, P
Σ
i, S
K
P
i
′
)
←
$
P
S
i
g
n
*
(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
′
-
1
)
,
m
i
).
(iii)
P
V
f
y
* is a deterministic algorithm run by the verifier who takes as input (
P
K
,
W
,
C
,
j
,
m
i
,
P
Σ
i
) and then outputs 1 if it is valid; else it outputs 0. We write it 1
/
0
←
P
V
f
y
*
(
P
K
,
W
,
C
,
j
,
m
i
,
P
Σ
i
).In the real world applications, user’s long-term secret key should be stored in a secure way and thus to guarantee that no information about the long-term key is leaked while the proxy key is exposed, it is better to generate a proxy key independent of the long-term key. We call such construction a full construction. There exists a simple method to the full construction from any BPW transformed proxy signature (cf. Section 5 of [15]).(i)
After obtaining the delegation information(
P
K, W, C, j, S
K
P
(
i
′
-
1
)
), the proxy first generates a fresh proxy key pair (
SK
P
0
′
,
P
K
P
′
)
←
$
K
g
*
(
1
k
).
(ii)
Compute(
c
e
r
t
′, S
K
P
i
′
)
←
$
S
i
g
n
*
(
S
K
P
(
i
′
-
1
), 00
∥
P
K
P
′
∥
0
∥
c
e
r
t
), where c
e
r
t
∈
C is the delegation certificate from the delegator.
(iii)
The new delegation information is(
P
K
′, W, C
′
,
j
′, S
K
P
0
′
), where P
K
′
∈
P
K
′ and c
e
r
t
′
∈
C
′.The concrete full construction of such proxy signature scheme and corresponding security analysis are presented in Appendices.


### 3.2. Implement Secure Mobile Agent from Proxy Signature Scheme

When we realize a mobile agent system construction by using a secure proxy signature scheme let the clients be the delegators and let the mobile agent be the proxy. Then the clients and the agent together run the interactive delegation protocol to delegate the client’s signing right to the agent. Finally, the agent can sign some specified messages on behalf of the client. A secure proxy signature scheme implies a secure mobile agent system; similarly, a leakage-resilient proxy signature scheme means that the corresponding mobile agent system can be resilient to some bounded information leakage.


### 3.3. Security of the Leakage-Resilient Proxy Signatures

We put forward the security model of existential unforgeability against adaptive chosen message and leakage attacks (EU-CMLA) for the proxy signatures in the presence of leakage. It defined by the following experimentE
x
p
S
I
G
*
,
A
eu-cmla which is played by a challenger B and a EU-CMLA adversary A who controls all user’s secret keys except the challenging user.(i)
B runs (
S
K
0
*
,
P
K
*
)
←
$
K
g
*
(
1
k
) and gives P
K
* to A.
(ii)
A can adaptively ask B for the following:
(a)
delegation toS
K
i
-
1
*: P
K
D
B interacts with A through the delegation protocol by running algorithm P
K
g
*
(
S
K
i
-
1
*, P
K
*, P
K
D). When it is finished, B will obtain the delegation information (
P
K
′, W
′, C
′, j
,
S
K
i
-
1
*
);
(b)
delegation ofS
K
i
-
1
*: (
P
K
P
,
W
j
)
B interacts with A through the delegation protocol to generate a proxy key to P
K
P; B runs D
e
l
*
(
S
K
i
-
1
*
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
). When it is finished, B returns the transcript of the delegation to A;
(c)
self-delegation ofS
K
i
-
1
*: W
B first runs (
S
K
0
′
,
P
K
′
)
←
$
K
g
* and then runs the delegation protocol to generate a proxy key to the challenging user itself, (
S
K
i
*
,
P
K
′
,
W
′
,
C
′
,
j
′
,
S
K
0
′
)
←
$
D
e
l
*
(
S
K
i
-
1
*
,
P
K
′
,
P
K
,
W
,
C
,
j
,
W
), P
K
g
*
(
S
K
0
′
,
P
K
′
,
P
K
*
). When it is finished, B will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
′
,
S
K
0
′
) and send the transcript of the delegation to A;
(d)
ordinary signing queries ofS
K
i
-
1
*: m
i
B runs (
Σ
i
,
S
K
i
*
)
←
$
S
i
g
n
*
(
S
K
i
-
1
*
,
m
i
) and returns Σ
i to A;
(e)
proxy signing queries ofS
K
i
-
1
*: (
P
K
,
W
,
C
,
j
,
m
i
)
B runs (
P
K
,
W
,
C
,
j
,
P
Σ
i
,
S
K
i
*
)
←
$
P
S
i
g
n
*
(
P
K, W
,
C
,
j
,
S
K
i
-
1
*
,
m
i
) and returns (
P
K, W, C, j
,
P
Σ
i
) to A
*;
(f)
leakage queries:f
i
A may adaptively launches leakage query after each query to the delegation protocol, ordinary signing, or proxy signing oracle; that is, these algorithms have taken as input the secret key S
K
i
-
1
*. B runs Λ
i
←
f
i
(
S
K
i
-
1
*
+
,
r
i
) and if Λ
i
≠
λ then it returns ⊥; else it returns Λ
i to A.
(iii)
At some point,A outputs a forgery which must be one of the following cases.
(1)
Ordinary signature ofP
K
*: (m
*
,
Σ
*)
if1
←
V
r
f
*
(
P
K
*
,
m
*
,
Σ
*
) and m
* has not been submitted to the ordinary signing queries, then output 1; else output 0.
(2)
Proxy signature ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the last entry in P
K
if1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and (
P
K
,
W
,
C
,
j
,
m
*
) has not submitted to the proxy signing queries, then output 1; else output 0.
(3)
Proxy signature on behalf ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the nth entry in P
K.
If1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and A has not queried the delegation of S
K
i
-
1
* oracle on inputs (P
K
n
+
1
,
W
n
+
1), that is, the (
n
+
1
)-th entry in the set P
K), then output 1 else output 0.We say that A wins the above experiment E
x
p
S
I
G
*
,
A
eu-cmla if it outputs a valid forgery. We denote the probability of A succeeded by A
d
v
S
I
G
*
,
A
eu-cmla. We say S
I
G
* is EU-CMLA secure if A
d
v
S
I
G
*
,
A
eu-cmla is negligible for every PPT adversary A.Remark. In the model of EU-CMA-PKE, A is allowed to query a redelegation of a user’s proxy key. However, we define the LRPS under the BPW transformation model (i.e., the user’s proxy key is exactly its secret key), so in the model of EU-CMLA, A can run the redelegation by itself except that the redelegation of S
K
i
-
1
* which can be obtained from the query of delegation of S
K
i
-
1
* in such setting. Similarly, A has no need to query the proxy key exposure queries.


## 3.1. Syntax

Formally, we define the stateful proxy signatures (under the BPW transformation) as follows. That is to say,S
I
G
*
=
(
K
g
*
,
S
i
g
n
*
,
V
f
y
*
,
D
e
l
*
,
P
K
g
*
,
P
S
i
g
n
*
,
P
V
f
y
*
) is a stateful proxy signature scheme if the first three algorithms are defined as K
g, S
i
g
n, and V
f
y of the scheme S
I
G, respectively, and the latter three algorithms satisfy the following.(i)
D
e
l
*
,
P
K
g
* is a pair of interactive PPT delegation protocol which means that the delegator D  whose stateful key is (
S
K
D
(
i
-
1
)
,
P
K
D
) delegates its signing right to a proxy P who has a stateful key pair (
S
K
P
(
i
′
-
1
)
,
P
K
P
).
(a)
D
e
l
* is run by the delegator with input (
S
K
D
(
i
-
1
), P
K
P, P
K, W, C, j, W
j
), where P
K, W, and C are the lists of public keys, warrants, and delegation certificates of the previous delegators, respectively, j describes the current proxy is the jth proxy in the delegation chain (j
=
0 means that the delegator is the original signer), and W
j is the warrant for the current delegation.
(b)
P
K
g
* is run by the proxy with input (
S
K
P
(
i
′
-
1
), P
K
P, P
K
D
) to generate its proxy key.As a result of this interactive algorithm, the algorithm D
e
l
* has no local output except that the delegator’s next stateful key S
K
D
i. The local output of P
K
g
* is the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
S
K
P
(
i
′
-
1
)
), where P
K
′, W
′, and C
′ are the lists of public keys, warrants, and certificates in the delegation chain extended with the public key of the proxy and warrant and certificate of the current delegation, respectively. We write it (S
K
D
i, P
K
′, W
′, C
′, j
,
S
K
P
(
i
′
-
1
)
)
←
$
D
e
l
*
(
S
K
D
(
i
-
1
)
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
), P
K
g
*
(
S
K
P
(
i
′
-
1
)
,
P
K
P
,
P
K
D
). (ii)
P
S
i
g
n
* is a PPT algorithm run by a proxy that takes as input its delegation information (
P
K, W, C, j, S
K
P
(
i
′
-
1
)
) and a message m
i and then outputs a proxy signature (
P
K
,
W
,
C
,
j
,
P
Σ
i
) on behalf of the delegator and its next stateful key S
K
P
i
′. We write it (
P
K, W, C, j, P
Σ
i, S
K
P
i
′
)
←
$
P
S
i
g
n
*
(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
′
-
1
)
,
m
i
).
(iii)
P
V
f
y
* is a deterministic algorithm run by the verifier who takes as input (
P
K
,
W
,
C
,
j
,
m
i
,
P
Σ
i
) and then outputs 1 if it is valid; else it outputs 0. We write it 1
/
0
←
P
V
f
y
*
(
P
K
,
W
,
C
,
j
,
m
i
,
P
Σ
i
).In the real world applications, user’s long-term secret key should be stored in a secure way and thus to guarantee that no information about the long-term key is leaked while the proxy key is exposed, it is better to generate a proxy key independent of the long-term key. We call such construction a full construction. There exists a simple method to the full construction from any BPW transformed proxy signature (cf. Section 5 of [15]).(i)
After obtaining the delegation information(
P
K, W, C, j, S
K
P
(
i
′
-
1
)
), the proxy first generates a fresh proxy key pair (
SK
P
0
′
,
P
K
P
′
)
←
$
K
g
*
(
1
k
).
(ii)
Compute(
c
e
r
t
′, S
K
P
i
′
)
←
$
S
i
g
n
*
(
S
K
P
(
i
′
-
1
), 00
∥
P
K
P
′
∥
0
∥
c
e
r
t
), where c
e
r
t
∈
C is the delegation certificate from the delegator.
(iii)
The new delegation information is(
P
K
′, W, C
′
,
j
′, S
K
P
0
′
), where P
K
′
∈
P
K
′ and c
e
r
t
′
∈
C
′.The concrete full construction of such proxy signature scheme and corresponding security analysis are presented in Appendices.


## 3.2. Implement Secure Mobile Agent from Proxy Signature Scheme

When we realize a mobile agent system construction by using a secure proxy signature scheme let the clients be the delegators and let the mobile agent be the proxy. Then the clients and the agent together run the interactive delegation protocol to delegate the client’s signing right to the agent. Finally, the agent can sign some specified messages on behalf of the client. A secure proxy signature scheme implies a secure mobile agent system; similarly, a leakage-resilient proxy signature scheme means that the corresponding mobile agent system can be resilient to some bounded information leakage.


## 3.3. Security of the Leakage-Resilient Proxy Signatures

We put forward the security model of existential unforgeability against adaptive chosen message and leakage attacks (EU-CMLA) for the proxy signatures in the presence of leakage. It defined by the following experimentE
x
p
S
I
G
*
,
A
eu-cmla which is played by a challenger B and a EU-CMLA adversary A who controls all user’s secret keys except the challenging user.(i)
B runs (
S
K
0
*
,
P
K
*
)
←
$
K
g
*
(
1
k
) and gives P
K
* to A.
(ii)
A can adaptively ask B for the following:
(a)
delegation toS
K
i
-
1
*: P
K
D
B interacts with A through the delegation protocol by running algorithm P
K
g
*
(
S
K
i
-
1
*, P
K
*, P
K
D). When it is finished, B will obtain the delegation information (
P
K
′, W
′, C
′, j
,
S
K
i
-
1
*
);
(b)
delegation ofS
K
i
-
1
*: (
P
K
P
,
W
j
)
B interacts with A through the delegation protocol to generate a proxy key to P
K
P; B runs D
e
l
*
(
S
K
i
-
1
*
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
). When it is finished, B returns the transcript of the delegation to A;
(c)
self-delegation ofS
K
i
-
1
*: W
B first runs (
S
K
0
′
,
P
K
′
)
←
$
K
g
* and then runs the delegation protocol to generate a proxy key to the challenging user itself, (
S
K
i
*
,
P
K
′
,
W
′
,
C
′
,
j
′
,
S
K
0
′
)
←
$
D
e
l
*
(
S
K
i
-
1
*
,
P
K
′
,
P
K
,
W
,
C
,
j
,
W
), P
K
g
*
(
S
K
0
′
,
P
K
′
,
P
K
*
). When it is finished, B will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
′
,
S
K
0
′
) and send the transcript of the delegation to A;
(d)
ordinary signing queries ofS
K
i
-
1
*: m
i
B runs (
Σ
i
,
S
K
i
*
)
←
$
S
i
g
n
*
(
S
K
i
-
1
*
,
m
i
) and returns Σ
i to A;
(e)
proxy signing queries ofS
K
i
-
1
*: (
P
K
,
W
,
C
,
j
,
m
i
)
B runs (
P
K
,
W
,
C
,
j
,
P
Σ
i
,
S
K
i
*
)
←
$
P
S
i
g
n
*
(
P
K, W
,
C
,
j
,
S
K
i
-
1
*
,
m
i
) and returns (
P
K, W, C, j
,
P
Σ
i
) to A
*;
(f)
leakage queries:f
i
A may adaptively launches leakage query after each query to the delegation protocol, ordinary signing, or proxy signing oracle; that is, these algorithms have taken as input the secret key S
K
i
-
1
*. B runs Λ
i
←
f
i
(
S
K
i
-
1
*
+
,
r
i
) and if Λ
i
≠
λ then it returns ⊥; else it returns Λ
i to A.
(iii)
At some point,A outputs a forgery which must be one of the following cases.
(1)
Ordinary signature ofP
K
*: (m
*
,
Σ
*)
if1
←
V
r
f
*
(
P
K
*
,
m
*
,
Σ
*
) and m
* has not been submitted to the ordinary signing queries, then output 1; else output 0.
(2)
Proxy signature ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the last entry in P
K
if1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and (
P
K
,
W
,
C
,
j
,
m
*
) has not submitted to the proxy signing queries, then output 1; else output 0.
(3)
Proxy signature on behalf ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the nth entry in P
K.
If1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and A has not queried the delegation of S
K
i
-
1
* oracle on inputs (P
K
n
+
1
,
W
n
+
1), that is, the (
n
+
1
)-th entry in the set P
K), then output 1 else output 0.We say that A wins the above experiment E
x
p
S
I
G
*
,
A
eu-cmla if it outputs a valid forgery. We denote the probability of A succeeded by A
d
v
S
I
G
*
,
A
eu-cmla. We say S
I
G
* is EU-CMLA secure if A
d
v
S
I
G
*
,
A
eu-cmla is negligible for every PPT adversary A.Remark. In the model of EU-CMA-PKE, A is allowed to query a redelegation of a user’s proxy key. However, we define the LRPS under the BPW transformation model (i.e., the user’s proxy key is exactly its secret key), so in the model of EU-CMLA, A can run the redelegation by itself except that the redelegation of S
K
i
-
1
* which can be obtained from the query of delegation of S
K
i
-
1
* in such setting. Similarly, A has no need to query the proxy key exposure queries.


## 4. Construction of Leakage-Resilient Proxy Signatures

In this section, we present a concrete construction of the LRPS schemeS
I
G
* based on FKPR signature scheme which can be instantiated with any EU-CMTLA (existential unforgeability against chosen message and total leakage attacks) 3-time signature scheme s
i
g
=
(
k
g
,
s
i
g
n
,
v
f
y
).Before giving the detailed description of theS
I
G
*, we first introduce some notations relative to the tree-based (with depth d
∈
N) signature. We denote the all bit strings of length at most d (including the empty string ε) with {
0,1
}
≤
d
=
⋃
i
=
1
d
‍
{
0,1
}
i
∪
ε (size 2
d
+
1
-
1). The left and right child of an internal node (or root) w
∈
{
0,1
}
≤
d
-
1 are denoted by w
∥
0 and w
∥
1, respectively, and par
(
w
) denotes the node w’s parent node.Depth-first traversal algorithm can be used to traverse and label the tree. For a node w
∈
{
0,1
}
≤
d
∖
1
d, we define algorithm D
F
(
w
) as the node traversed after w in the depth-first traversal; that is,(1)
D
F
(
w
)
∶
=
w
∥
0
,
if
w
<
d
w
is
the
root
or
an
internal
node
w
′
∥
1
,
if
w
=
d
,
where
w
=
w
′
∥
0
∥
1
j
w
is
a
leaf
.When the depth-first algorithm traverses the binary tree, each node w is associated with a secret-public key pair (
s
k
w
,
p
k
w
) by invoking the k
g algorithm of the underlying signature scheme s
i
g. The following notations will be used in the latter part of this paper. Let w
=
w
1
w
2
⋯
w
t be a bit string with length t.(i)
Γ
w
∶
=
{
p
k
w
,
ϕ
w
,
…
,
(
p
k
w
1
w
2
,
ϕ
w
1
w
2
), (
p
k
w
1
,
ϕ
w
1
)
} is a “signature path” from w to the root; ϕ
w
′ is a signature of 010
∥
p
k
w
′ with its parent’s key s
k
par
(
w
′
); that is, ϕ
w
′
←
$
s
i
g
n
(
s
k
par
(
w
′
)
,
010
∥
p
k
w
′
).
(ii)
S
w
∶
=
{
s
k
w
1
w
2
⋯
w
i
∣
w
i
+
1
=
0
} is a subset of the secret keys on the path from the root ε to node w. s
k
w
′
∈
S
w if and only if the path goes to the left child w
′
∥
0 at the node w
′. (The reason is that, in this case, the node w
′’s right child w
′
∥
1 will be traversed after node w under the depth-first traversal. Consequently, we need the secret key s
k
w
′ of node w
′ to sign its right child w
′
∥
1’s public key p
k
w
′
∥
1.)The stateful secret key of the schemeS
I
G
* will have the form (
w
,
S
w
,
Γ
w
) (i.e., using stacks S
w and Γ
w to keep track of the state, or node w). For a stack S, define the following three algorithms:(1)
p
u
s
h
(
S
,
a
): putting element a on the stack S;
(2)
a
←
p
o
p
(
S
): removing the topmost element from the stack S and assigning it to a;
(3)
t
r
a
s
h
(
S
): removing the topmost element from the stack S.


### 4.1. Construction

To avoid trivial attacks against this scheme, we use the idea of Boldyreva et al. [13], attach a 3-bit string as the prefix of the text that will be signed, that is, 111∥(text which will be to compute ordinary signatures), 010∥(text which will be to compute signature paths), 100∥(text which will be to compute delegation certificates), and 101∥(text which will be to compute proxy signatures), respectively. The LRPS scheme S
I
G
* is constructed as follows.(i)
K
g
*
(
1
k
):
(
s
k
ε
,
p
k
ε
)
←
$
K
g
(
1
k
)
,
S
ε
∶
=
s
k
ε
,
Γ
ε
∶
=
∅
,
S
K
ε
∶
=
(
w
ε
,
S
ε
,
Γ
ε
)
,
PK
∶
=
p
k
ε; return (
S
K
ε
,
PK
).
(ii)
S
i
g
n
*
(
S
K
w
,
m
): (to ease exposition, the signing process of the root ε (i.e., σ
←
$
s
i
g
n
(
s
k
ε
,
111
∥
m
)) is not contained in this formalizing description)
parseS
K
w
∶
=
(
w
,
S
w
,
Γ
w
); if w
=
1
d return ⊥; w
^
←
D
F
(
w
), (
s
k
w
^
,
p
k
w
^
)
←
$
K
g
(
1
k
)
σ
←
$
s
i
g
n
(
s
k
w
^
,
111
∥
m
)
;
s
k
par
(
w
^
)
←
p
o
p
(
S
w
)
;
ϕ
w
^
←
$
s
i
g
n
(
s
k
par
(
w
^
)
,
010
∥
p
k
w
^
)
(2)
if
w
^
|
w
^
|
=
0
,
S
w
⟵
p
u
s
h
(
S
w
,
s
k
par
(
w
^
)
)
if
w
^
<
d
,
S
w
^
⟵
p
u
s
h
(
S
w
,
s
k
w
^
)
if
w
=
d
,
w
=
w
′
0
1
j
,
for
i
=
1
,
…
,
j
+
1
,
do
t
r
a
s
h
Γ
w
Γ
w
^
←
p
u
s
h
(
Γ
w
,
(
p
k
w
^
,
ϕ
w
^
)
)
;
Σ
∶
=
(
σ
,
Γ
w
^
)
;
S
K
w
^
∶
=
(
w
^
,
S
w
^
,
Γ
w
^
); return (
Σ
,
S
K
w
^
).
(iii)
V
f
y
*
(
PK
,
m
,
Σ
):
parseΣ
∶
=
(
σ
,
Γ
w
^
1
w
^
2
⋯
w
^
|
w
^
|
), p
k
ε
∶
=
PK; for i
=
1
,
…
,
w
^ do
if0
←
v
f
y
(
p
k
w
^
1
⋯
w
^
i
-
1
,
010
∥
p
k
w
^
1
⋯
w
^
i
,
ϕ
w
^
1
⋯
w
^
i
) return 0;
else returnv
f
y
(
p
k
w
^
1
w
^
2
⋯
w
^
|
w
^
|
,
111
∥
m
,
σ
).
(iv)
D
e
l
*
(
S
K
D
(
i
-
1
)
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
):
D  runs (
c
e
r
t
j, S
K
D
i
)
←
$
S
i
g
n
*
(
S
K
D
(
i
-
1
), 100
∥
P
K
P
∥
j
∥
W
j
) and
then sends(
P
K, W, C, j, W
j, c
e
r
t
j
) to P.
(v)
P
K
g
*
(
S
K
P
(
i
′
-
1
)
,
P
K
P
,
P
K
D
):
P  first checks the validity of the delegation certificates, for k
=
1
,
…
,
j does
if0
←
V
f
y
*
(
P
K
k
-
1
,
100
∥
P
K
k
∥
k
∥
W
k
,
c
e
r
t
k
), it returns ⊥ and rejects this delegation;
otherwise, runP
K
←
p
u
s
h
(
P
K
,
P
K
P
)
,
W
←
p
u
s
h
(
W
,
W
j
)
,
C
←
p
u
s
h
(
C
,
c
e
r
t
j
);
finally, set the delegation information as(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
′
-
1
)
).
If someone, whose key pair is(
S
K
S
D
(
i
-
1
)
,
P
K
S
D
), wants to designate itself as a proxy it runs (
S
K
P
0
′
,
P
K
P
′
)
←
$
K
g
*
(
1
k
) to generate a fresh key pair as the proxy key and creates a certificate (
c
e
r
t
′
,
S
K
S
D
i
)
←
$
S
i
g
n
*
(
S
K
S
D
i
-
1
,
100
∥
P
K
P
′
∥
0
∥
W
′
), then does(3)
P
K
⟵
p
u
s
h
(
P
K
,
P
K
P
′
)
,
W
⟵
p
u
s
h
(
W
,
W
′
)
,
C
⟵
p
u
s
h
(
C
,
c
e
r
t
′
)
;
finally, it sets the delegation information as(
P
K
,
W
,
C
,
j
,
S
K
P
0
′
).
(vi)
P
S
i
g
n
*
(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
-
1
)
,
m
):
(
Σ
,
S
K
P
i
)
←
$
S
i
g
n
*
(
S
K
P
(
i
-
1
)
,
101
∥
m
) and output the proxy signature (
P
K
,
W
,
C
,
j
,
P
Σ
∶
=
Σ
).
(vii)
P
V
f
y
*
(
P
K
,
W
,
C
,
j
,
m
,
P
Σ
):
V  first checks the validity of the delegation certificates, for k
=
1
,
…
,
j does
if0
←
V
f
y
*
(
P
K
k
-
1
,
100
∥
P
K
k
∥
k
∥
W
k
,
c
e
r
t
k
) returns 0;
else it returnsV
f
y
*
(
P
K
j
,
101
∥
m
,
P
Σ
).Upper Bound of the Number of the Messages Can Be Signed. For a fixed signing key, in both of the schemes FKPR and S
I
G
*, the upper bound of the number of the message that can be signed is q
=
2
d
+
1
-
2. We can see that, from the above construction, each internal node is used only one time to the signing algorithm. However, the key (with respect to the schemesig) of any leaf can be signed three times. Hence, the upper bound of the number of the message can be signed and could be increased to 2
d
+
2
-
4 that is double the number of the previous upper bound, as well as the FKPR scheme.We should stress here that there is a disadvantage to our scheme which is based on tree-based signature compared to that constructed based on aggregate signature [13, 15]; that is, in those schemes, the verification of the delegation certificates can be executed at a time due to the property of aggregability of the aggregate signatures [41].


### 4.2. Security

We now analyze the security of the proposed LRPS scheme.Theorem 1.
If the FKPR scheme (denoted byS
I
G) is EU-CMLA secure, then the proxy signature scheme S
I
G
* also is EU-CMLA secure.Our proof line is similar to that of Boldyreva et al.’s [13]. If there exists a EU-CMLA adversary and A can break the security of the scheme S
I
G
*, then we can construct a challenger B to break the security of the FKPR scheme S
I
G.(i)
Initially,B will be given a challenging public key P
K
′ and can adaptively make signing query (S
Q) and leakage query (L
Q) in the experiment E
x
p
S
I
G
,
B
eu-cmla. B first sets P
K
*
∶
=
P
K
′ as the challenging public key of the experiment E
x
p
S
I
G
*
,
A
eu-cmla and sends it to A. Then it plays the experiment with A.
(ii)
A may adaptively ask B for the following.
(a)
Delegation toS
K
i
-
1
*: P
K
D
B interacts with A through the delegation protocol by running P
K
g
*
(
*
,
P
K
*
,
P
K
D). When it is finished, B will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
*
). B can run the P
K
g
* algorithm even if it has no idea about the S
K
i
-
1
*, because S
K
i
-
1
* will be set as the proxy key of the challenging user, so upon completion, B does not know the corresponding proxy key.
(b)
Delegation fromS
K
i
-
1
*: (
P
K
P
,
W
j
)
B interacts with A through the delegation protocol to generate a proxy key to P
K
P. B makes the signing query S
Q with input 00
∥
P
K
P
∥
j
∥
W
j; then it will be returned Σ. After the delegation protocol is finished, A will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
*
), where P
K
P
∈
P
K
′
,
W
j
∈
W
′, and c
e
r
t
j
:
=
Σ
∈
C
′.
(c)
Self-delegation ofS
K
i
-
1
*: W
B runs the delegation protocol to generate a proxy key of P
K
* to itself. B first runs (
S
K
0
′
,
P
K
′
)
←
$
K
g
* and then makes the signing query S
Q with input 00
∥
P
K
′
∥
0
∥
W; then it will be returned to Σ. Finally, B will return the delegation information (
P
K
′, W
′, C
′, 0, S
K
0
′
) and sends the delegation transcripts to A, where P
K
′
∈
P
K
′
,
W
∈
W
′, and c
e
r
t
′
∶
=
Σ
∈
C
′.
(d)
Ordinary signing queries ofS
K
i
-
1
*: m
i
B makes the signing query S
Q with input 11
∥
m
i; then it will be returned to signature Σ. Finally, B returns Σ to A.
(e)
Proxy signing queries ofS
K
i
-
1
*: (
P
K
,
W
,
C
,
j
,
m
i
)
B makes the signing query S
Q with input 01
∥
m
i; then it will be returned to signature Σ. Finally, B returns (
P
K
,
W
,
C
,
j
,
P
Σ
∶
=
Σ
) to A.
(f)
Leakage queries:f
i
A may make query f
i for the leakage information after each delegation protocol, ordinary signing, or proxy signing query. To answer it, B makes the same query to L
Q; it will be returned as a valid leakage information Λ
i or ⊥ if f
i is illegal. Finally, B returns it to A.
Remark. In the construction of scheme S
I
G
*, except for the S
i
g
n
* algorithm, there are also two algorithms using the signing or proxy signing key, the D
e
l
* and P
S
i
g
n
*. Actually, however, they are also a signing algorithm just with different input of text, so the leakage information answered by B (from L
Q) is indistinguishable to what A obtains in the real interaction in the experiment E
x
p
S
I
G
*
,
A
eu-cmla.
(iii)
Finally, according to the assumption,A outputs a forgery for the challenging public key P
K
* with respect to scheme S
I
G
*. It must be one of the following cases. We now show the challenger B how to translate A’s forgery as a forgery with respect to the FKPR scheme S
I
G.
(1)
Ordinary signature ofP
K
*: (
m
*
,
Σ
*
)
IfA outputs an ordinary signature (
m
*
,
Σ
*
) of P
K
*, then B outputs (
11
∥
m
*
,
Σ
*
).
(2)
Proxy signature ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the last entry in P
K.
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
) of P
K
*, B outputs (
01
∥
m
*
,
Σ
*
).
(3)
Proxy signature on behalf ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the nth entry in the list P
K.
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
) on behalf of P
K
*, then B outputs (
00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n
,
c
e
r
t
n
+
1
).Analysis of
B. It is clear that the view of A which is answered by B in the above experiment is identical to what A obtains in the real interaction in the experiment E
x
p
S
I
G
*
,
A
eu-cmla. We now show that any valid output of the adversary A can be translated to a valid forgery with respect to the FKPR scheme S
I
G.(1)
IfA outputs an ordinary signature (
m
*
,
Σ
*
), 1
←
V
r
f
*
(
P
K
*
,
m
*
,
Σ
*
), and m
* has not been submitted to the ordinary signing queries, so B does not make the signing query S
Q with input 11
∥
m
*. Therefore, (
11
∥
m
*
,
Σ
*
) is a valid forgery with respect to the scheme S
I
G.
(2)
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), 1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
), and (
P
K
,
W
,
C
,
j
,
m
*
) has not submitted to the proxy signing queries, so B does not make the signing query S
Q with input 01
∥
m
*. Therefore, (
01
∥
m
*
,
P
Σ
*
) is a valid forgery with respect to the scheme S
I
G.
(3)
IfA outputs a proxy signature on behalf of P
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), where P
K
* is the nth entry in P
K, 1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and A does not make the query of delegation from S
K
i
-
1
* with input (
P
K
n
+
1
,
W
n
+
1
) ((
n
+
1
)th entry in P
K), so B does not make the signing query S
Q with input 00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n. Therefore, (
00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n
,
c
e
r
t
n
+
1
) is a valid forgery with respect to the scheme S
I
G.From the above analysis, we can see that the challengerB’s output of forgery is contradictory to the security of the FKPR scheme S
I
G (cf. Theorem 1 of [37]) and thus proves the security of the LRPS scheme S
I
G
*.


## 4.1. Construction

To avoid trivial attacks against this scheme, we use the idea of Boldyreva et al. [13], attach a 3-bit string as the prefix of the text that will be signed, that is, 111∥(text which will be to compute ordinary signatures), 010∥(text which will be to compute signature paths), 100∥(text which will be to compute delegation certificates), and 101∥(text which will be to compute proxy signatures), respectively. The LRPS scheme S
I
G
* is constructed as follows.(i)
K
g
*
(
1
k
):
(
s
k
ε
,
p
k
ε
)
←
$
K
g
(
1
k
)
,
S
ε
∶
=
s
k
ε
,
Γ
ε
∶
=
∅
,
S
K
ε
∶
=
(
w
ε
,
S
ε
,
Γ
ε
)
,
PK
∶
=
p
k
ε; return (
S
K
ε
,
PK
).
(ii)
S
i
g
n
*
(
S
K
w
,
m
): (to ease exposition, the signing process of the root ε (i.e., σ
←
$
s
i
g
n
(
s
k
ε
,
111
∥
m
)) is not contained in this formalizing description)
parseS
K
w
∶
=
(
w
,
S
w
,
Γ
w
); if w
=
1
d return ⊥; w
^
←
D
F
(
w
), (
s
k
w
^
,
p
k
w
^
)
←
$
K
g
(
1
k
)
σ
←
$
s
i
g
n
(
s
k
w
^
,
111
∥
m
)
;
s
k
par
(
w
^
)
←
p
o
p
(
S
w
)
;
ϕ
w
^
←
$
s
i
g
n
(
s
k
par
(
w
^
)
,
010
∥
p
k
w
^
)
(2)
if
w
^
|
w
^
|
=
0
,
S
w
⟵
p
u
s
h
(
S
w
,
s
k
par
(
w
^
)
)
if
w
^
<
d
,
S
w
^
⟵
p
u
s
h
(
S
w
,
s
k
w
^
)
if
w
=
d
,
w
=
w
′
0
1
j
,
for
i
=
1
,
…
,
j
+
1
,
do
t
r
a
s
h
Γ
w
Γ
w
^
←
p
u
s
h
(
Γ
w
,
(
p
k
w
^
,
ϕ
w
^
)
)
;
Σ
∶
=
(
σ
,
Γ
w
^
)
;
S
K
w
^
∶
=
(
w
^
,
S
w
^
,
Γ
w
^
); return (
Σ
,
S
K
w
^
).
(iii)
V
f
y
*
(
PK
,
m
,
Σ
):
parseΣ
∶
=
(
σ
,
Γ
w
^
1
w
^
2
⋯
w
^
|
w
^
|
), p
k
ε
∶
=
PK; for i
=
1
,
…
,
w
^ do
if0
←
v
f
y
(
p
k
w
^
1
⋯
w
^
i
-
1
,
010
∥
p
k
w
^
1
⋯
w
^
i
,
ϕ
w
^
1
⋯
w
^
i
) return 0;
else returnv
f
y
(
p
k
w
^
1
w
^
2
⋯
w
^
|
w
^
|
,
111
∥
m
,
σ
).
(iv)
D
e
l
*
(
S
K
D
(
i
-
1
)
,
P
K
P
,
P
K
,
W
,
C
,
j
,
W
j
):
D  runs (
c
e
r
t
j, S
K
D
i
)
←
$
S
i
g
n
*
(
S
K
D
(
i
-
1
), 100
∥
P
K
P
∥
j
∥
W
j
) and
then sends(
P
K, W, C, j, W
j, c
e
r
t
j
) to P.
(v)
P
K
g
*
(
S
K
P
(
i
′
-
1
)
,
P
K
P
,
P
K
D
):
P  first checks the validity of the delegation certificates, for k
=
1
,
…
,
j does
if0
←
V
f
y
*
(
P
K
k
-
1
,
100
∥
P
K
k
∥
k
∥
W
k
,
c
e
r
t
k
), it returns ⊥ and rejects this delegation;
otherwise, runP
K
←
p
u
s
h
(
P
K
,
P
K
P
)
,
W
←
p
u
s
h
(
W
,
W
j
)
,
C
←
p
u
s
h
(
C
,
c
e
r
t
j
);
finally, set the delegation information as(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
′
-
1
)
).
If someone, whose key pair is(
S
K
S
D
(
i
-
1
)
,
P
K
S
D
), wants to designate itself as a proxy it runs (
S
K
P
0
′
,
P
K
P
′
)
←
$
K
g
*
(
1
k
) to generate a fresh key pair as the proxy key and creates a certificate (
c
e
r
t
′
,
S
K
S
D
i
)
←
$
S
i
g
n
*
(
S
K
S
D
i
-
1
,
100
∥
P
K
P
′
∥
0
∥
W
′
), then does(3)
P
K
⟵
p
u
s
h
(
P
K
,
P
K
P
′
)
,
W
⟵
p
u
s
h
(
W
,
W
′
)
,
C
⟵
p
u
s
h
(
C
,
c
e
r
t
′
)
;
finally, it sets the delegation information as(
P
K
,
W
,
C
,
j
,
S
K
P
0
′
).
(vi)
P
S
i
g
n
*
(
P
K
,
W
,
C
,
j
,
S
K
P
(
i
-
1
)
,
m
):
(
Σ
,
S
K
P
i
)
←
$
S
i
g
n
*
(
S
K
P
(
i
-
1
)
,
101
∥
m
) and output the proxy signature (
P
K
,
W
,
C
,
j
,
P
Σ
∶
=
Σ
).
(vii)
P
V
f
y
*
(
P
K
,
W
,
C
,
j
,
m
,
P
Σ
):
V  first checks the validity of the delegation certificates, for k
=
1
,
…
,
j does
if0
←
V
f
y
*
(
P
K
k
-
1
,
100
∥
P
K
k
∥
k
∥
W
k
,
c
e
r
t
k
) returns 0;
else it returnsV
f
y
*
(
P
K
j
,
101
∥
m
,
P
Σ
).Upper Bound of the Number of the Messages Can Be Signed. For a fixed signing key, in both of the schemes FKPR and S
I
G
*, the upper bound of the number of the message that can be signed is q
=
2
d
+
1
-
2. We can see that, from the above construction, each internal node is used only one time to the signing algorithm. However, the key (with respect to the schemesig) of any leaf can be signed three times. Hence, the upper bound of the number of the message can be signed and could be increased to 2
d
+
2
-
4 that is double the number of the previous upper bound, as well as the FKPR scheme.We should stress here that there is a disadvantage to our scheme which is based on tree-based signature compared to that constructed based on aggregate signature [13, 15]; that is, in those schemes, the verification of the delegation certificates can be executed at a time due to the property of aggregability of the aggregate signatures [41].


## 4.2. Security

We now analyze the security of the proposed LRPS scheme.Theorem 1.
If the FKPR scheme (denoted byS
I
G) is EU-CMLA secure, then the proxy signature scheme S
I
G
* also is EU-CMLA secure.Our proof line is similar to that of Boldyreva et al.’s [13]. If there exists a EU-CMLA adversary and A can break the security of the scheme S
I
G
*, then we can construct a challenger B to break the security of the FKPR scheme S
I
G.(i)
Initially,B will be given a challenging public key P
K
′ and can adaptively make signing query (S
Q) and leakage query (L
Q) in the experiment E
x
p
S
I
G
,
B
eu-cmla. B first sets P
K
*
∶
=
P
K
′ as the challenging public key of the experiment E
x
p
S
I
G
*
,
A
eu-cmla and sends it to A. Then it plays the experiment with A.
(ii)
A may adaptively ask B for the following.
(a)
Delegation toS
K
i
-
1
*: P
K
D
B interacts with A through the delegation protocol by running P
K
g
*
(
*
,
P
K
*
,
P
K
D). When it is finished, B will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
*
). B can run the P
K
g
* algorithm even if it has no idea about the S
K
i
-
1
*, because S
K
i
-
1
* will be set as the proxy key of the challenging user, so upon completion, B does not know the corresponding proxy key.
(b)
Delegation fromS
K
i
-
1
*: (
P
K
P
,
W
j
)
B interacts with A through the delegation protocol to generate a proxy key to P
K
P. B makes the signing query S
Q with input 00
∥
P
K
P
∥
j
∥
W
j; then it will be returned Σ. After the delegation protocol is finished, A will obtain the delegation information (
P
K
′
,
W
′
,
C
′
,
j
,
*
), where P
K
P
∈
P
K
′
,
W
j
∈
W
′, and c
e
r
t
j
:
=
Σ
∈
C
′.
(c)
Self-delegation ofS
K
i
-
1
*: W
B runs the delegation protocol to generate a proxy key of P
K
* to itself. B first runs (
S
K
0
′
,
P
K
′
)
←
$
K
g
* and then makes the signing query S
Q with input 00
∥
P
K
′
∥
0
∥
W; then it will be returned to Σ. Finally, B will return the delegation information (
P
K
′, W
′, C
′, 0, S
K
0
′
) and sends the delegation transcripts to A, where P
K
′
∈
P
K
′
,
W
∈
W
′, and c
e
r
t
′
∶
=
Σ
∈
C
′.
(d)
Ordinary signing queries ofS
K
i
-
1
*: m
i
B makes the signing query S
Q with input 11
∥
m
i; then it will be returned to signature Σ. Finally, B returns Σ to A.
(e)
Proxy signing queries ofS
K
i
-
1
*: (
P
K
,
W
,
C
,
j
,
m
i
)
B makes the signing query S
Q with input 01
∥
m
i; then it will be returned to signature Σ. Finally, B returns (
P
K
,
W
,
C
,
j
,
P
Σ
∶
=
Σ
) to A.
(f)
Leakage queries:f
i
A may make query f
i for the leakage information after each delegation protocol, ordinary signing, or proxy signing query. To answer it, B makes the same query to L
Q; it will be returned as a valid leakage information Λ
i or ⊥ if f
i is illegal. Finally, B returns it to A.
Remark. In the construction of scheme S
I
G
*, except for the S
i
g
n
* algorithm, there are also two algorithms using the signing or proxy signing key, the D
e
l
* and P
S
i
g
n
*. Actually, however, they are also a signing algorithm just with different input of text, so the leakage information answered by B (from L
Q) is indistinguishable to what A obtains in the real interaction in the experiment E
x
p
S
I
G
*
,
A
eu-cmla.
(iii)
Finally, according to the assumption,A outputs a forgery for the challenging public key P
K
* with respect to scheme S
I
G
*. It must be one of the following cases. We now show the challenger B how to translate A’s forgery as a forgery with respect to the FKPR scheme S
I
G.
(1)
Ordinary signature ofP
K
*: (
m
*
,
Σ
*
)
IfA outputs an ordinary signature (
m
*
,
Σ
*
) of P
K
*, then B outputs (
11
∥
m
*
,
Σ
*
).
(2)
Proxy signature ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the last entry in P
K.
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
) of P
K
*, B outputs (
01
∥
m
*
,
Σ
*
).
(3)
Proxy signature on behalf ofP
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), P
K
* is the nth entry in the list P
K.
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
) on behalf of P
K
*, then B outputs (
00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n
,
c
e
r
t
n
+
1
).Analysis of
B. It is clear that the view of A which is answered by B in the above experiment is identical to what A obtains in the real interaction in the experiment E
x
p
S
I
G
*
,
A
eu-cmla. We now show that any valid output of the adversary A can be translated to a valid forgery with respect to the FKPR scheme S
I
G.(1)
IfA outputs an ordinary signature (
m
*
,
Σ
*
), 1
←
V
r
f
*
(
P
K
*
,
m
*
,
Σ
*
), and m
* has not been submitted to the ordinary signing queries, so B does not make the signing query S
Q with input 11
∥
m
*. Therefore, (
11
∥
m
*
,
Σ
*
) is a valid forgery with respect to the scheme S
I
G.
(2)
IfA outputs a proxy signature (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), 1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
), and (
P
K
,
W
,
C
,
j
,
m
*
) has not submitted to the proxy signing queries, so B does not make the signing query S
Q with input 01
∥
m
*. Therefore, (
01
∥
m
*
,
P
Σ
*
) is a valid forgery with respect to the scheme S
I
G.
(3)
IfA outputs a proxy signature on behalf of P
K
*: (
m
*
,
(
P
K
,
W
,
C
,
j
,
P
Σ
*
)
), where P
K
* is the nth entry in P
K, 1
←
P
V
r
f
*
(
P
K
,
W
,
C
,
j
,
m
*
,
P
Σ
*
) and A does not make the query of delegation from S
K
i
-
1
* with input (
P
K
n
+
1
,
W
n
+
1
) ((
n
+
1
)th entry in P
K), so B does not make the signing query S
Q with input 00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n. Therefore, (
00
∥
P
K
n
+
1
∥
n
+
1
∥
W
n
,
c
e
r
t
n
+
1
) is a valid forgery with respect to the scheme S
I
G.From the above analysis, we can see that the challengerB’s output of forgery is contradictory to the security of the FKPR scheme S
I
G (cf. Theorem 1 of [37]) and thus proves the security of the LRPS scheme S
I
G
*.


## 5. Conclusion

In this paper, we design a leakage-resilient proxy signature scheme, the LRPS. To model the security of such schemes, we adapt the existing models of the proxy signature schemes which are proposed by Schuldt et al. (in PKC 2008) [15] and Boldyreva et al. (in Jour. Crypto. 2012) [13] to the leakage-resilient cryptography setting and give an extended model, EU-CMLA, for the LRPS schemes. Furthermore, we present a concrete construction based on Faust et al.’s (in TCC 2010) [37] LR signature scheme. This construction is provably secure under the given security model.



---

*Source: 901418-2015-04-07.xml*