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. 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. 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. 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 ( pk_k , sk_k ), where sk_k is the private key corresponding to pk_k and is issued by KIS. Setup ^Arb ( k ): Given the security parameter k , the algorithm generates a public-private key pair ( pk_a , sk_a ) for an arbitrator Arb. Ext( pk_k , sk_k , 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 , pk_k , pk_a , m ): The algorithm produces a full signature σ on a message m in the message space M . This algorithm can be probabilistic. Vfy( id , pk_k , pk_a , σ , 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 , pk_k , pk_a , m )$: The algorithm produces a partial signature ω on a message m in M . The algorithm can be probabilistic. PVfy( id , pk_k , pk_a , ω , m ): The algorithm checks the validity of given partial signature ω on m . If ω is valid, then the algorithm returns T ; otherwise F . Open( id , pk_k , pk_a , sk_a , ω , 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 , pk_k , pk_a , m ) be a partial signature and σ = Sig( id , sk , pk_k , pk_a , m ) be a full signature of a message m of a user U whose identity is id . The correctness property requires the following conditions: where σ' = Open( id , pk_k , pk_a , sk_a , ω , 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. 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: $${\text{Adv}}_A^{\text{SIG}}(k)=\mathrm{Pr}\left[\begin{array}{l}\text{PVfy}(id,p{k}_k,p{k}_a,\omega ,m)=T\\ \text{and Vfy}(id\text{,}p{k}_k\text{,}p{k}_a\text{,}\sigma ,m)\hspace{0.17em}\text{=\hspace{0.17em}}\mathrm{F:}\\ (p{k}_k,s{k}_k)\leftarrow {\text{Setup}}^{\text{KIS}}(k),\\ (p{k}_a,s{k}_a)\leftarrow {\text{Setup}}^{\text{Arb}}(k),\\ (id,\omega ,m)\leftarrow A^{O_E,O_O}(I,p{k}_a,s{k}_a),\\ \sigma \leftarrow \text{Open(}id\text{,}p{k}_k,p{k}_a\text{,}s{k}_a\text{,}\omega ,m\text{)}\end{array}\right],$$ where O_E and O_O 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: $${\text{Adv}}_A^{\text{VFY}}(k)=\mathrm{Pr}\left[\begin{array}{l}\text{Vfy}(id,p{k}_k,p{k}_a,\sigma ,m)=\mathrm{T\hspace{0.17em}}\text{and}\\ (m,\omega )\in L_P\text{\hspace{0.17em}and\hspace{0.17em}}(m\text{,}\sigma \text{)}\notin L_F:\\ (p{k}_k,s{k}_k)\leftarrow {\text{Setup}}^{\text{KIS}}(k),\\ (p{k}_a,s{k}_a)\leftarrow {\text{Setup}}^{\text{Arb}}(k),\\ (id,\sigma ,\omega ,m)\leftarrow A^{O_E,O_P,O_O}(I,p{k}_k,s{k}_a)\end{array}\right],$$ where O_E , O_P and O_O 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 O_E . The set of all identities is denoted by I , the set of message/signature pairs generated by O_P is denoted by L_P , and the set of all message/signature pairs opened by O_O is denoted by L_F . 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: $${\text{Adv}}_A^{\text{ARB}}(k)=\mathrm{Pr}\left[\begin{array}{l}\text{Vfy}(id,p{k}_k,p{k}_a,\sigma ,m)=\mathrm{T\hspace{0.17em}}\\ \text{and\hspace{0.17em}}(\omega ,m)\notin L\text{:}\\ (p{k}_k,s{k}_k)\leftarrow {\text{Setup}}^{\text{KIS}}(k),\\ (p{k}_a,s{k}_a)\leftarrow {\text{Setup}}^{\text{Arb}}(k),\\ (id,\sigma ,m)\leftarrow A^{O_E,O_P}(I,p{k}_k,p{k}_a,s{k}_a)\end{array}\right],$$ where O_E and O_P 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 O_E . 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 O_P . An ID-based fair exchange is secure against a malicious arbitrator A if its advantage Adv _A ^ARB ( k ) is negligible. 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] . 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 id_i to be the corresponding identity of user U _i . Setup^KIS. KIS chooses a safe RSA modulus n_k = p_kq_k and a prime e_k such that gcd ( e_k , ϕ ( n_k )) = 1, where ϕ is Euler’s totient function, and computes d_k = e_k ^–1 mod   ϕ ( n_k ). The public key is { n_k , e_k }, and the private key is d_k . The hash function I maps identity information to an element of Z_nk ^* , and the hash function h maps a string of arbitrary length to an ℓ_h -bit string. Setup^Arb. Arb chooses a safe RSA modulus n_a = p_aq_a and a prime exponent e_a that satisfies gcd ( e_a , ϕ ( n_a )) = 1. It then computes d_a = e_a ^–1 mod   ϕ ( n_a ). The public key is { n_a , e_a }, and the private key is d_a . The hash function that maps a string of arbitrary length to an element of Z_na ^* is denoted by H . Ext. When a user U _i requests their private key, the key-issuing server computes I_i = I ( id_i ) and sk_i = I_i ^dk mod n_k and then sends sk_i to U _i in a secure way. User U _i can verify the correctness of a given private key by checking sk_i ^ek = I ( id_i ) mod n_k . PSig and Sig. To make a signature of a message m , U _i chooses three random values a (in Z_na ^* ), a * (in {0, 1} ^ℓh ), and r (in Z_nk ^* ) and then computes t = r^ek mod n_k , a_e = H ( m || a *|| t ) · a^ea mod   n_a , c = h ( m || a_e || t ), and b = r · sk_i ^c mod n_k . Then, the partial signature and the full signature on m are ( a_e , b , c ) and ( a , a *, b , c ), respectively. Note that two values, m and t , are used for computing a_e 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 a_e 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 ( a_e , b , c ) on m , a verifier computes t' = b^ek · I ( id_i ) ^–c mod n_k . Then, the signature is valid only if the following condition holds: h ( m ||( a_e || t' ) = c . Vfy. Given a full signature ( a , a *, b , c ) on a message m , a verifier computes t' = b^ek · I ( id_i ) ^–c mod n_k and a_e' = H ( m || a* || t' ) · a^ea mod   n_a . The signature is then valid only if the following condition holds: h ( m || a_e' || t' )= c . Open. When a partial signature ( a_e , b , c ) generated by U _i on a message m is given, the arbitrator Arb verifies the following condition: h ( m ||( a_e || t' ) = c , where t' = b^ek · I ( id_i ) ^–c mod n_k . If the condition holds, Arb chooses a random a * ' in {0,1} ^ℓh and recovers a' by computing a' = ( a_e / H ( m || a * ' || t' )) ^da mod   n_a . 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 a_e = H ( m || v || t ) · u^ea mod n_a . Therefore, when a dispute occurs, the role of the arbitrator is to find a pair ( a' , a * ' ) such that a_e = H ( m || a * ' || t ) · a' ^ea mod n_a 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 ω = ( a_e , b , c ) be a partial signature on a message m of a user U _i (whose identity is id_i ), 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: t' = b^ek · I(id_i) ^–c = r^ek= t mod n_k and a_e'=H(m||a*||t) · a^ea=a_e mod n_a For the same reason, the partial signature ω is also verified correctly. 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 ( a_e , b , c ), whose full signature is ( a , a *, b , c ), can be transformed to a full signature by opening a' and a * ' such that a_e = H ( m || a * ' || t' ) · a' ^ea mod n_a , where t' = b^ek · I ( id_i ) ^–c · mod n_k . 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. 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 e_a by using short RSA exponents such as 3 and 2 ¹⁶ +1. The size of the exponent determines the cost of exponentiation, so the cost of exponentiation with e_a is not a heavy one. Hence, the computational cost of our scheme is comparable to that of the GQ-IBS scheme. When e_a =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 =| n_k |=| n_a |. 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. 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 ( a_e , b , c ) be a partial signature on a message m generated by a user U _i whose hashed identity is I_i = I ( id_i ). If the given partial signature is valid, then we have the following relation: h(m||a_e||t) = c, where t = b^ek · I_i ^–c mod n_k . Since the RSA encryption is bijective, for any integer a * in {0, 1} ^ℓh , we can compute the element a in Z_na as a = (a_e/H(m||a*||t))^da mod n_a, and the values a and a * satisfy the following condition: a_e = H(m||a*||t) · a^ea mod n_a. 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 n_k and a prime e_k such that gcd ( ϕ ( n_k ), e_k ) = 1, and set ( n_k , e_k ) and ( N , E ) as the public key for KIS and Arb, respectively. We denote n_a = N and e_a = E . We know ϕ ( n_k ) — 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 gⁱ mod n_j is statistically uniform over Z_nj * for any generator g in Z_nj , i in {0, 1} ^ℓ , and j in { a , k }. We maintain four lists L_I , L_h , L_H , 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 id_i by choosing a random I_i , which is then given to A . We store ( id_i , I_i ) in L_I , which contains previous queries. Hash Query for h: For the hash query on ( m , a_e , t ), we choose a random c and give it to A as the hash value such that h ( m || a_e || t ) = c . We store ( m , a_e , t , c ) in L_h . Hash Query for H: We respond to a hash query on ( m , a *, t ) as follows. If there is a tuple ( m , •, t , •, •) in L_H , we retrieve {( a_e , b , c ), ( m , t ), δ } in L _PSig , choose a random ζ in {0,1} ^ℓ such that gcd ( δ – ζ , e_a ) = 1, compute γ = C^ζ mod   n_a , give γ to the adversary A , and store ( m , a *, t , γ , ζ ) in L_H . Otherwise, we choose a random γ , give it to A , and store ( m , a *, t , γ , 0) in L_H . Extraction Query: For the extraction query on an identity idi, we retrieve ( id_i , I_i ) from L_I , compute sk_i = I_i ^dk mod n_k , and then give the result to A . Recall that we did not consider the case where id_i 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 Z_nk *, and c in {0, 1} ^ℓh such that gcd ( δ – ζ , e_a ) = 1, compute t = r^ek mod n_k , b = r · sk_i ^c mod n_k , γ = C^ζ mod n_a , and a_e = C^δ mod n_a and set H ( m || a *|| t ) = γ and h ( m || a_e || t ) = c . Since the following relation holds, ( a_e , b , c ) is a valid partial signature on m : b^ek · I_i ^–c =( r^ek · I_i ^c ) · I_i ^–c = r^ek = t mod n_k . We store {( a^e , b , c ), ( m , t ), δ } in L _PSig . We also store ( m , a *, t , γ , ζ ) in L_H . 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 ( a_e , b , c ) of m as follows. First, we compute γ = a_e ^{ea · η+1} mod n_a and a = a_e^–η mod n_a 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 L_H , 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 ) · a^ea = a_e ^{ea· η+1} · a_e ^{-ea· η} = a_e mod n_a , 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 ( a_e , b , c ) on a message m of a user U _i , which is returned by the adversary algorithm A . The partial signature( a_e , b , c ) was generated by a partial signing oracle but not opened by the opening oracle. Since ( a_e , b , c ) is a valid partial signature that was generated by a partial signing oracle, we have the following: t = b^ek · I ( id_i ) ^–c mod n_k and h ( m || a_e || t ) = c , and {( a_e , b , c ), ( m , t ), δ } and ( m , a *, t , γ , ζ ) are stored in L _PSig and L_H , respectively. Hence, we have C^δ = a_e = H(m||a*||t) · a^ea = C^δ· a^ea mod n_a. From the above equation, we have A = (C^δ · C^–ζ)^da = C^da(δ–ζ) mod n_a. Since the two values δ and ζ satisfy gcd ( δ – ζ , e_a ) = 1, we can find two integers, μ and ν , such that μ ·( δ – ζ )+ ν · e_a =1 by performing the extended Euclidean algorithm. Then, using these values, we can recover the e_a th root ( E th root) of C by computing a^μ·C^ν=C^{da(μ·(δ – ζ))} · C^{da ·ν·ea} = C^da mod n_a. 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 n_k = N and e_k = E . We can access the two hash oracles O_I ^GQ and O_h ^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, L_H 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 id_i , we make a hash query on the identity to hash oracle O_I ^GQ . Let I_i be the answer returned by the oracle. We give I_i to A . Hash Query for h: When A asks a hash query on a pair ( m , a_e , t ), we make a hash query for ( m' , t ) to hash oracle O_h ^GQ where m' = m || a_e . Let c be the answer returned by O_h ^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 L_H . Extraction Query: For a given extraction query for an identity id_i , 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 id_i 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 a_e in Z_na * and make a singing query on m' = m || a_e 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 Z_na * and a * in {0, 1} ^ℓh , and then compute the following: t = b^ek · I_i ^–c mod n_k and γ = a_e/ a^ea mod n_a. We set H ( m || a *|| t ) = γ and store ( m , a *, t , γ ) and ( m , a , a *, b , c ) in L_H and L _Sig , respectively. For a partial signing query, we give ( a_e , 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 = b^ek · I ( id_i ) ^–c mod n_k , a_e = H ( m || a *|| t ), and m' = m || a_e . If the forged signature returned by the algorithm A is valid, then we have h ( m || a_e || 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 || a_e . 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 ). 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. 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.