Health Articles

 

Ime.usp.br

Efficient and Provably-Secure Identity-Based Signatures and Signcryption from Bilinear Maps Paulo S. L. M. Barreto2, Benoˆıt Libert3?, Noel McCullagh1??, and Jean-Jacques Quisquater3 1 School of Computer Applications Dublin City University Ballymun, Dublin 9, Ireland.
2 PCS, Escola Polit´ecnica, Universidade de S˜ao Paulo Av. Prof. Luciano Gualberto, tr. 3, n. 158, s. C1-46 BR 05508-900, S˜ ao Paulo(SP), Brazil.
3 UCL, Microelectronics Laboratory, Crypto Group Place du Levant, 3, B-1348, Louvain-La-Neuve, Belgium.
Telephone : +32(0)10 47.80.62, Fax : +32(0)10 47.25.98 Abstract. In this paper we describe a new identity-based signcryption(IBSC) scheme built upon bilinear maps. This scheme turns out to bemore efficient than all others proposed so far. We prove its security in aformal model under recently studied computational assumptions and inthe random oracle model. As a result of independent interest, we proposea new provably secure identity-based signature (IBS) scheme that is alsofaster than all known pairing-based IBS methods.
Two fundamental services of public key cryptography are privacy and authentica-tion. Public key encryption schemes aim at providing confidentiality whereas dig-ital signatures must provide authentication and non-repudiation. Nowadays, no-ticeably, many real-world cryptographic application require those distinct goalsto be simultaneously achieved. This motivated Zheng [39] to provide the cryp-tographer's toolbox with a novel cryptographic primitive which he called ‘sign-cryption.' The purpose of this kind of cryptosystem is to encrypt and sign datain a single operation which has a computational cost less than that of doingboth operations sequentially. Proper signcryption schemes should provide confi-dentiality as well as authentication and non-repudiation. As in conventional en-cryption schemes, recovering the plaintext from a signcrypted message must be ? This author's work was supported the DGTRE's First Europe Program of the Wal- loon Region in Belgium.
?? This author wishes to thank Enterprise Ireland for their support with this research under grant IF/2002/0312/N.
computationally infeasible without the recipients private key; as in conventionaldigital signatures, it must be computationally infeasible to create signcryptedtexts without the senders private key.
Identity based cryptography has become a very fashionable area of research for the last couple of years. The concept was originally introduced in 1984 byShamir [34] whose idea was that users within a system could use their online iden-tifiers (combined with certain system-wide information) as their public keys. Thisgreatly reduces the problems with key management that have hampered the massuptake of public key cryptography on a per individual basis. While identity-basedsignature schemes (IBS) rapidly emerged [20, 23] after 1984 (see [5] for a thor-ough study of them), and despite another bandwidth-consuming proposal [18], itis only in 2001 that bilinear mappings over elliptic curve were found to yield thefirst fully practical identity-based encryption (IBE) solution [10]. Those bilinearmaps, or pairings, subsequently turned out to yield a plenty of cryptographic ap-plications [2] among which several recent outstanding results on identity-basedencryption [7, 8, 21, 36].
Several identity-based signcryption algorithms have been proposed so far, e.g. [11, 14, 16, 17, 26, 27, 30, 33, 37]. Within this handful of results, only [11, 14,16, 17, 26, 37] consider schemes supported by formal models and security proofs inthe random oracle model [6]. Among them, Chen and Malone-Lee's proposal [14]happens to yield the most efficient construction.
The main contribution of this paper is to propose a new identity-based sign- cryption scheme that even supersedes [14] from an efficiency point of view atthe expense of a security resting on stronger assumptions. The new constructioncan benefit from the most efficient pairing calculation techniques for a largervariety of elliptic curves than previous schemes. Indeed, recent observations [35]pinpointed problems arising when many provably secure pairing based protocolsare implemented using asymmetric pairings and ordinary curves. Our proposalavoids those problems thanks to the fact that it does not require to hash onto anelliptic curve cyclic subgroup. As a result of independent interest, we discovereda new identity-based signature that happens to be faster at verification thanpreviously known IBS schemes.
This paper is organized as follows. Section 2 presents the basic security the- oretic concepts of bilinear map groups and the hard problems underlying ourproposed algorithms. We describe our identity-based signature scheme and proveits security in section 3. We propose a new identity-based signcryption schemein section 4, and compare its efficiency to various schemes in section 5. We drawour conclusions in section 6.
Bilinear map groups and related computational problems Let k be a security parameter and p be a k-bit prime number. Let us considergroups G1, G2 and GT of the same prime order p and let P, Q be generators of respectively G1 and G2. We say that (G1, G2, GT ) are bilinear map groups ifthere exists a bilinear map e : G1 × G2 → GT satisfying the following properties: 1. Bilinearity: ∀ (S, T ) ∈ G1 × G2, ∀ a, b ∈ Z, e(aS, bT ) = e(S, T )ab.
2. Non-degeneracy: ∀ S ∈ G1, e(S, T ) = 1 for all T ∈ G2 iff S = O.
3. Computability: ∀ (S, T ) ∈ G1 × G2, e(S, T ) is efficiently computable.
4. There exists an efficient, publicly computable (but not necessarily invertible) isomorphism ψ : G2 → G1 such that ψ(Q) = P .
Such bilinear map groups are known to be instantiable with ordinary ellipticcurves such as those suggested in [29] or [4]. In this case, the trace map can beused as an efficient isomorphism ψ as long as G2 is properly chosen [35]. Withsupersingular curves, symmetric pairings (i.e. G1 = G2) can be obtained and ψis the identity.
The computational assumptions for the security of our schemes were pre- viously formalized by Boneh and Boyen [9, 7] and are recalled in the followingdefinition.
Definition 1 ([9, 7]). Let us consider bilinear map groups (G1, G2, GT ) andgenerators P ∈ G1 and Q ∈ G2.
- The q-Strong Diffie-Hellman problem (q-SDHP) in the groups (G1, G2) consists in, given a (q + 2)-tuple (P, Q, αQ, α2Q, . . , αqQ) as input, findinga pair c, 1 P
with c ∈ - The q-Bilinear Diffie-Hellman Inversion problem (q-BDHIP) in the groups (G1, G2, GT ) consists in, given hP, Q, αQ, α2Q, . . , αqQi, computinge(P, Q)1/α ∈ GT .
A new identity-based signature We here present a new identity-based signature that is significantly more efficientall known pairing based IBS schemes as its verification algorithm requires a singlepairing calculation. This efficiency gain is obtained at the expense of letting thesecurity rely on a stronger assumption than other provably secure pairing basedIBS [12, 15, 24].
Setup: given a security parameter k, the PKG chooses bilinear map groups (G1, G2, GT ) of prime order p > 2k and generators Q ∈ G2, P = ψ(Q) ∈ G1,g = e(P, Q). It then selects a master key s R Z , a system-wide public key pub = sQ ∈ G2 and hash functions H1 : {0, 1}∗ → Z , H 2 : {0, 1}∗ × GT → Z . The public parameters are params := {G1, G2, GT , P, Q, g, Qpub, e, ψ, H1, H2} Keygen: for an identity ID, the private key is SID = Sign: in order to sign a message M ∈ {0, 1}∗, the signer 1. picks a random x R Z and computes r = gx, 3. computes S = (x + h)SID.
The signature on M is σ = (h, S) ∈ Verify: a signature σ = (h, S) on a message M is accepted iff h = H2(M, e(S, H1(ID)Q + Qpub)g−h).
The scheme can be thought of as an identity-based extension of a digital sig- nature discussed in two independent papers [9, 38]. More precisely, the methodfor obtaining private keys from identities is a simplification of a method sug-gested by Sakai and Kasahara ([33]).
In [25], Kurosawa and Heng described an identity-based identification (IBI) protocol that implicitly suggests an IBS described in appendix E and which canbe proven secure under the same assumption as our proposal. It turns out thatours is slightly faster than the Kurosawa-Heng IBS in the signature generation.
At Eurocrypt'04, Bellare, Namprempre and Neven established a frame- work [5] for proving the security of a large family of identity-based signaturesand they only found two schemes to which their framework does not apply. Thepresent one does not either fall into the category of schemes to which it applies.
Indeed, it can be showed that our IBS does not result from the transformation ofany convertible standard identification or signature scheme (in the sense of [5])unless the q-SDHP is easy. A direct security proof is thus needed.
We recall here the usual model [5, 12, 15, 19, 24] of security for identity-basedsignatures which is an extension of the usual notion of existential unforgeabilityunder chosen-message attacks [22].
Definition 2 ([12]). An IBS scheme is existentially unforgeable underadaptive chosen message and identity attacks if no probabilistic polynomial time(PPT) adversary has a non-negligible advantage in this game: 1. The challenger runs the setup algorithm to generate the system's parameters and sends them to the adversary.
2. The adversary F performs a series of queries to the following oracles: - Key extraction oracle: returns private keys for arbitrary identities.
- Signature oracle: produces signatures on arbitrary messages using the private key corresponding to arbitrary identities.
3. F produces a triple (ID∗, M ∗, σ∗) made of an identity ID∗, whose private key was never extracted, and a message-signature pair (M ∗, σ∗) such that(M ∗, ID∗) was not submitted to the signature oracle. She wins if the verifi-cation algorithm accepts the triple (ID∗, M ∗, σ∗).
The next lemmas establish the security of the scheme under the q-SDH assump-tion. Lemma 1 [12] allows to only consider a weaker attack where a forger ischallenged on a given identity chosen by the challenger. The proof of lemma 2relies on the forking lemma [31, 32].
Lemma 1 ([12]). If there is a forger F0 for an adaptively chosen message andidentity attack having advantage 0 against our scheme when running in a timet0 and making qh queries to random oracle h 1, then there exists an algorithm F1 for an adaptively chosen message and given identity attack which has advantage within a running time t 1 ≤ t0. Moreover, F1 asks the same number key extraction queries, signature queries and H2-queries as F0 does.
Lemma 2. Let us assume that there is an adaptively chosen message and givenidentity attacker F that makes qh queries to random oracles H queries to the signing oracle. Assume that, within a time t, F produces a forgerywith probability  ≥ 10(qs + 1)(qs + qh )/2k. Then, there exists an algorithm B that is able to solve the q-SDHP for q = qh in an expected time t0 ≤ 120686qh (t + O(q sτp))/((1 − q/2k )) + O(q2τmult) where τmult denotes the cost of a scalar multiplication in G2 and τp is the costof a pairing evaluation.
Proof. See appendix A.
The combination of the above lemmas yields the following theorem.
Theorem 1. Let us assume that there exists an adaptively chosen message andidentity attacker F making qh queries to random oracles H queries to the signing oracle. Assume that, within a time t, F produces a forgerywith probability  ≥ 10(qs + 1)(qs + qh )/2k. Then, there exists an algorithm B that is able to solve the q-SDHP for q = qh in an expected time t0 ≤ 120686qh q (t + O(q sτp))/((1 − q/2k )) + O(q2τmult) where τmult and τp respectively denote the cost of a scalar multiplication in G2and the required time for a pairing evaluation.
Fast identity-based signcryption Formal model of identity-based signcryption The formal structure that we shall use for identity-based signcryption schemesis the following.
Setup: is a probabilistic algorithm run by a private key generator (PKG) that takes as input a security parameter to output public parameters params anda master key mk that is kept secret.
Keygen: is a key generation algorithm run by the PKG on input of params and the master key mk to return the private key SID associated to the identityID.
Sign/Encrypt: is a probabilistic algorithm that takes as input public parameters params, a plaintext message M , the recipient's identity IDR, and the sender'sprivate key SID , and outputs a ciphertext σ = Sign/Encrypt(M, S Decrypt/Verify: is a deterministic decryption algorithm that takes as input a ciphertext σ, public parameters params, the receiver's private key SIDRand (optionally) a sender's identity IDS before returning a valid message-signature pair (M, s) or a distinguished symbol ⊥ if σ does not decrypt intoa message bearing signer IDS's signature.
Unlike recent works of [11, 14] that present two-layer designs of probabilisticsignature followed by a deterministic encryption, our construction is a single-layer construction jointly achieving signature and encryption on one side anddecryption and verification on the other side. Although the description of ourscheme could be modified to fit a two-layer formalism, we kept the monolithicpresentation without hampering the non-repudiation property as, similarly to[11, 14], our construction enables an ordinary signature on the plaintext to beextracted from any properly formed ciphertext using the recipient's private key.
The extracted message-signature pair can be forwarded to any third party insuch a way that a sender remains committed to the content of the plaintext.
Unlike models of [11, 14] that consider anonymous ciphertexts, the above one assumes that senders' identities are sent in the clear along with ciphertexts.
Actually, receivers do not need to have any a priori knowledge on whom theciphertext emanates from in our scheme but this simply allows more efficientreductions in the security proofs. A simple modification of our scheme yieldsanonymous ciphertexts and enables senders' identities to be recovered by theDecrypt/Verify algorithm (which only takes a ciphertext and the recipient's pri-vate key as input).
Definition 3. An identity-based signcryption scheme (IBSC) satisfies the mes-sage confidentiality property (or adaptive chosen-ciphertext security: IND-IBSC-CCA) if no PPT adversary has a non-negligible advantage in the followinggame.
1. The challenger runs the Setup algorithm on input of a security parameter k and sends the domain-wide parameters params to the A.
2. In a find stage, A starts probing the following oracles: - Keygen: returns private keys associated to arbitrary identities.
- Sign/Encrypt: given a pair of identities IDS, IDR and a plaintext M , it returns an encryption under the receiver's identity IDR of the messageM signed in the name of the sender IDS.
- Decrypt/Verify: given a pair of identities (IDS, IDR) and a ciphertext σ, it generates the receiver's private key SID either a valid message-signature pair (M, s) for the sender's identity IDSor the ⊥ symbol if, under the private key SID , σ does not decrypt into a valid message-signature pair.
3. A produces two plaintexts M0, M1 ∈ M and identities ID∗ and ID∗ .
She may not have extracted the private key of ID∗ and she obtains C = Sign/Encrypt(Mb, SID∗ , ID∗ , params), for a random a bit b R 4. In the guess stage, A asks new queries as in the find stage. This time, she may not issue a key extraction request on ID∗ and she cannot submit C to the Decrypt/Verify oracle for the target identity ID∗ .
5. Finally, A outputs a bit b0 and wins if b0 = b.
A's advantage is defined as Adv(A) := 2 × Pr[b0 = b] − 1.
The next definition, given in [11], considers non-repudiation w.r.t. signaturesembedded in ciphertexts rather than w.r.t. ciphertexts themselves.
Definition 4. An identity-based signcryption scheme (IBSC) is said to be ex-istentially signature-unforgeable against adaptive chosen messages and ci-phertexts attacks (ESUF-IBSC-CMA) if no PPT adversary can succeed in thefollowing game with a non-negligible advantage: 1. the challenger runs the Setup algorithm on input k and gives the system-wide public key to the adversary F .
2. F issues a number of queries as in the previous definition.
3. Finally, F outputs a triple (σ∗, ID∗ , ID∗ ) and wins the game if the sender's identity ID∗ was not corrupted and if the result of the Decrypt/Verify ora- cle on the ciphertext σ∗ under the private key associated to ID∗ is a valid message-signature pair (M ∗, s∗) such that no Sign/Encrypt query involvedM ∗, ID∗ and some receiver ID0 (possibly different from ID∗ ) and resulted in a ciphertext σ0 whose decryption under the private key SID0 is the alleged forgery (M ∗, s∗, ID∗ ).
The adversary's advantage is its probability of victory.
In both of these definitions, we consider insider attacks [1]. Namely, in the definition of message confidentiality, the adversary is allowed to be challenged ona ciphertext created using a corrupted sender's private key whereas, in the notionof signature non-repudiation, the forger may output a ciphertext computed undera corrupted receiving identity.
Our scheme is obtained from an optimized combination of our IBS scheme withthe most basic version of the Sakai-Kasahara IBE ([33, 13]) which is only secureagainst chosen-plaintext attacks when used as an encryption-only system. Thisallows performing the signature-encryption operation without computing a pair-ing whereas only two pairings have to be computed upon decryption/verification.
Setup: given k, the PKG chooses bilinear map groups (G1, G2, GT ) of prime order p > 2k and generators Q ∈ G2, P = ψ(Q) ∈ G1, g = e(P, Q) ∈ GT . Itthen chooses a master key s R Z , a system-wide public key Q G2 and hash functions H1 : {0, 1}∗ → Z , H 2 : {0, 1}∗ × GT → Zp H3 : GT → {0, 1}n. The public parameters are params := {G1, G2, GT , P, Q, g, Qpub, e, ψ, H1, H2, H3} Keygen: for an identity ID, the private key is SID = Sign/Encrypt: given a message M ∈ {0, 1}∗, a receiver's identity IDB and a sender's private key SID , 3(r) ∈ {0, 1}n.
2(M, r) ∈ Z .
3. Compute S = (x + h)ψ(SID ).
4. Compute T = x(H1(IDB)P + ψ(Qpub)).
The ciphertext is σ = hc, S, T i ∈ {0, 1}n × G1 × G1.
Decrypt/Verify: given σ = hc, S, T i, and some sender's identity IDA, 1. Compute r = e(T, SID ), M = c ⊕ H 3(r), and h = H2(M, r).
2. Accept the message iff r = e(S, H1(IDA)Q + Qpub)g−h. If this condition holds, return the message M and the signature (h, S) ∈ If required, the anonymity property is obtained by scrambling the sender's identity IDA together with the message at step 1 of Sign/Encrypt in such away that the recipient retrieves it at the first step of the reverse operation.
This change does not imply any computational penalty in practice but inducesmore expensive security reductions. In order for the proof to hold, IDA must beappended to the inputs of H2.
The following theorems claim the security of the scheme in the random oraclemodel under the same irreflexivity assumption as Boyen's scheme [11]: the signa-ture/encryption algorithm is assumed to always take distinct identities as inputs(in other words, a principal never encrypts a message bearing his signature usinghis own identity).
Theorem 2. Assume that an IND-IBSC-CCA adversary A has an advantage against our scheme when running in time τ , asking qh queries to random oracles Hi (i = 1, 2, 3), qse signature/encryption queries and qdv queries to the decryp-tion/verification oracle. Then there is an algorithm B to solve the q-BDHIP forq = qh with probability within a time τ 0 < τ +O(qse+qdv)τp+O(q2 )τ exp where τexp and τmult are respectively the costs of an exponentiation in GT and a multiplicationin G2 whereas τp is the complexity of a pairing computation.
Proof. See appendix B.
Theorem 3. Assume there exists an ESUF-IBSC-CMA attacker A that makesqh queries to random oracles H i (i = 1, 2, 3), qse signature/ encryption queries and qdv queries to the decryption/verification oracle. Assume also that, withina time τ , A produces a forgery with probability  ≥ 10(qse + 1)(qse + qh )/2k.
Then, there is an algorithm B that is able to solve the q-SDHP for q = qh in τ + O((qse + qdv)τp) + qdvqh τexp (1 − 1/2k)(1 − q/2k) where τmult, τexp and τp denote the same quantities as in theorem 2.
Proof. See appendix C.
We now restate theorem 2 for the variant of our scheme with anonymous ciphertexts. The simulator's worst-case running time is affected by the fact that,when handling Decrypt/Verify requests, senders'identities are not known in ad-vance. The reduction involves a number of pairing calculations which is quadraticin the number of adversarial queries.
Theorem 4. Assume that an IND-IBSC-CCA adversary A has an advantage against our scheme when running in time τ , asking qh queries to random oracles Hi (i = 1, 2, 3), qse signature/encryption queries and qdv queries to the decryp-tion/verification oracle. Then there is an algorithm B to solve the q-BDHIP forq = qh with probability within a time τ 0 < τ + O(qse + qdvqh )τ τexp, τmult and τp denote the same quantities as in previous theorems.
Proof. See appendix D.
Theorem 3 can be similarly restated as its reduction cost is affected in the sameway.
A formal proof of ciphertext anonymity in the model of [11] will be given in the full version of this paper for the anonymous version of the scheme.
We concede that even the latter variant does not feature all the properties of the systems of Boyen ([11]) or Chen-Malone-Lee ([14]). For example, it doesnot have the ciphertext unlinkability property ([11, 14]): it seems infeasible foranyone to use his private key to embed a given message-signature pair into aproper ciphertext intended to himself. We were also unable to formally estab-lish the ciphertext authentication property according to which a ciphertext isalways signed and encrypted by the same person and cannot be subject to akind of ‘man-in-the-middle' attack. Nevertheless, the scheme does seem to havethis property because of the same reason that precludes the ciphertext unlinka-bility property.
Overall, we believe that the scheme does satisfy the main requirements that might be desired in practice. In our opinion, it suffices to implement most prac-tical applications and its great efficiency renders it more than interesting foridentity-based cryptography.
Efficiency discussions and comparisons In [35], Smart and Vercauteren pointed out problems that arise when severalpairing based protocols are implemented with asymmetric pairings. They showedthe difficulty of finding groups G2 allowing the use of the most efficient pairing calculation techniques for ordinary curves [3] if arbitrary strings should be ef-ficiently hashed onto them and efficient isomorphism ψ : G2 → G1 must beavailable at the same time. As a consequence, several protocols have to be im-plemented with groups for which no efficient isomorphism ψ : G2 → G1 iscomputable and their security eventually has to rely on somewhat unnaturalassumptions.
Except [33] that has no security proof (and actually has several known secu- rity problems [28]), all known identity-based signcryption schemes would requireto hash onto G2 if they were instantiated with asymmetric pairings. Our schemeavoids this problem since it does not require to hash onto a cyclic group. It thusmore easily benefits from optimized pairing calculation algorithms. For example,section 4 of [35] yields an example of group G2 for which techniques of [3] canbe used and where efficient isomorphisms are available.
Table 1. Efficiency comparison signcryption scheme exp mul pairings time (ms) exp mul pairings time (ms) Nalla-Reddy♦./ ([30]) Malone-Lee♣ ([27]) Chen-Malone-Lee ([14]) Sakai-Kasahara♣ ([33]) exp mul pairings time (ms) exp mul pairings time (ms) Chow-Yiu-Hui-Chow ([16]) (†) One pairing is precomputable, incurring for each user a storage cost of one µr element for each other user in the system.
(‡) One pairing is precomputable, incurring for each user a storage cost of one µr element for each other user in the system, plus one µr exponentiation.
(?) Two pairings are precomputable, incurring for each user a storage cost of one µr element for each user in the system, plus two µr exponentiations.
(§) One of the scalar multiplications is done in hQi rather than hP i.
(¶) Universally verifiable scheme (i.e. supports public ciphertext validation).
(♣) These schemes suffer from security problems as mentioned in [26, 28].
(♠) This scheme does not provide insider-security for the message-confidentiality criterion.
(♦) This scheme has no security proof.
(./) This construction can only authenticate messages from the receiver's point of view.
We now assess the comparative efficiency of several identity-based signcryp- tion schemes, implemented according to their original descriptions. Table 1 sum-marises the number of relevant basic operations underlying several identity-basedsigncryption and signature schemes, namely, µr exponentiations, scalar pointmultiplications, and pairing evaluations, and compares the observed processingtimes (in milliseconds) for a supersingular curve of embedding degree k = 6 over F397 , using implementations written in C++ and run on an Athlon XP 2 GHz.
Subtleties in the algorithms determine somewhat different running times evenwhen the operation counts for those algorithms are equal. We see from theseresults that our proposed algorithms rank among the fastest schemes.
We have described efficient and provably secure signature and signcryptionschemes that are faster than any pairing-based scheme previously proposed inthe literature. The latter can be instantiated with either named or anonymousciphertexts and is more convenient than previous proposals for implementationswith asymmetric pairings.
1. J.-H. An, Y. Dodis, and T. Rabin. On the security of joint signature and encryption.
In Eurocrypt'02, volume 2332 of LNCS, pages 83–107. Springer, 2002.
2. P. S. L. M. Barreto. The pairing based crypto lounge. http://planeta.terra.
3. P. S. L. M. Barreto, B. Lynn, and M. Scott. On the selection of pairing-friendly groups. In SAC'03, volume 3006 of LNCS, pages 17–25. Springer, 2003.
4. P. S. L. M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order.
Cryptology ePrint Archive, Report 2005/133, 2005. http://eprint.iacr.org/2005/133.
5. M. Bellare, C. Namprempre, and G. Neven. Security proofs for identity-based identification and signature schemes. In Eurocrypt'04, volume 3027 of LNCS, pages268–286. Springer, 2004.
6. M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In 1st ACM Conference on Computer and CommunicationsSecurity, pages 62–73, Fairfax, USA, 1993. ACM Press.
7. D. Boneh and X. Boyen. Efficient selective-ID secure identity based encryption without random oracles. In Eurocrypt'04, volume 3027 of LNCS, pages 223–238.
Springer, 2004.
8. D. Boneh and X. Boyen. Secure identity based encryption without random oracles.
In Crypto'04, volume 3152 of LNCS, pages 443–459. Springer, 2004.
9. D. Boneh and X. Boyen. Short signatures without random oracles. In Eurocrypt'04, volume 3027 of LNCS, pages 56–73. Springer, 2004.
10. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. In Crypto'01, volume 2139 of LNCS, pages 213–229. Springer, 2001.
11. X. Boyen.
Multipurpose identity-based signcryption: A swiss army knife for identity-based cryptography. In Crypto'03, volume 2729 of LNCS, pages 383–399.
Springer, 2003.
12. J. C. Cha and J. H. Cheon. An identity-based signature from gap Diffie-Hellman groups. In PKC'03, volume 2567 of LNCS, pages 18–30. Springer, 2003.
13. L. Chen and Z. Cheng.
Security proof of Sakai-Kasahara's identity-based en- cryption scheme.
Cryptology ePrint Archive, Report 2005/226, 2005.
14. L. Chen and J. Malone-Lee. Improved identity-based signcryption. In PKC'05, volume 3386 of LNCS, pages 362–379. Springer, 2005.
15. J. H. Cheon, Y. Kim, and H. J. Yoon.
A new id-based signature with batch verification. Cryptology ePrint Archive, Report 2004/131, 2004. http://eprint.
iacr.org/2004/131.
16. S. S. M. Chow, S. M. Yiu, L. C. K. Hui, and K. P. Chow. Efficient forward and provably secure ID-based signcryption scheme with public verifiability and publicciphertext authenticity. In 6th International Conference on Information Securityand Cryptology – ICISC'03, volume 2971 of LNCS, pages 352–369. Springer, 2003.
17. S. S. M. Chow, T. H. Yuen, L. C. K. Hui, and S. M. Yiu. Signcryption in hierarchical identity based cryptosystem. In 20th International Conference on InformationSecurity (SEC'05). IFIP TC11, 2005.
18. C. Cocks. An identity based encryption scheme based on quadratic residues. In 8th IMA International Conference, volume 2260 of LNCS, pages 360–363. Springer,2001.
19. Y. Dodis, J. Katz, S. Xu, and M. Yung. Strong key-insulated signature schemes.
In PKC'03, volume 2567 of LNCS, pages 130–144. Springer, 2003.
20. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems.
In Crypto'86, volume 0263 of LNCS, pages 186–194.
Springer, 1986.
21. C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In Asiacrypt'02, volume 2501 of LNCS, pages 548–566. Springer, 2002.
22. S. Goldwasser, S. Micali, and R. Riverst. A digital signature scheme secure against adaptive chosen message attacks. SIAM Journal of Computing, 17(2):281–308,1988.
23. L. Guillou and J.-J. Quisquater. A "paradoxical" identity-based signature scheme resulting from zero-knowledge. In Crypto'88, volume 0403 of LNCS, pages 216–231.
Springer, 1988.
24. F. Heß. Efficient identity based signature schemes based on pairings. In SAC'02, volume 2595 of LNCS, pages 310–324. Springer, 2003.
25. K. Kurosawa and S.-H. Heng. Identity-based identification without random oracles.
In ISH'05, LNCS. Springer, 2005. To appear.
26. B. Libert and J.-J. Quisquater. New identity based signcryption schemes from In IEEE Information Theory Workshop, Paris, France, 2003.
27. J. Malone-Lee. Identity-based signcryption. Cryptology ePrint Archive, Report 28. N. McCullagh and P. S. L. M. Barreto.
Efficient and forward-secure identity- based signcryption. Cryptology ePrint Archive, Report 2004/117, 2004. http://eprint.iacr.org/2004/117.
29. A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals, E84-A(5):1234–1243, 2001.
30. D. Nalla and K. C. Reddy. Signcryption scheme for identity-based cryptosystems.
Cryptology ePrint Archive, Report 2003/066, 2003. http://eprint.iacr.org/2003/066.
31. D. Pointcheval and J. Stern. Security proofs for signature schemes. In Eurocrypt'96, volume 1992 of LNCS, pages 387–398. Springer, 1996.
32. D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361–396, 2000.
33. R. Sakai and M. Kasahara. ID based cryptosystems with pairing on elliptic curve.
In SCIS'03, Hamamatsu, Japan, 2003. http://eprint.iacr.org/2003/054.
34. A. Shamir. Identity based cryptosystems and signature schemes. In Crypto'84, volume 0196 of LNCS, pages 47–53. Springer, 1984.
35. N. P. Smart and F. Vercauteren. On computable isomorphisms in efficient pair- ing based systems. Cryptology ePrint Archive, Report 2005/116, 2005. http://eprint.iacr.org/2005/116.
36. B. Waters. Efficient identity-based encryption without random oracles. In Euro- crypt'05, volume 3494 of LNCS, pages 114–127. Springer, 2005.
37. T. H. Yuen and V. K. Wei. Fast and proven secure blind identity-based signcryption from pairings. In CT-RSA'05, volume 3376 of LNCS, pages 305–322. Springer,2003.
38. F. Zhang, R. Safavi-Naini, and W. Susilo. An efficient signature scheme from bilinear pairings and its applications. In PKC'04, volume 2947 of LNCS, pages277–290. Springer, 2004.
39. Y. Zheng. Digital signcryption or how to achieve cost (signature & encryption) << cost(signature) + cost(encryption). In Crypto'97, volume 1294 of LNCS, pages165–179. Springer, 1997.
Proof. We first show how to provide the adversary with a consistent view andwe then explain how to apply the forking lemma.
Algorithm B takes as input (P, Q, αQ, α2Q, . . , αqQ) and aims to find a pair (c, 1 P ). In a setup phase, it builds a generator G ∈ G1 such that it knows 1, . . , wq−1 ∈R Zp 1, w2, . . , wq−1 ← Z and expands f (z) = Qq−1(z + w 0, . . , cq−1 ∈ Z so that f (z) = Pq−1 c 2. It sets generators H = Pq−1 c i(αiQ) = f (α)Q ∈ G2 and G = ψ(H ) = f (α)P ∈ G1. The public key Hpub ∈ G2 is fixed to Hpub = Pq so that Hpub = αH although B does not know α.
3. For 1 ≤ i ≤ q − 1, B expands fi(z) = f (z)/(z + wi) = Pq−2 d diψ(αiQ) = fi(α)P = G) are computed using the left member of (1).
B is then ready to answer F 's queries along the course of the game. It firstinitializes a counter to 1 and launches F on the input (Hpub, ID∗) for a randomlychosen challenge identity ID∗ R ← {0, 1}∗. For simplicity, we assume that queries to H1 are distinct, and that any query involving an identifier ID is preceded bythe random oracle query H1(ID).
1-queries on an identity ID ∈ {0, 1}∗: B returns a random w∗ ID = ID∗. Otherwise, B answers w = w and increments . In both cases, B stores (ID, w) (where w∗ = w or w ) in a list L1.
- Key extraction queries on ID 6= ID∗: B recovers the matching pair (ID, w) from L1 and returns the previously computed (1/(α + w))G.
- Signature query on a message-identity pair (M, ID): B picks S R Z , computes r = e(S, Q ID)e(G, H )−h, where QID = H1(ID)H + Hpub, and backpatches to define the value H 2(M, r) as h ∈ Z (B aborts in the unlikely event that H2(M, r) is already defined).
We have explained how to simulate F 's environment in a chosen-message andgiven identity attack. We are ready to apply the forking lemma that essen-tially says the following: consider a scheme producing signatures of the form(M, r, h, S), where each of r, h, S corresponds to one of the three moves of ahonest-verifier zero-knowledge protocol. Let us assume that a chosen-messageattacker F forges a signature (M, r, h, S) in a time t with probability  ≥10(qs + 1)(qs + qh)/2k (k being a security parameter so that h is uniformlytaken from a set of 2k elements) when making qs signature queries and qh ran-dom oracle calls. If the triples (r, h, S) can be simulated without knowing theprivate key, then there exists a Turing machine F 0 that uses F to produce twovalid signatures (m, r, h1, S1), (m, r, h2, S2), with h1 6= h2, in expected timet0 ≤ 120686qht/.
In our setting, from a forger F , we build an algorithm F 0 that replays F a sufficient number of times on the input (Hpub, ID∗) to obtain two suitable forg-eries hM ∗, r, h1, S1i, hM ∗, r, h2, S2i with h1 6= h2.
The reduction then works as follows. The simulator B runs F 0 to obtain two forgeries hM ∗, r, h1, S1i, hM ∗, r, h2, S2i for the same message M ∗ and commit-ment r. At this stage, B recovers the pair (ID∗, w∗) from list L1. We note thatw∗ 6= w1, . . , wq−1 with probability at least 1 − q/2k. If both forgeries satisfythe verification equation, we obtain the relations e(S1, QID∗ )e(G, H)−h1 = e(S2, QID∗ )e(G, H)−h2 , with QID∗ = H1(ID∗)H + Hpub = (w∗ + α)H. Then, it comes that e((h1 − h2)−1(S1 − S2), QID∗ ) = e(G, H), and hence T ∗ = (h1 − h2)−1(S1 − S2) = G. From T ∗, B can proceed as in [9] to extract σ∗ = P : it first obtains γ −1, γ0, . . , γq−2 ∈ Zp f (z)/(z + w∗) = γ−1/(z + w∗) + Pq−2 γ izi and eventually computes before returning the pair (w∗, σ∗) as a result.
It finally comes that, if F forges a signature in a time t with probability  ≥ 10(qs + 1)(qs + qh )/2k, B solves the q-SDHP in expected time t0 ≤ 120686qh (t + O(q sτp))/((1 − q/2k )) + O(q2τmult) where the last term accounts for the cost of the preparation phase.
Proof of Theorem 2 Proof. Algorithm B takes as input hP, Q, αQ, α2Q, . . , αqQi and attempts toextract e(P, Q)1/α from its interaction with A.
In a preparation phase, B selects R Ii = I − wi. As in the technique of [9] and in lemma 2, it sets up generatorsG2 ∈ G2, G1 = ψ(G2) ∈ G1 and another G2 element U = αG2 such that it knowsq − 1 pairs (wi, Hi = (1/(wi + α))G2) for i ∈ {1, . . , q} { }. The system-widepublic key Qpub is chosen as Qpub = −U − I G2 = (−α − I )G2 so that its (unknown) private key is implicitly set to x = −α − I i ∈ {1, . . , q} { }, we have (Ii, −Hi) = (Ii, (1/(Ii + x))G2).
B then initializes a counter ν to 1 and starts A on input of (G1, G2, Qpub).
Throughout the game, we assume that H1-queries are distinct, that the targetidentity ID∗ is submitted to H 1 at some point and that any query involving an identity ID comes after a H1-query on ID: - H1-queries (let us call IDν the input of the νth one of such queries): B answers Iν and increments ν.
- H2-queries on input (M, r): B returns the defined value if it exists and a otherwise. To anticipate possible subsequent Decrypt/Verify requests, B additionally simulates random oracle H3 on its own to obtainh3 = H3(r) ∈ {0, 1}n and stores the information (M, r, h2, c = M ⊕ h3, γ =r · e(G1, G2)h2 ) in L2.
- H3-queries for an input r ∈ GT : B returns the previously assigned value if it exists and a random h 3 ← {0, 1}n otherwise. In the latter case, the input r and the response h3 are stored in a list L3.
- Keygen queries on an input IDν: if ν = , then B fails. Otherwise, it knows that H1(IDν) = Iν and returns −Hν = (1/(Iν + x)) G2 ∈ G2.
- Sign/Encrypt queries for a plaintext M and identities (IDS, IDR) = (IDµ, IDν) for µ, ν ∈ {1, . . , qh }: we observe that, if µ 6= , B knows the sender's private µ and can answer the query according to the specification of Sign/Encrypt. We thus assume µ = and hence ν 6= by the irreflexivityassumption. Observe that B knows the receiver's private key SID = −H construction. The difficulty is to find a random triple (S, T, h) ∈ e(T, SID ) = e(S, Q G2 + Qpub. To do so, B randomly chooses t, h computes S = tψ(SID ) = −tψ(H ν G2 + Qpub in order to obtain the desired equality r = e(T , SIDν 1, G2)−h = e(ψ(SIDν 1, G2)−h before patching the hash value H2(M, r) to h (B fails if H2 is already defined but this only hap-pens with probability (qse + qh )/2k). The ciphertext σ = hM ⊕ H is returned.
- Decrypt/Verify queries on a ciphertext σ hc, S, T i for identities (IDS, IDR) = (IDµ, IDν): we assume that ν = (and hence µ 6= by the ir-reflexivity assumption), because otherwise B knows the receiver's private keySID = −H ν and can normally run the Decrypt/Verify algorithm. Since µ 6= , B has the sender's private key SID and also knows that, for all valid cipher- (ψ−1(S) − hS (T ), where h = H hash value obtained in the Sign/Encrypt algorithm and QID = I ν G2 + Qpub.
Hence, we have the relation e(T, SID ) = e(ψ(Q ), ψ−1(S) − hS which yields e(T, SID ) = e(ψ(Q ), ψ−1(S))e(ψ(Q serve that the latter equality can be tested without inverting ψ ase(ψ(QID ), ψ−1(S)) = e(S, Q ). The query is thus handled by computing γ = e(S, QID ), where Q µG2 + Qpub, and searching through list L2 for entries of the form (Mi, ri, h2,i, c, γ) indexed by i ∈ {1, . . , qh }. If none is found, σ is rejected. Otherwise, each one of them is further examined: forthe corresponding indexes, B checks if e(T, SID )/e(S, Q (the pairings are computed only once and at most qh exponentiations are needed), meaning that (3) is satisfied. If the unique i ∈ {1, . . , qh } satisfying (4) is detected, the matching pair (Mi, hh2,i, Si) is returned. Otherwise, σ isrejected. Overall, an inappropriate rejection occurs with probability smallerthan qdv/2k across the whole game.
At the challenge phase, A outputs messages (M0, M1) and identities (IDS, IDR)for which she never obtained IDR's private key. If IDR 6= ID , B aborts. Otherwise,it picks ξ R ← {0, 1}n and S R G1 to return the challenge σ∗ = hc, S, T i where T = −ξG1 ∈ G1. If we define ρ = ξ/α and since x = −α − I , we cancheck that T = −ξG1 = −αρG1 = (I + x)ρG1 = ρI G1 + ρψ(Qpub).
A cannot recognize that σ∗ is not a proper ciphertext unless she queries H2 orH3 on e(G1, G2)ρ. Along the guess stage, her view is simulated as before andher eventual output is ignored. Standard arguments can show that a successfulA is very likely to query H2 or H3 on the input e(G1, G2)ρ if the simulation isindistinguishable from a real attack environment.
To produce a result, B fetches a random entry (M, r, h2, c, γ) or hr, .i from the lists L2 or L3. With probability 1/(2qh + q ) (as L 3 contains no more than records by construction), the chosen entry will contain the right element r = e(G1, G2)ρ = e(P, Q)f(α)2ξ/α, where f (z) = Pq−1 c izi is the polynomial for which G2 = f (α)Q. The q-BDHIP solution can be extracted by noting that, ifγ∗ = e(P, Q)1/α, then 1, G2)1/α = γ∗(c2 ci+1(αiP ), c0Q
e G1, In an analysis of B's advantage, we note that it only fails in providing a consistent simulation because one of the following independent events: E1: A does not choose to be challenged on ID .
E2: a key extraction query is made on ID .
E3: B aborts in a Sign/Encrypt query because of a collision on H2.
E4: B rejects a valid ciphertext at some point of the game.
We clearly have Pr[¬E1] = 1/qh and we know that ¬E 1 implies ¬E2. We also already observed that Pr[E3] ≤ qse(qse + qh )/2k and Pr[E 4] ≤ qdv /2k . We thus 1 ∧ ¬E3 ∧ ¬E4] ≥ We obtain the announced bound by noting that B selects the correct elementfrom L2 or L3 with probability 1/(2qh + q ). Its workload is dominated by O(q2 ) multiplications in the preparation phase, O(q se + qdv ) pairing calculations and O(qdvqh ) exponentiations in GT in its emulation of the Sign/Encrypt and Proof of Theorem 3 Proof. The proof is almost similar to the one of theorem 1. Namely, it showsthat a forger in the ESUF-IBSC-CMA game implies a forger in a chosen-messageand given identity attack. Using the forking lemma [31, 32], the latter is in turnshown to imply an algorithm to solve the q-Strong Diffie-Hellman problem. Moreprecisely, queries to the Sign/Encrypt and Decrypt/Verify oracles are answered asin the proof of theorem 2 and, at the outset of the game, the simulator choosespublic parameters in such a way that it can extract private keys associated toany identity but the one which is given as a challenge to the adversary. By doingso, thanks to the irreflexivity assumption, it is able to extract clear message-signature pairs from ciphertexts produced by the forger (as it knows the privatekey of the receiving identity ID∗ ).
Proof of Theorem 4 Proof. The simulator is the same as in theorem 2 with the following differences(recall that senders' identities are provided as inputs to H2).
- H2-queries on input (IDS, M, r): B returns the previously defined value if it exists and a random h otherwise. To anticipate subsequent Decrypt/Verify requests, B simulates oracle H3 to obtain h3 = H3(r) ∈{0, 1}n+n0 (where n0 is the maximum length of identity strings) and stores(IDS, M, r, h2, c = (M kIDS) ⊕ h3, γ = r · e(G1, G2)h2 ) in list L2.
- Decrypt/Verify queries: given a ciphertext σ = hc, S, T i and a receiver's iden- tity IDR = IDν, we assume that ν = because otherwise B knows thereceiver's private key. The simulator B does not know the sender's identityIDS but knows that IDS 6= IDν. It also knows that, for the private key SID , (ψ−1(S) − hS e(T, SID ) = e(ψ(Q ), ψ−1(S) − hS where h = H2(IDS, M, r) is the hash value obtained in the Sign/ Encryptalgorithm and QID ν G2 + Qpub. The query is handled by searching through list L2 for entries of the form (IDS,i, Mi, ri, h2,i, c, γi) indexed byi ∈ {1, . . , qh }. If none is found, the ciphertext is rejected. Otherwise, each one of these entries for which IDS,i 6= IDν is further examined by checkingwhether γi = e(S, H1(IDS,i)Q + Qpub) and (at most 3qh + 1 pairings and q exponentiations must be computed), meaning that equation (5) is satisfied and that the ciphertext contains avalid message signature pair if both relations hold. If B detects an indexi ∈ {1, . . , qh } satisfying them, the matching pair (M i, hh2,i, Si) is returned.
Otherwise, σ is rejected and such a wrong rejection again occurs with anoverall probability smaller than qdv/2k.
The Kurosawa-Heng identity-based signature We describe here the IBS scheme that can be derived from a modification of theKurosawa-Heng [25] identity-based identification scheme using the Fiat-Shamirheuristic [20].
Setup and Keygen are the same as in our scheme described in section 3. The public parameters are params := {G1, G2, GT , P, Q, g, Qpub, e, ψ, H1, H2}.
We also define QID = H1(ID)Q + Qpub.
Sign: to sign a message M ∈ {0, 1}∗, the signer does the following: Z and computes r = e(P, Q 3. computes S = xP + hSID.
The signature on M is σ = (h, S) ∈ Verify: a signature σ = (h, S) on a message M is accepted iff h = H2(M, e(S, QID)g−h).
The above IBS can be proven secure under the q-Strong Diffie-Hellman assump-tion. Even in its optimized version where e(P, H1(ID)Q + Qpub) is pre-computedby the signer, its signature generation algorithm happens to be slightly moreexpensive than our scheme's one which requires a simple scalar multiplicationat step 3.

Source: https://www.ime.usp.br/~rt/cranalysis/BarretoSignLIbert.pdf