Paper reference: Identity-Based Encryption from the Weil Pairing | SpringerLink

Known Public Encryption Scheme  #

• Setup: Generate  global system parameters and a master-key

• Extract: use the master-key to generate the private-key  corresponding to an public-key string $ID ∈ \{0,1\}^*$

• Enc: encrypt M with ID → C

• Dec: decrypt C with private-key

Application#

(interesting)

Revocation of Public Keys#

“One could potentially make this approach more granular by encrypting e-mail for Bob using “bob@hotmail.com ‖ current-date”. This forces Bob to obtain a new private key every day.” (Boneh and Franklin, p. 215)

“This approach enables Alice to send messages into the future: Bob will only be able to decrypt the e-mail on the date specified by Alice” (Boneh and Franklin, p. 215)

Delegation of Decryption Keys#

1. bind <pk,sk> pairs with dates so that private-key can be stored in a vulnerable device: only thoses pairs are compromised and the Master-key is unharmed.
2. delegations of duties or other title as a skill to distribute private keys.

Construction#

preparation#

Bilinear Map:  e.g. Weil pairing#

, where $G_1$ and $G_2$ are two CYCLIC groups of some large prime order $p$ .

“In our system, G1 is the group of points of an elliptic curve over Fp and G2 is a subgroup of F∗p2 . Therefore, we view G1 as an additive group and G2 as a multiplicative group.” (Boneh and Franklin, p. 216)

• Bilinear $e(aP,bQ) =e(P,Q)^{ab} \; for \; all \; P,Q∈G_1 \; and \; all \; a,b ∈ Z$

• DH problem is hard in $G_1$

Properties of the Weil Pairing#

Build:

where prime $p$ satisfies $p =2 \; (mod \; 3) \; and \; p=6q-1 \; for \; some \; prime \; q$

Syntax#

• Setup:  k -> sys param (publicly shared) | master key (owned by PKG (“Private Key Generator” ))

• **Extract(master-key K,string ID) **=> private decryption key d.> ID is used as a public key    

• Enc/Dec

Secure Models#

• IND-ID-CCA: “adaptive chosen ciphertext attack”(Boneh and Franklin, p. 218)

• ID-OWE(one-way encryption): Given random public key $K_{pub}$ and ciphertext C which is the encryption of a random message M using $K_{pub}$ , A’s goal is to recover M.

models above allow A to conduct multi-round queries of <ID,d(private key)> pairs;

Scheme#

MapToPoint(string ID)=> Point#

$G: \; \{0,1\}^* \rightarrow \mathbb{F}_b$ , where in the security analysis  G is viewed as a random oracle.

1. Compute $y_0 = G(ID)$  and $y_0 \rightarrow E:\;x_0=(y^2_0 -1)^{1/3} =(y^2_0-1)^{(2p-1)/3}\;mod\;p$

2. return $Q_{ID} = 6(x_0,y_0) ∈ E/\mathbb{F}_b$

Basic IBE (BasicIdent)#

security parameter: $k$

Setup#

Step 1: Choose a large k-bit prime p such that p = 2 mod 3 and p = 6q − 1 for some prime q > 3. Let E be the elliptic curve defined by $y^2 = x^3 + 1$  over $\mathbb{F}_b$ . Choose an arbitrary $P ∈ E/\mathbb{F}_p$  of order q.

Step 2: Pick a random $s ∈ Z^*_q$  and set $P_{pub} = sP$ .

Step 3: Choose a cryptographic hash function $H: \; F_{p^2} → \{0, 1\}^n$  for some n. Choose a cryptographic hash function $G: \; \{0, 1\}^∗ → \mathbb{F}_p$. The security analysis will view H and G as random oracles.

output: system params :=$<p,n,P,P_{pub},G,H>$ , master-key : $s∈\mathbb{Z}_q$ picked in Step 2.

Message space is $M =\{0,1\}^n$

Ciphertext space is $C= E/\mathbb{F}_b \times \{0,1\}^n$  

Extract(string ID)#

Step 1. $Q_{ID} = MapToPoint(ID)$

Step 2. private key $d_{ID}=sQ_{ID}$, where s is the master key.

Encrypt#

Decrypt#

“Let C = 〈U, V 〉 ∈ C be a ciphertext encrypted using the public key ID. If U ∈ E/Fp is not a point of order q reject the ciphertext. Otherwise, to decrypt C using the private key dID compute:” (Boneh and Franklin, p. 222)

proof:

IND-CCA Security: enhanced by Fujisaki-Okamoto transform#

Fujisaki-Okamoto transform#

Suppose $<PEnc,PDec>$ is a public key encryption scheme.H and G are hash functions(viewed as random oracles): $H: \{0,1\}^n \times \{0,1\}^n \rightarrow \mathbb{F}_q$ , $G: \{0,1\}^n \rightarrow \{0,1\}^n$

Comparing with conventional Hybrid Encryption, FO transform  surpasses as follows:

• IND-CCA Security
• using Hash functions to blind random seeds and message
• check keys before decryption

Encrypt#

Notice that $g^r_{ID} =e(Q_{ID,P_{pub}})^r$  binds with both the message M and the random seed $\sigma$ ,functioning as $H(\sigma,M)$ as that above.

Decrypt: receive C=<U,V,W>#

1. Check if $U ∈ E/\mathbb{F}_p$ is not a point of order q, otherwise reject C

2. Compute $\sigma = V \oplus H(e(d_{ID},U))$

3. Decrypt $M=W \oplus G(\sigma)$

4. re-compute and check   $r=H(\sigma,M) == U =rP$