Output : e(P, P)abc ∈ G2 with the help of a DBDH oracle.

ˆ

Boneh and Franklin [22] point out that the Gap Bilinear Dif¬e-Hellman (GBDH)

parameter generators satisfying the GBDH assumption can be constructed from the

Weil and Tate pairings associated with super-singular elliptic curves or abelian va-

rieties.

De¬nition 2.1.10 (Bilinear Inverse Dif¬e-Hellman Problem)

Instance : (P, aP, cP)

’1 c

Output : e(P, P)a ∈ G2 .

ˆ

Recent work of Zhang, Safavi-Naini, and Susilo [106] shows that the Bilinear In-

verse Dif¬e-Hellman (BIDH) problem is polynomial time equivalent to the BDH

problem.

2.1.4 Cryptographic Tools

Encryption schemes, signature schemes, message authentication codes, and crypto-

graphic hash functions are functions which have many uses in cryptography. In order

to obtain security arguments without compromising the ef¬ciency of hash functions,

such functions are hypothesized to behave like a random function. The security of

the various encryption, signature, message authentication codes schemes is de¬ned

using an indistinguishability (IND) game. An example of the IND game is described

in De¬nition 2.1.12.

2.1.4.1 Encryption Schemes: Asymmetric Setting

The classical goal of a secure encryption scheme is to preserve the privacy of mes-

sages. That is to allow one party to send a message to another such that the contents

24 2 Background Materials

of the message remain hidden from anyone intercepting the communication. Any

adversary, A , should not be able to learn from a ciphertext information about its

plaintext.

The standard de¬nition for the security of encryption schemes (also known as se-

mantic security) was ¬rst formulated by Goldwasser and Micali [47]. They consider

privacy under indistinguishability of encryptions (IND) under chosen-plaintext at-

tack (CPA)3 , and show that IND-CPA is equivalent to semantic security. The de¬ni-

tion for an asymmetric encryption scheme [11] is given in De¬nition 2.1.11.

De¬nition 2.1.11 (An Asymmetric Encryption Scheme) An asymmetric encryp-

tion scheme is given by a triple of algorithms, PE = (K , E , D), where

• K , the key generation algorithm, is a probabilistic algorithm that takes a secu-

rity parameter k and returns a pair (pk, sk) of matching public and secret keys.

• E , the encryption algorithm, is a probabilistic algorithm that takes a public key

pk and a message x ∈ {0, 1}— to produce a ciphertext y.

• D, the decryption algorithm, is a deterministic algorithm which takes a secret key

sk and ciphertext y to produce either a message x ∈ {0, 1}— or a special symbol

⊥ to indicate that the ciphertext was invalid.

We require that for all (pk, sk) which can be output by K (k), for all x ∈ {0, 1}— ,

and for all y that can be output by E pk (x), we have that Dsk (y) = x. We also require

that K , E , and D can be computed in polynomial time.

Prior to discussing the basic notion of indistinguishability of encryptions for asym-

metric (i.e., public-key) encryption, we describe the indistinguishability (IND)

game. In the IND game, the attacker is asked to provide two messages, m0 and

m1 . The challenger picks one of these messages at random and encrypts it, giving

the resulting ciphertext, y— , back to the attacker. The attacker then guesses which

message (i.e., m0 or m1 ) the challenger encrypted.

At ¬rst glance, this may seem trivial “ the attacker can just encrypt both m0 and

m1 to obtain y0 and y1 and compare whether

? ?

y0 = y— or y1 = y— .

Recall that E , the encryption algorithm, is probabilistic. In other words, encryption

of the same message twice is unlikely to result in the same ciphertext, and knowing

the encryption of a message may not help us recognise another encryption of the

same message.

De¬nition 2.1.12 describes the indistinguishability (IND) game.

3 In a chosen-plaintext attack (CPA), the adversary, A , is allowed to encrypt plaintexts of A ™s

choice. In the public-key setting, with the knowledge of the public key, A can compute a ciphertext

for any plaintext desired. Hence, in the de¬nitions of security under CPA, A is provided access to

the public key.

2.1 Mathematical Background 25

