The Twin Bilinear Diffie-Hellman Inversion Problem and Applications - Information Security and Cryptology-ICISC 2010 - page 121

Encrypt. A message M ∈M is encrypted for an identity ID as follows:

1. Compute t 1 = u 1 g H 1 ( ID ) = g s 1 + H 1 ( ID )

1

and t 2 = u 2 g H 1 ( ID ) = g s 2 + H 1 ( ID )

2

.

1 2

n and compute ( r 1 ,r 2 )= H 3 ( σ, M ).
3. Set the ciphertext to be C =( t r 1 ,t r 2 ,σ

2. Choose a random σ ∈{ 0 , 1 }

H 2 ( e ( g 1 ,g 1 ) r 1 ,e ( g 2 ,g 2 ) r 2 ) ,M

⊕ ⊕

H 4 ( σ )).
Decrypt. Let C = be a ciphertext encrypted using ID .Then

C can be decrypted by d ID =( d 1 ,d 2 )as:
1. Compute V ⊕ H 2 ( e ( U 1 ,d 1 ) ,e ( U 2 ,d 2 )) = σ .
2. Compute W

U 1 ,U 2 ,V,W ∈C

H 4 ( σ )= M .
3. Set ( r 1 ,r 2 )= H 3 ( σ, M ). Test whether U 1 = t r 1

⊕

and U 2 = t r 2

. If not, reject

the ciphertext; otherwise output M .

Theorem 3.1 Twin SK-IBE is chosen ciphertext secure ( IND - ID - CCA ) provided
that H i (1 2) are random oracles and the ( Q h 1 +1) - BDHI assumption

holds. Specifically, suppose there exists an IND - ID - CCA adversary

≤ i ≤

A against twin

SK-IBE that has advantage . Suppose during the attack

A

makes at most Q h i

queries to H i for 1

≤ i ≤ B to

2 respectively. Then there exists an algorithm

solve the ( Q h 1 +1) - BDHI problem with advantage

1

1
Q h 1

2 Q h 1
p

Adv-BDHI B ≥ 2 · −

and a running time O ( time ( A )).

Proof. We first build an algorithm B that uses A to solve the strong twin Q h 1 -

BDHI problem in is given as input a random strong twin Q h 1 -BDHI instance

( g 1 , g 1 x ,..., g 1 x q ; g 2 , g 2 y ,..., g 2 y q ).

G . B

's goal is to output Z 1 = e ( g 1 , g 1 ) 1 /x B and

Z 2 = e ( g 2 , g 2 ) 1 /y . B works by interacting with A in an IND - ID - CCA game, spec-

ified in Appendix A.1, as follows:

builds generators g 1 ,g 2 ∈ G ∗ for which it knows Preparation. Let q = Q h 1 , B

1 triples of the form ( w 0 + w i ,g 1 / ( x + w i ) ,g 1 /y + w i

2

q − ) for random w 1 ,...,w q− 1 ∈

1

Z p .Thisisdoneasfollows:
1. Pick random w 0 ,...,w q− 1 ∈ Z p

and let f ( z ) be the polynomial f ( z )=

q− 1

i =1 ( z + w i ). Reformulate f to get f ( z )= q− 1 i =0 c i z i . The constant term

c 0 is non-zero because w i =0.The c i are computable from w i .

2. Compute

q− 1 q− 1

( g 1 x i ) c i = g 1 f ( x ) ; u 1 = g −w 0 ( g 1 x i +1 ) c i = g −w 0 g 1 xf ( x ) = g x−w 0

g 1 = ;

1 1 1

i =0 i =0

q− 1 q− 1

( g 2 y i ) c i = g 2 f ( y ) ; u 2 = g −w 0 ( g 2 y i +1 ) c i = g −w 0 g 2 yf ( y ) = g y−w 0

g 2 = .

2 2 2

i =0 i =0