Fairness of exchange is a significant property for secure online transactions, and a fair exchange scheme is a useful tool for ensuring the fairness of exchanges conducted over networks. In this paper, we propose an ID-based optimistic fair exchange scheme based on the RSA function, one which is designed by combining a well-known RSA-based signature scheme and the (naive) RSA function. Note that the main contribution of this paper is to give the first provably secure ID-based fair exchange scheme based on the RSA function, whose security can be proved under fully formalized security models. Our scheme has the following additional strongpoints. The scheme is setup-free; hence, there is no registration step between a user and an arbitrator. Moreover, the proposed scheme is designed in an ID-based setting; thus, it is possible to eliminate the need for certificates and avoid some related problems.
I. Introduction
These days, certain basic social activities such as commercial transactions and business communications are more frequently conducted over networks through the use of computers. One significant security requirement for such activities is the fairness of exchange, in the sense that two communicating parties give and take items without allowing either party to gain an advantage through any wrongdoings. The fair exchange scheme is a useful tool for fair activities performed over the Internet that require such a level of security.
A simple way to implement fair exchange schemes is to adopt an arbitrator, who will then aid clients to exchange signatures in a fair manner. In such scenarios, two users may commit their signatures to an arbitrator, who then only forwards them to the intended receivers if the two signatures are valid. This simple approach is not efficient, since the arbitrator should participate in every execution of a fair exchange, even if there is no dispute between users. To overcome this shortcoming, an optimistic fair exchange scheme has been proposed by Asokan and others
[1]
where an arbitrator only becomes involved in the execution of an exchange if there is a dispute between the two parties. Simply, optimistic fair exchange schemes work as follows. First, each communicating party generates a partial signature and gives it to its communicating partner. When valid partial signatures are exchanged between communicating parties, each party gives additional information to its partner so that the partner can recover the full signature from the already exchanged partial signature. An arbitrator only becomes involved in the protocol when either party refuses to help its partner to obtain the required full signature. The arbitrator’s role is to recover a full signature from a partial signature without the assistance of either party.
Until now, numerous fair exchange schemes have been proposed based on various primitives
[1]
–
[13]
, and two paradigms have been mainly used for designing fair exchange schemes. One is based on verifiably encrypted signatures
[1]
–
[4]
, and the other is based on two-party multi-signatures
[8]
. In
[5]
, Dodis and Reyzin introduced verifiably committed signatures
[10]
–
[12]
that generalize verifiably encrypted signatures and two-party multi-signatures. A new paradigm has been proposed based on ID-based signatures
[9]
. Recently, a designated confirmer signature scheme was used in the design of a fair exchange scheme
[7]
.
Due to the convenience and simplicity of the RSA function, several fair exchange schemes based on the function itself have been proposed, but the greater part of them are insecure or inefficient. The scheme in
[14]
was broken by Cathalo, Libert, and Quisquater
[15]
. In
[8]
, a fair exchange scheme based on two-party multi-signatures has been proposed; unfortunately, the scheme is easily breakable at the registration phase
[5]
. In
[16]
, a simple fair exchange scheme based on ID-based mediated RSA has been proposed
[17]
. The scheme remains secure, but its security is not proved with formal language. The schemes in
[5]
,
[18]
, and
[19]
are secure, but they require costly zero-knowledge proofs. In
[20]
, a secure ID-based fair exchange scheme based on the RSA function has been proposed, but its security is not proved under fully formalized security models. In
[21]
–
[22]
, generic constructions have been proposed that permit us to easily obtain a provably secure fair exchange scheme from a set of component schemes (which are specified in each transform technique) without burdensome security analysis. In
[9]
, an efficient fair exchange scheme has been proposed by combining an RSA signature and a well-known ID-based signature
[23]
.
In 1984, Shamir
[24]
introduced the notion of identity-based public-key cryptography in an attempt to simplify key management procedures of traditional certificate-based public key infrastructure (PKI) by way of eliminating certificates. Since the first practical ID-based encryption based on bilinear pairings was proposed by Boneh and Franklin
[25]
, a rapid development of ID-based schemes has taken place based on pairing operations
[13]
,
[26]
–
[29]
, including ID-based fair exchange schemes. Until now, most ID-based fair exchange schemes have been designed based on pairing operations
[13]
,
[26]
,
[28]
; thus, it is worthy to design ID-based fair exchange schemes without the pairing operation for a variety of primitives. Note that RSA-based schemes are widely used in practice instead of pairing-based schemes due to the convenience and simplicity of the RSA function
[30]
. Hence, from a practical viewpoint, it is particularly worthwhile designing RSA-based schemes. However, only a small number of schemes based on the RSA function have been proposed, for such schemes are not easy to design.
One desirable property of a fair exchange is its setup-freeness. A fair exchange scheme is called setup-free if there is no registration step between a user and the arbitrator, and a fair exchange is called setup-driven if a user should interact with the arbitrator for registration. As indicated in
[21]
, a setup-free fair exchange is more advantageous than a setup-driven fair exchange. The first setup-free fair exchange scheme was proposed in
[3]
, and several schemes
[9]
–
[12]
,
[21]
have since been proposed with the property.
- 1. Contribution
Until now, several ID-based fair exchange schemes have been proposed, but only a few of these have been designed based on the RSA function. Some fair exchange schemes have been designed using either ID-based encryption or ID-based signatures as a component
[9]
,
[16]
, but they are not ID-based fair exchange schemes. Though generic construction strategies have been proposed in
[21]
–
[22]
, these techniques are not intended to be used in the design of ID-based fair exchange schemes. In
[20]
, an efficient fair exchange scheme based on the GQ-IBS scheme
[23]
has been proposed, but the security of the proposed scheme has not yet been verified under fully formalized security models.
In this paper, we propose an efficient ID-based optimistic fair exchange scheme based on the RSA function by combining the GQ-IBS scheme and the (naive) RSA function. We prove the security of the proposed fair exchange scheme under fully formalized security models based on the hardness of the RSA problem. The main contribution of this paper is to provide the first provably secure ID-based fair exchange scheme based on the RSA function, whose security can be proved under fully formalized security models. In
[20]
, an ID-based fair exchange scheme based on the GQ-IBS scheme has been proposed, as in our scheme, but so far attempts to prove its security under fully formalized security models have failed. Some significant points were not considered in the security proof (given in
[20]
). For example, security against an adversary — who can obtain multiple valid private keys — was not considered in
[20]
, which is one of the fundamental security requirements of ID-based schemes. Moreover, in
[20]
, one trusted party performed two sensitive roles — that of the key-issuer and that of the arbitrator. Note that recently formalized security models separate the role of the key-issuing server (KIS) and the arbitrator since it is desirable to separate these roles for higher security. Therefore, we can say that our scheme is the first provably secure ID-based fair exchange scheme that is designed based on the RSA function and whose security can be proved under fully formalized security models. The proposed scheme has some strongpoints. Our scheme is suitable for cryptographic engineering practices due to the simplicity of the RSA function, and the scheme is efficient in the sense that it provides almost the same performance compared with the underlying signature scheme. Moreover, the proposed scheme is designed in an ID-based setting; hence, it is possible to eliminate the need for certificates and avoid some related problems. Our scheme also achieves setup-freeness, which means that users can enjoy the fairness provided by the fair exchange scheme without the need to interact with the arbitrator for registration.
The rest of this paper is organized as follows. In section II, we review formal models of ID-based fair exchange schemes. In section III, we design an RSA-based optimistic fair exchange scheme in an ID-based setting. We prove the multiuser security of the scheme in section IV. Finally, section V concludes this paper.
II. Formal Models for ID-Based Fair Exchange Schemes
- 1. Formal Description
ID-based optimistic fair exchange schemes are composed with the following algorithms:
Setup
KIS
(
k
): This algorithm, when given the security parameter
k
, generates a public-private key pair (
pkk
,
skk
), where
skk
is the private key corresponding to
pkk
and is issued by KIS.
Setup
Arb
(
k
): Given the security parameter
k
, the algorithm generates a public-private key pair (
pka
,
ska
) for an arbitrator Arb.
Ext(
pkk
,
skk
,
id
): The algorithm generates the private signing key
sk
for an identity
id
. The identity
id
is used as a public key.
Sig(
id
,
sk
,
pkk
,
pka
,
m
): The algorithm produces a full signature σ on a message
m
in the message space
M
. This algorithm can be probabilistic.
Vfy(
id
,
pkk
,
pka
,
σ
,
m
): The algorithm checks the validity of given signature
σ
. If
σ
is a valid signature on
m
, then the algorithm returns
T
; otherwise
F
.
PSig(
id
,
sk
,
pkk
,
pka
,
m
)$: The algorithm produces a partial signature
ω
on a message
m
in
M
. The algorithm can be probabilistic.
PVfy(
id
,
pkk
,
pka
,
ω
,
m
): The algorithm checks the validity of given partial signature
ω
on
m
. If
ω
is valid, then the algorithm returns
T
; otherwise
F
.
Open(
id
,
pkk
,
pka
,
ska
,
ω
,
m
): Given a partial signature
ω
on a message
m
, the algorithm extracts the full signature
σ
from
ω
.
A fair exchange protocol requires two properties: correctness and ambiguity. Let
ω
= PSig(
id
,
sk
,
pkk
,
pka
,
m
) be a partial signature and
σ
= Sig(
id
,
sk
,
pkk
,
pka
,
m
) be a full signature of a message
m
of a user U whose identity is
id
. The correctness property requires the following conditions:
-
(1) PVfy(id,pkk,pka,ω,m) =T,
-
(2) Vfy(id,pkk,pka,σ,m) =T,
-
(3) Vfy(id,pkk,pka,σ',m) =T,
where
σ'
= Open(
id
,
pkk
,
pka
,
ska
,
ω
,
m
), which is a full signature opened by the algorithm Open upon receiving the partial signature
ω
. If Open is a deterministic algorithm, then
σ'
=
σ
; otherwise (that is, if Open is a probabilistic algorithm)
σ'
could differ from
σ
. The ambiguity property requires that
σ'
and
σ
are computationally indistinguishable. To measure the ambiguity, it suffices to show that any full signature can be generated by both the signing algorithm “Sig” and the opening algorithm Open.
- 2. Security Models
We review the security notions for ID-based fair exchange schemes introduced by Zhang and others
[28]
and rearrange them to give the notions as definitions. Note that the basic concept for the security notions in
[28]
is not changed.
A secure fair exchange scheme should be secure against malicious signers, verifiers, and an arbitrator. To be secure against malicious signers, it is a necessary requirement that a signer should not be allowed to generate a valid partial signature that cannot then be converted to a full signature. A full-partial signature pair is called unfair if the partial signature is valid but the full signature is not.
Definition 1.
Security against signers.
Given an adversary algorithm, say
A
, the advantage of the algorithm
A
is defined as follows:
where
OE
and
OO
are oracles that respond to extraction and opening queries asked by
A
, respectively. The set of all identities is denoted by
I
. The partial signature of a message
m
is denoted by
ω
, with
σ
being the corresponding full signature. An ID-based fair exchange is said to be secure against malicious signers if for any
A
, its advantage Adv
A
SIG
(
k
) is negligible.
For security against verifiers, it is a requirement that no one be allowed to generate a full signature from a partial signature without asking the arbitrator to open it.
Definition 2.
Security against verifiers.
The advantage of
A
in computing a full signature from a partial signature, whose full signature was not generated by an opening oracle, is defined as follows:
where
OE
,
OP
and
OO
are oracles that respond to extraction, partial signing, and opening queries asked by
A
, respectively. We assume that
A
cannot obtain the private key of the target user. In other words, it is assumed that the private key of the identity
id
was not returned by oracle
OE
. The set of all identities is denoted by
I
, the set of message/signature pairs generated by
OP
is denoted by
LP
, and the set of all message/signature pairs opened by
OO
is denoted by
LF
. An ID-based fair exchange is secure against malicious verifiers if for any
A
, its advantage Adv
A
VFY
(
k
) is negligible.
For security against an arbitrator, it is a requirement that no single arbitrator be allowed to generate a valid full signature whose partial signature was not generated by a partial signing oracle. Similar to the ordinary notions of unforgeability, we consider the existential unforgedability under adaptive chosen message attacks, which is regarded as a standard security notion for signature schemes.
Definition 3.
Security against arbitrators.
The advantage of an adversary
A
in existentially forging a full signature whose partial signature was not generated by a partial signing oracle is defined as follows:
where
OE
and
OP
are respectively oracles that respond to the extraction and partial signing queries asked by
A
. We assume that the adversary
A
cannot obtain the private key of the target user. In other words, it is assumed that the private key of the identity
id
was not returned by the oracle
OE
. The set of all identities is denoted by
I
. Let
σ
be the full signature of
ω
on the message
m
, and let
L
be the set of signature/message pairs that are generated by
OP
. An ID-based fair exchange is secure against a malicious arbitrator
A
if its advantage Adv
A
ARB
(
k
) is negligible.
III. ID-Based Optimistic Fair Exchange Schemes
In this section, we propose an identity-based optimistic fair exchange (ID-OFE) based on the identity-based signature proposed by Guillou and Quisquater (GQ-IBS)
[23]
,
[31]
and the standard RSA function proposed by Rivest, Shamir and Adleman
[32]
.
- 1. Scheme
In our scheme, we assume the existence of two trusted entities. One is the trusted KIS that issues the secret key for a user, and the other is the arbitrator Arb that lends support in resolving disputes between clients. Since KIS and Arb are trusted entities, such as a certificate authority is in a PKI, we can use their public keys without certificates as such information can be regarded as a system parameter. In what follows, we denote
idi
to be the corresponding identity of user U
i
.
SetupKIS.
KIS chooses a safe RSA modulus
nk
=
pkqk
and a prime
ek
such that
gcd
(
ek
,
ϕ
(
nk
)) = 1, where
ϕ
is Euler’s totient function, and computes
dk
=
ek
–1
mod
ϕ
(
nk
). The public key is {
nk
,
ek
}, and the private key is
dk
. The hash function
I
maps identity information to an element of
Znk
*
, and the hash function
h
maps a string of arbitrary length to an
ℓh
-bit string.
SetupArb.
Arb chooses a safe RSA modulus
na
=
paqa
and a prime exponent
ea
that satisfies
gcd
(
ea
,
ϕ
(
na
)) = 1. It then computes
da
=
ea
–1
mod
ϕ
(
na
). The public key is {
na
,
ea
}, and the private key is
da
. The hash function that maps a string of arbitrary length to an element of
Zna
*
is denoted by
H
.
Ext.
When a user U
i
requests their private key, the key-issuing server computes
Ii
=
I
(
idi
) and
ski
=
Ii
dk
mod
nk
and then sends
ski
to U
i
in a secure way. User U
i
can verify the correctness of a given private key by checking
ski
ek
=
I
(
idi
)
mod
nk
.
PSig and Sig.
To make a signature of a message
m
, U
i
chooses three random values
a
(in
Zna
*
),
a
* (in {0, 1}
ℓh
), and
r
(in
Znk
*
) and then computes
t
=
rek
mod nk
,
ae
=
H
(
m
||
a
*||
t
) ·
aea
mod
na
,
c
=
h
(
m
||
ae
||
t
), and
b
=
r
·
ski
c
mod
nk
. Then, the partial signature and the full signature on
m
are (
ae
,
b
,
c
) and (
a
,
a
*,
b
,
c
), respectively. Note that two values,
m
and
t
, are used for computing
ae
and
c
. We repeatedly use the same inputs to give a way to manage random oracles in Theorem 1. Note that in PSig and Sig, two values, (
m
and
t
), are repeatedly used for computing
ae
and
c
to simulate random oracles in the proof of Theorem 1. In the theorem, we can correctly respond to queries on random oracles due to the fact that the same input values are used for generating different messages.
Pvfy.
For a given artial signature (
ae
,
b
,
c
) on
m
, a verifier computes
t'
=
bek
·
I
(
idi
)
–c mod nk
. Then, the signature is valid only if the following condition holds:
h
(
m
||(
ae
||
t'
) =
c
.
Vfy.
Given a full signature (
a
,
a
*,
b
,
c
) on a message
m
, a verifier computes
t'
=
bek
·
I
(
idi
)
–c mod nk
and
ae'
=
H
(
m
||
a*
||
t'
) ·
aea
mod
na
. The signature is then valid only if the following condition holds:
h
(
m
||
ae'
||
t'
)=
c
.
Open.
When a partial signature (
ae
,
b
,
c
) generated by U
i
on a message
m
is given, the arbitrator Arb verifies the following condition:
h
(
m
||(
ae
||
t'
) =
c
, where
t'
=
bek
·
I
(
idi
)
–c mod nk
. If the condition holds, Arb chooses a random
a
*
'
in {0,1}
ℓh
and recovers
a'
by computing
a'
= (
ae
/
H
(
m
||
a
*
'
||
t'
))
da
mod
na
. The opened full signature is then (
a'
,
a
*
'
,
b
,
c
).
Note that in the opening algorithm Open the two equations
a
=
a'
and
a
*=
a
*
'
are not always guaranteed, which means that the opened full signature is not always the same as the full signature generated by Sig. In other words, a partial signature can be opened to more than one full signature since there are several pairs (
u
,
v
) satisfying
ae
=
H
(
m
||
v
||
t
) ·
uea mod na
. Therefore, when a dispute occurs, the role of the arbitrator is to find a pair (
a'
,
a
*
'
) such that
ae
=
H
(
m
||
a
*
'
||
t
) ·
a'
ea
mod
na
instead of recovering the fixed pair (
a
,
a
*). Note that this property does not have any influence upon the security of the fair exchange scheme. Note that the scheme in
[9]
also has the same property and that this did not influence the security of their fair exchange scheme; a fact that has been indicated in
[20]
. From now on, we do not distinguish between the full signatures generated by Sig and the full signatures generated by Open.
It is easy to show that the proposed scheme achieves the required level of correctness. Let
ω
= (
ae
,
b
,
c
) be a partial signature on a message
m
of a user U
i
(whose identity is
idi
), and let
σ
= (
a
,
a
*,
b
,
c
) be a full signature for the partial signature. Recall that, as we discussed in section II.1, a fair exchange scheme has to satisfy three conditions for correctness. The proposed scheme achieves correctness since it satisfies the following conditions:
-
Condition (1), (2): The full signature σ is correctly verified since
t' = bek · I(idi) –c = rek= t mod nk
and
ae'=H(m||a*||t) · aea=ae mod na
For the same reason, the partial signature
ω
is also verified correctly.
-
Condition (3): A valid full signatureσis always recoverable from the partial signature since the RSA function is bijective.
As we briefly stated in section II.1, we can measure the ambiguity of a fair exchange scheme by showing that any full signature can be generated either by the signing algorithm Sig or by the opening algorithm Open. In the proposed scheme, any correctly generated partial signature (
ae
,
b
,
c
), whose full signature is (
a
,
a
*,
b
,
c
), can be transformed to a full signature by opening
a'
and
a
*
'
such that
ae
=
H
(
m
||
a
*
'
||
t'
) ·
a'
ea
mod na
, where
t'
=
bek
·
I
(
idi
)
–c · mod nk
. The opening algorithm can generate a full signature that is identical to the full signature generated by the signer when the algorithm uses the same
a
* (that is,
a
*=
a
*
'
). Therefore, the scheme achieves the ambiguity.
- 2. Performance
Recall that the goal of this paper is to construct an ID-based optimistic fair exchange scheme using the RSA function and that the scheme in
[20]
is the only known ID-based optimistic fair exchange scheme that is designed based on the RSA function. Hence, to demonstrate the strongpoints of our scheme, we compare our scheme with the previously proposed scheme in terms of security and computational complexity.
Security:
The scheme in
[20]
is designed based on the GQ-IBS scheme, as is our scheme, but the two schemes provide different levels of security. First of all, the security proof given in
[20]
does not follow well-formalized security models. In particular, the security proof does not take into account an adversary capable of obtaining multiple valid private keys. Note that this security feature is one of the fundamental requirements of ID-based schemes; thus, we can say that the scheme in
[20]
fails to provide sufficient (provable) security. Moreover, in
[20]
, one trusted party performs two sensitive roles — that of the key-issuing server and that of the arbitrator. For stronger security, it is desirable to separate sensitive roles. For this reason, recently formalized security models separate the role of the key-issuing server and the arbitrator. Therefore, our scheme provides stronger security features than the scheme in
[20]
.
Computational Complexity:
The computation costs of the proposed scheme and the scheme in
[20]
are essentially identical, with insignificant differences due to the structural similarity of the two schemes. Hence, we did not compare their efficiency. The proposed ID-OFE is practical in terms of computational complexity. For each signing and verification, we need three exponentiations. Note that the cost of partial signing is identical to the cost of full signing. We can efficiently compute one exponentiation with
ea
by using short RSA exponents such as 3 and 2
16
+1. The size of the exponent determines the cost of exponentiation, so the cost of exponentiation with
ea
is not a heavy one. Hence, the computational cost of our scheme is comparable to that of the GQ-IBS scheme. When
ea
=3, we need two additional multiplications for signing and verification compared with the GQ-IBS scheme. The lengths of a partial signature and a full signature are 2
ℓn
+
ℓh
and 2
ℓn
+2
ℓh
, respectively, where
ℓn
=|
nk
|=|
na
|. In practice, we used
ℓn
=1,024 and
ℓh
=160 for 1,024-bit RSA modulus.
Additional Useful Properties:
The proposed scheme has some desirable properties, including setup-freeness and convenience in development. Since the scheme is setup-free, no interaction with an arbitrator is necessary. A user should interact with the KIS to obtain a private signing key, but the user still does not interact with the arbitrating server. Our scheme is designed by combining the RSA function and GQ signature scheme, and the GQ signature can be implemented by using the RSA function. Due to the simplicity of the RSA function, the proposed scheme is suitable for cryptographic engineering practices.
IV. Security
Prior to proving the security of the proposed ID-OFE scheme, we review the RSA problem that guarantees the security of our scheme.
Definition 4.
For a given (
N
,
E
,
C
), the RSA problem is to find the
E
th root of
C
under the modulus
N
.
In this paper, we consider the case where the public exponent
E
is a prime number. Note that the RSA problem is still secure even though the public exponent is a prime number.
From now on, we prove the security of the proposed ID-OFE scheme under the hardness of the RSA problem in the random oracle model. We want to emphasis that the security of our scheme is proved in the multi-user setting, where an adversary can make oracle queries for any users including the target victim user. Roughly speaking, in the security proof, oracle queries are not restricted to the target victim user; thus, the security proof is valid in the multi-user setting.
Theorem 1.
The proposed ID-OFE scheme is secure under the security notions described in section II.2 if the RSA assumption holds and the advantage of an adversary who breaks the security of our scheme is bounded by
εRSA
+
ε
(
k
), where
εRSA
is the maximum advantage of polynomial time adversaries who break the RSA problem and
ε
(
k
) is a negligible function.
Proof.
Since we prove the security of our scheme in the random oracle model, we have control over all hash function outputs. For each hash function we maintain a list that stores previous queries; thus, we can respond to a hash query in a previously asked message by retrieving stored data. □
Security against signers:
Let (
ae
,
b
,
c
) be a partial signature on a message m generated by a user U
i
whose hashed identity is
Ii
=
I
(
idi
). If the given partial signature is valid, then we have the following relation:
h(m||ae||t) = c,
where
t
=
bek
·
Ii –c mod nk
. Since the RSA encryption is bijective, for any integer
a
* in {0, 1}
ℓh
, we can compute the element
a
in
Zna
as
a = (ae/H(m||a*||t))da mod na,
and the values
a
and
a
* satisfy the following condition:
ae = H(m||a*||t) · aea mod na.
Hence, (
a
,
a
*,
b
,
c
) is a valid full signature for the given partial signature. Therefore, all valid partial signatures can be transformed to a valid full signature, so the proposed scheme is unconditionally secure against malicious signers.
Security against Verifiers:
Let (
N
,
E
,
C
) be a given challenge to the RSA problem. Recall that the goal is to compute the
E
th root of
C
under the modulus
N
. Let
A
be an algorithm that generates the full signature from a partial signature that was generated by a partial signing oracle, but which has not yet been opened by the opening oracle. To prove security against verifiers, we solve the RSA problem by using the algorithm
A
. To simulate the attack environment, we choose a safe RSA moduli
nk
and a prime
ek
such that
gcd
(
ϕ
(
nk
),
ek
) = 1, and set (
nk
,
ek
) and (
N
,
E
) as the public key for KIS and Arb, respectively. We denote
na
=
N
and
ea
=
E
. We know
ϕ
(
nk
) — the secret key of KIS. Throughout the proof, we use a security parameter
ℓ
to simulate random oracles. The size of the parameters is chosen so that the distribution of
gi
mod
nj
is statistically uniform over
Znj
* for any generator
g
in
Znj
,
i
in {0, 1}
ℓ
, and
j
in {
a
,
k
}. We maintain four lists
LI
,
Lh
,
LH
, and
L
PSig
for the three hash functions
I
,
h
, and
H
and for the partial-signing queries PSig, respectively. We respond to each query asked by the algorithm
A
as follows:
Hash Query for I:
We respond to the query for
idi
by choosing a random
Ii
, which is then given to
A
. We store (
idi
,
Ii
) in
LI
, which contains previous queries.
Hash Query for h:
For the hash query on (
m
,
ae
,
t
), we choose a random c and give it to
A
as the hash value such that
h
(
m
||
ae
||
t
) =
c
. We store (
m
,
ae
,
t
,
c
) in
Lh
.
Hash Query for H:
We respond to a hash query on (
m
,
a
*,
t
) as follows. If there is a tuple (
m
, •,
t
, •, •) in
LH
, we retrieve {(
ae
,
b
,
c
), (
m
,
t
),
δ
} in
L
PSig
, choose a random
ζ
in {0,1}
ℓ
such that
gcd
(
δ
–
ζ
,
ea
) = 1, compute
γ
=
Cζ
mod
na
, give
γ
to the adversary
A
, and store (
m
,
a
*,
t
,
γ
,
ζ
) in
LH
. Otherwise, we choose a random
γ
, give it to
A
, and store (
m
,
a
*,
t
,
γ
, 0) in
LH
.
Extraction Query:
For the extraction query on an identity idi, we retrieve (
idi
,
Ii
) from
LI
, compute
ski
=
Ii
dk
mod nk
, and then give the result to
A
. Recall that we did not consider the case where
idi
is the identity of the target user (victim).
Partial Signing Query:
To respond to a partial signing query on a message
m
of a user U
i
, we choose five random values
a
* in {0, 1}
ℓh
,
δ
in {0, 1}
ℓ
,
ζ
in {0,1}
ℓ
,
r
in
Znk
*, and
c
in {0, 1}
ℓh
such that
gcd
(
δ
–
ζ
,
ea
) = 1, compute
t
=
rek
mod nk
,
b
=
r
·
ski
c mod nk
,
γ
=
Cζ
mod na
, and
ae
=
Cδ
mod na
and set
H
(
m
||
a
*||
t
) =
γ
and
h
(
m
||
ae
||
t
) =
c
. Since the following relation holds, (
ae
,
b
,
c
) is a valid partial signature on
m
:
bek
·
Ii
–c
=(
rek
·
Ii
c
) ·
Ii
–c
=
rek
=
t mod nk
. We store {(
ae
,
b
,
c
), (
m
,
t
),
δ
} in
L
PSig
. We also store (
m
,
a
*,
t
,
γ
,
ζ
) in
LH
.
Full Signing Query:
When the algorithm
A
requests a full signing query on a message
m
of a user U
i
, we compute a full signature (
a
,
a
*,
b
,
c
) according to the description of the ID-OFE scheme. Since we know the private key of KIS, the fullsigning query can be successfully simulated.
Opening Query:
We respond to an opening query on a partial signature (
ae
,
b
,
c
) of
m
as follows. First, we compute
γ
=
ae
ea · η+1
mod na
and
a
=
ae–η mod na
for a randomly chosen integer
η
in {0, 1}
ℓ
. Then, we set
H
(
m
||
a
*||
t
) =
γ
for a randomly chosen
a
* in {0, 1}
ℓh
, store (
m
,
a
*,
t
,
γ
, 0) in
LH
, and then give (
a
,
a
*,
b
,
c
) to the adversary as the full signature of the given partial signature. We have
H
(
m
||
a
*||
t
) ·
aea
=
ae
ea· η+1
·
ae
-ea· η
=
ae
mod na
, so (
a
,
a
*,
b
,
c
) is a valid full signature of the given partial signature.
Let(
a
,
a
*,
b
,
c
) be a full signature of a partial signature (
ae
,
b
,
c
) on a message
m
of a user U
i
, which is returned by the adversary algorithm
A
. The partial signature(
ae
,
b
,
c
) was generated by a partial signing oracle but not opened by the opening oracle.
Since (
ae
,
b
,
c
) is a valid partial signature that was generated by a partial signing oracle, we have the following:
t
=
bek
·
I
(
idi
)
–c
mod
nk
and
h
(
m
||
ae
||
t
) =
c
, and {(
ae
,
b
,
c
), (
m
,
t
),
δ
} and (
m
,
a
*,
t
,
γ
,
ζ
) are stored in
L
PSig
and
LH
, respectively. Hence, we have
Cδ = ae = H(m||a*||t) · aea = Cδ· aea mod na.
From the above equation, we have
A = (Cδ · C–ζ)da = Cda(δ–ζ) mod na.
Since the two values
δ
and
ζ
satisfy
gcd
(
δ
–
ζ
,
ea
) = 1, we can find two integers,
μ
and
ν
, such that
μ
·(
δ
–
ζ
)+
ν
·
ea
=1 by performing the extended Euclidean algorithm. Then, using these values, we can recover the
ea
th root (
E
th root) of
C
by computing
aμ·Cν=Cda(μ·(δ – ζ)) · Cda ·ν·ea = Cda mod na.
Then, we can solve the RSA problem with advantage
ε
if the advantage of algorithm
A
is
ε
; thus,
ε
<
εRSA
, where
εRSA
is the maximum advantage of polynomial time adversaries that break the RSA problem. Therefore, the ID-OFE scheme is secure against verifiers if the RSA problem is intractable.
Security against the arbitrator:
To prove unforgeability, we forge a signature of the GQ-IBS scheme by using an algorithm
A
that breaks the unforgeability of the proposed ID-OFE scheme. Let (
N
,
E
) be a set of parameters for GQ-IBS given as a challenge. We set
nk
=
N
and
ek
=
E
. We can access the two hash oracles
OI
GQ
and
Oh
GQ
, an extraction oracle
O
Ext
GQ
and a signing oracle
O
Sig
GQ
. A malicious arbitrator can open any partial signature; hence, we did not provide the opening oracle. We maintain two lists,
LH
and
L
Sig
, for hash queries for
H
and for signing queries, respectively. We respond to
A
’s queries as follows.
Hash Query for I:
For a given hash query on an identity
idi
, we make a hash query on the identity to hash oracle
OI
GQ
. Let
Ii
be the answer returned by the oracle. We give
Ii
to
A
.
Hash Query for h:
When
A
asks a hash query on a pair (
m
,
ae
,
t
), we make a hash query for (
m'
,
t
) to hash oracle
Oh
GQ
where
m'
=
m
||
ae
. Let
c
be the answer returned by
Oh
GQ
. We then give
c
to
A
.
Hash Query for H:
For a given hash query for (
m
,
a
*,
t
) we choose a random
γ
, we then give it to algorithm
A
who then stores (
m
,
a
*,
t
,
γ
) in
LH
.
Extraction Query:
For a given extraction query for an identity
idi
, we make an extraction query to
O
Ext
GQ
for the identity. We give the answer ski, returned by the oracle
O
Ext
GQ
, to the algorithm
A
. Recall that we did not consider the case where
idi
is the identity of the target user (victim).
Partial/full Signing Query:
When algorithm
A
makes a signing query on a message
m
of a user U
i
, we respond to the query as follows. We choose a random value
ae
in
Zna
* and make a singing query on
m'
=
m
||
ae
to the signing oracle
O
Sig
GQ
. Let (
b
,
c
) be the signature of
m'
answered by
O
Sig
GQ
. Then, we choose two random values,
a
in
Zna
* and
a
* in {0, 1}
ℓh
, and then compute the following:
t = bek · Ii –c mod nk
and
γ = ae/ aea mod na.
We set
H
(
m
||
a
*||
t
) =
γ
and store (
m
,
a
*,
t
,
γ
) and (
m
,
a
,
a
*,
b
,
c
) in
LH
and
L
Sig
, respectively. For a partial signing query, we give (
ae
,
b
,
c
) to algorithm
A
. For a full signing query, we give (
a
,
a
*,
b
,
c
) to algorithm
A
.
Algorithm
A
may return a signature ((
a
,
a
*,
b
,
c
)) on a message (
m
) whose partial signature was not generated by any oracle. Note that since the arbitrator can open a partial signature to a full signature, we exclude the case where the adversary obtains the full signature by opening a partial signature that was generated by an oracle. We return (
b
,
c
) as a forgery on the message
m'
, where
t
=
bek
·
I
(
idi
)
–c mod nk
,
ae
=
H
(
m
||
a
*||
t
), and
m'
=
m
||
ae
. If the forged signature returned by the algorithm
A
is valid, then we have
h
(
m
||
ae
||
t
) =
c
. Hence, (
b
,
c
) is a valid signature of the GQ-IBS scheme since the following relation holds:
h
(
m'
||
t
) =
c
, where
m'
=
m
||
ae
. Therefore, the unforgeability of the ID-OFE scheme is reduced to the security of the GQ-IBS scheme. Let
ε
be the advantage of the algorithm
A
. Then, we can break the GQ-IBS scheme with advantage
ε
, so
ε
<
εGQ-IBS
, where
εGQ-IBS
is the maximum advantage of polynomial time adversaries that break the security of the GQ-IBS scheme. Since the security of the GQ-IBS scheme is reduced to the hardness of the RSA problem
[33]
–
[34]
we have
εGQ-IBS
≈
εRSA
+
ε
(
k
) for a negligible function
ε
(
k
). Hence,
ε
<
εRSA
+
ε
(
k
).
V. Conclusion
In this paper, we propose an efficient ID-based optimistic fair exchange based on the RSA function. From a theoretical point of view, the proposed scheme is the first provably secure ID-based fair exchange scheme based on the RSA function whose security can be proved under fully formalized security models. Note that the theoretical contribution is the main contribution of this paper. The proposed scheme has the following additional strongpoints. The scheme is suitable for cryptographic engineering practices due to the simplicity of the RSA function. The scheme is setup-free; therefore, the arbitrator participates in the protocol execution only if there is a dispute between the two parties. Moreover, the proposed fair exchange scheme is designed in an ID-based setting; hence, it is possible to eliminate the need for certificates and avoid some related problems.
This research was supported by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (Grant No. 2011-0029925).
BIO
Taek-Young Youn received his PhD degree in cryptography from Korea University, Seoul, Rep. of Korea in 2009. He was working as a postdoctoral researcher at the Graduate School of Information Management and Security, Korea University, Seoul, Rep. of Korea, from September 2009 to June 2010. He is now a researcher at the Electronics and Telecommunications Research Institute, Daejeon, Rep. of Korea. His research interests include information security, public key cryptosystems, and cryptographic protocol.
Ku-Young Chang received his BS, MS and PhD degrees in mathematics from Korea University, Seoul, Rep. of Korea, in 1995, 1997, and 2000, respectively. He is currently a principal researcher in the Cryptography Research Section at ETRI, Daejeon, Rep. of Korea. His research interests include cryptography, data privacy, and architectures for computations in finite fields.
Asokan N.
,
Shoup V.
,
Waidner M.
1998
“Optimistic Fair Exchange of Digital Signatures,”
Springer-Verlag
Berlin
EUROCRYPT LNCS
1403
591 -
606
DOI : 10.1007/BFb0054156
Asokan N.
,
Shoup V.
,
Waidner M.
2000
“Optimistic Fair Exchange of Digital Signatures,”
IEEE J. Sel. Areas Commun.
18
(4)
593 -
610
DOI : 10.1109/49.839935
Boneh D.
2003
“Aggregate and Verifiably Encrypted Signatures from Bilinear Maps,”
Springer-Verlag
Berlin
EUROCRYPT LNCS
2656
416 -
432
DOI : 10.1007/3-540-39200-9_26
Camenisch J.
,
Damgárd I.
2000
“Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes,”
Springer-Verlag
Berlin
ASIACRYPT LNCS
1976
331 -
345
DOI : 10.1007/3-540-44448-3_25
Dodis Y.
,
Reyzin L.
2003
“Breaking and Repairing Optimistic Fair Exchange from PODC 2003,”
ACM Press
New York
ACM Workshop DRM
47 -
54
DOI : 10.1145/947380.947387
Huang X.
2011
“Optimistic Fair Exchange with Strong Resolution-Ambiguity,”
IEEE J. Sel. Areas Commun.
29
(7)
1491 -
1502
DOI : 10.1109/JSAC.2011.110814
Huang Q.
,
Wong D.S.
,
Susilo W.
2010
“A New Construction of Designated Confirmer Signature and its Application to Optimistic Fair Exchange,”
Springer-Verlag
Berlin
Pairing LNCS
6487
41 -
61
DOI : 10.1007/978-3-642-17455-1_4
Park J.M.
,
Chong E.K.P.
,
Siegel H.J.
2003
“Constructing Fair- Exchange Protocols for E-Commerce via Distributed Computation of RSA Signatures,”
PODC
ACM Press
New York
172 -
181
DOI : 10.1145/872035.872060
Yum D.H.
,
Lee P.J.
2008
“Efficient Fair Exchange from Identity- Based Signature,”
IEICE Trans. Fundamentals
E91-A
(1)
119 -
126
Zhu H.
,
Bao F.
2006
“More on Stand-Alone and Setup-Free Verifiably Committed Signatures,”
Springer-Verlag
Berlin
ACISP LNCS
4058
148 -
158
DOI : 10.1007/11780656_13
Zhu H.
,
Bao F.
2006
“Stand-Alone and Setup-Free Verifiably Committed Signatures,”
Springer-Verlag
Berlin
CT-RSA LNCS
3860
159 -
173
DOI : 10.1007/11605805_11
Zhu H.
,
Susilo W.
,
Mu Y.
2007
“Multi-party Stand-Alone and Setup-Free Verifiably Committed Signatures,”
Springer-Verlag
Berlin
PKC LNCS
4450
134 -
149
DOI : 10.1007/978-3-540-71677-8_10
Zhang L.
,
Wu Q.
,
Qin B.
2013
“Identity-Based Optimistic Fair Exchange in the Standard Model,”
Security Commun. Netw.
6
(8)
1010 -
1020
DOI : 10.1002/sec.652
Markowitch O.
,
Saeednia S.
2002
“Optimistic Fair Exchange with Transparent Signature Recovery,”
Springer-Verlag
Berlin
FC LNCS
2339
339 -
350
DOI : 10.1007/3-540-46088-8_26
Cathalo J.
,
Libert B.
,
Quisquater J.-J.
2004
“Cryptanalysis of a Verifiably Committed Signature Scheme Based on GPS and RSA,”
Springer-Verlag
Berlin
LNCS
3225
52 -
60
DOI : 10.1007/978-3-540-30144-8_5
Zhang Z.
,
Feng D.
2003
“Simple Fair Exchange Based Mediated- RSA and Factoring Representation,”
WISA
Jeju Island, Rep. of Korea
689 -
696
Ding X.
,
Tsudik G.
2003
“Simple Identity-Based Cryptography with Mediated RSA,”
Springer-Verlag
Berlin
CT-RSA LNCS
2612
193 -
210
DOI : 10.1007/3-540-36563-X_13
Ateniese G.
1999
“Efficient Verifiable Encryption (and Fair Exchange) of Digital Signatures,”
ACM Conf. Comput. Commun. Security
138 -
146
DOI : 10.1145/319709.319728
Saeednia S.
,
Markowitch O.
,
Roggeman Y.
“Identity-Based Optimistic Fair Exchange with Transparent Signature Recovery,”
CANS
http://www.ulb.ac.be/di/scsi/markowitch/publications/dms03.pdf
Dodis Y.
,
Lee P.J.
,
Yum D.H.
2007
“Optimistic Fair Exchange in a Multi-user Setting,”
Springer-Verlag
Berlin
PKC LNCS
4450
118 -
133
DOI : 10.1007/978-3-540-71677-8_9
Huang Q.
2008
“Efficient Optimistic Fair Exchange Secure in the Multi-user Setting and Chosen-Key Model without Random Oracles,”
Springer-Verlag
Berlin
CT-RSA LNCS
4964
106 -
120
DOI : 10.1007/978-3-540-79263-5_7
Guillou L.C.
,
Quisquater J.-J.
1988
“A Paradoxical Indentity-Based Signature Scheme Resulting from Zero-Knowledge,”
Springer-Verlag
Berlin
CRYPTO LNCS
403
216 -
231
Shamir A.
1985
“Identity Based Cryptosystems and Signature Schemes,”
Springer-Verlag
Berlin
Cryptology LNCS
196
47 -
53
DOI : 10.1007/3-540-39568-7_5
Boneh D.
,
Franklin M.
2001
“Identity-Based Encryption from the Weil Pairing,”
Springer-Verlag
Berlin
CRYPTO LNCS
2139
213 -
229
Gu C.
,
Zhu Y.
,
Zhang Y.
2005
“An ID-Based Optimistic Fair Signature Exchange Protocol from Pairings,”
Springer-Verlag
Berlin
CIS LNCS
3802
9 -
16
DOI : 10.1007/11596981_2
Zhang Z.
2005
“Efficient ID-Based Optimistic Fair Exchange with Provable Security,”
Springer-Verlag
Berlin
ICICS LNCS
3783
14 -
26
DOI : 10.1007/11602897_2
Zhang L.
,
Wu Q.
,
Hu Y.
2012
“Hierarchical Identity-Based Encryption with Constant-Size Private Keys,”
ETRI J.
34
(1)
142 -
145
DOI : 10.4218/etrij.12.0211.0140
L.C. Guillou
,
Quisquater J.-J.
1988
“A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing both Trasmission and Memory,”
Springer-Verlag
Berlin
EUROCRYPT LNCS
330
123 -
128
DOI : 10.1007/3-540-45961-8_11
Rivest R.L.
,
Shamir A.
,
Adleman L.M.
1978
“A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,”
ACM
21
(2)
120 -
126
DOI : 10.1145/359340.359342
Bellare M.
2004
“Security Proofs for Identity-Based Identification and Signature Schemes,”
Springer-Verlag
Berlin
EUROCRYPT LNCS
3027
268 -
286
DOI : 10.1007/s00145-008-9028-8