De¬nition 2.1.12 (The Indistinguishability Game) Let PE = (K , E , D) be the

asymmetric encryption scheme described in De¬nition 2.1.11. The IND game for an

attacker, A = (A1 , A2 ), consists of four major steps, as described below.

1. A challenger generates a random key-pair (pk, sk) by running the key generation

algorithm, K .

2. The attacker, A , runs A1 on the input k, which returns two messages m0 , m1 , as

well as some state information s.

3. The challenger chooses a bit, b ∈ {0, 1}. It computes the challenge ciphertext

y— = E (mb , pk).

4. A runs A2 on the input (y— , pk, s) . It returns a guess b for b.

A wins the game of b = b, and its advantage in playing the IND game is de¬ned to

be

1

AdvPE ,A (k) = | Pr[b = b] ’ |

2

De¬nition 2.1.13 describes security for the asymmetric (i.e., public-key) encryption.

De¬nition 2.1.13 (Security under IND-CPA [11]) PE = (K , E , D), an asym-

metric encryption scheme, is secure in the sense of indistinguishability (equiva-

lently [47], semantically secure) if for any probabilistic, polynomial time adversary

A = (A1 , A2 ), the following is negligible (in k):

AdvPE ,A (k) = 2 — |Pr[(pk, sk) ← K (k); (m0 , m1 , s) ← A1 (k, pk);

b ∈R {0, 1}; y ← E pk (mb ); b ← A2 (k, pk, y, s) : b = b ]| ’ 1

2.1.4.2 Encryption Schemes: Symmetric Setting

The de¬nition for a symmetric encryption scheme is given in De¬nition 2.1.14.

De¬nition 2.1.14 (A Symmetric Encryption Scheme [11]) A symmetric encryp-

tion scheme is given by a triple of algorithms, S E = (K , E , D), where

• K , the key generation algorithm, is a probabilistic algorithm that takes a secu-

rity parameter k and returns a symmetric encryption key sk.

• E , the encryption algorithm, is a deterministic algorithm that takes sk and a

message x ∈ {0, 1}— to produce a ciphertext y.

• D, the decryption algorithm, is a deterministic algorithm which takes sk and

ciphertext y to produce either a message x ∈ {0, 1}— or a special symbol ⊥ to

indicate that the ciphertext was invalid.

We require that for all sk which can be output by K (k), for all x ∈ {0, 1}— , and for

all y that can be output by Esk (x), we have that Dsk (y) = x. We also require that K ,

E , and D can be computed in polynomial time.

Security for symmetric encryption schemes is similar to that described for the asym-

metric encryption scheme described in De¬nitions 2.1.12 and 2.1.13.

26 2 Background Materials

2.1.4.3 Digital Signature Schemes

De¬nition 2.1.15 describes the digital signature scheme.

De¬nition 2.1.15 (A Digital Signature Scheme) A digital signature scheme is given

by a triple of algorithms, Σ = (K , G , V ), where

• K , the key generation algorithm, is a probabilistic algorithm that takes a secu-

rity parameter k and returns a pair (vk, sk) of matching veri¬cation and signing

keys.

• G , the signature algorithm, is a probabilistic algorithm that takes a signing key,

sk, and a message, x ∈ {0, 1}— , to produce a signature, S.

• V , the veri¬cation algorithm, is a deterministic algorithm which takes a veri¬-

cation key, vk, and signature, S, to output a ¬‚ag to indicate whether the signature

is valid or invalid.

We require that for all (pk, sk) which can be output by K (k), for all x ∈ {0, 1}— ,

and for all S that can be output by Gsk (x), we have that V pk (S) = Valid. We also

require that K , E , and V can be computed in polynomial time.

The standard de¬nition for the security of digital signature schemes was ¬rst given

by Goldwasser, Micali, and Rivest [48] where they consider the existential unforge-

ability4 under adaptive chosen-message attack5 (ACMA).

De¬nition 2.1.16 (Security under ACMA [48]) Σ = (K , G , V ), a signature scheme,

is secure in the sense of adaptive chosen message attack (ACMA) if for any proba-

bilistic, polynomial time forging algorithms F , the following is negligible (in k):