Advanced
ID-Based Optimistic Fair Exchange Scheme Based on RSA
ID-Based Optimistic Fair Exchange Scheme Based on RSA
ETRI Journal. 2014. Jun, 36(4): 673-681
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : April 15, 2013
  • Accepted : November 21, 2013
  • Published : June 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Taek-Young Youn
Ku-Young Chang

Abstract
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.
Keywords
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:
Adv A SIG (k)=Pr[ PVfy(id,p k k ,p k a ,ω,m)=T and Vfy(id,p k k ,p k a ,σ,m) = F: (p k k ,s k k ) Setup KIS (k), (p k a ,s k a ) Setup Arb (k), (id,ω,m) A O E , O O (I,p k a ,s k a ), σOpen(id,p k k ,p k a ,s k a ,ω,m) ],
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:
Adv A VFY (k)=Pr[ Vfy(id,p k k ,p k a ,σ,m)=T and (m,ω) L P  and (m,σ) L F : (p k k ,s k k ) Setup KIS (k), (p k a ,s k a ) Setup Arb (k), (id,σ,ω,m) A O E , O P , O O (I,p k k ,s k a ) ],
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:
Adv A ARB (k)=Pr[ Vfy(id,p k k ,p k a ,σ,m)=T  and (ω,m)L: (p k k ,s k k ) Setup KIS (k), (p k a ,s k a ) Setup Arb (k), (id,σ,m) A O E , O P (I,p k k ,p k a ,s k a ) ],
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/ aeamod 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.
References
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
Ateniese G. 2004 “Verifiable Encryption of Digital Signatures and Applications,” ACM TISSEC 7 (1) 1 - 20    DOI : 10.1145/984334.984335
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
Ren X.-Y. , Qi Z.-H. , Geng Y. 2012 “Provably Secure Aggregate Signcryption Scheme,” ETRI J. 34 (3) 421 - 428    DOI : 10.4218/etrij.12.0111.0215
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
Lim S. , Lee H.-S. 2011 “A Short and Efficient Redactable Signature Based on RSA,” ETRI J. 33 (4) 621 - 628    DOI : 10.4218/etrij.11.0110.0530
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
Dodis Y. 2003 “Strong Key-Insulated Signature Schemes,” Springer-Verlag Berlin PKC LNCS 2567 130 - 144    DOI : 10.1007/3-540-36288-6_10