boneh-franklin-ibe.ipynb

Kernel: SageMath 10.0

Connect: Boneh-Franklin Identity-Based Encryption

Module 07 | Real-World Connections

Show how pairings enable encryption where any string (email address) serves as a public key.

Introduction

In traditional public-key encryption, Alice needs Bob's public key certificate before she can encrypt a message to him. This requires a Public Key Infrastructure (PKI) -- certificate authorities, revocation lists, key servers.

Identity-Based Encryption (IBE) eliminates this overhead: Alice encrypts directly to Bob's identity string (email address, phone number, employee ID). No certificate needed.

The Boneh-Franklin scheme (2001) was the first practical IBE construction. It uses bilinear pairings as its core building block, the same pairings from Module 07.

The key insight: a trusted authority (the Private Key Generator, or PKG) holds a master secret and can derive any user's private key from their identity. This is a feature, not a bug, the PKG replaces the entire certificate authority infrastructure.

The Boneh-Franklin Scheme

Four algorithms:

Algorithm	Who Runs It	What It Does
Setup	PKG (trusted authority)	Generate master secret $s$, publish params $(P, sP)$
Extract	PKG	Derive user's private key $d_{\text{id}} = s \cdot H_1(\text{id})$
Encrypt	Anyone (sender)	Encrypt to identity string using only public params
Decrypt	User (recipient)	Decrypt using private key obtained from PKG

The pairing enables decryption: the recipient can reconstruct the same mask that the sender used, even though they hold different secrets.

# === Step 1: Setup. PKG generates master key and public parameters ===

# Supersingular curve for pairing
p = 467
E = EllipticCurve(GF(p), [1, 0])  # y^2 = x^3 + x
card = E.cardinality()
n = 13   # prime subgroup order
k = 2    # embedding degree
cofactor = card // n

# Extension field
F2.<a> = GF(p^k)
E_ext = E.change_ring(F2)

# Generator P in G1
while True:
    P = cofactor * E.random_point()
    if P != E(0) and n * P == E(0):
        break

P_ext = E_ext(P)

# Generator Q in G2 (for pairing computation)
cofactor_ext = E_ext.cardinality() // n
while True:
    Q_gen = cofactor_ext * E_ext.random_point()
    if Q_gen != E_ext(0) and n * Q_gen == E_ext(0):
        if P_ext.weil_pairing(Q_gen, n) != 1:
            break

# Master secret key
s = randint(1, n - 1)

# Master public key
P_pub = s * P  # sP, published
P_pub_ext = E_ext(P_pub)

print("=== PKG Setup ===")
print(f"Curve: y^2 = x^3 + x over GF({p})")
print(f"Subgroup order: n = {n}")
print(f"Generator P = {P}")
print(f"Master secret: s = {s} (kept secret by PKG)")
print(f"Master public key: P_pub = sP = {P_pub} (published)")

# === Hash functions ===

def hash_to_curve_id(identity, E, n, cofactor):
    """
    H1: {0,1}* -> G1
    Hash an identity string to a curve point in the n-torsion subgroup.
    """
    h = hash(f"IBE-H1:{identity}") % (10^6)
    for x_try in range(h, h + 1000):
        x = GF(p)(x_try)
        y_sq = x^3 + x
        if y_sq.is_square():
            y = y_sq.sqrt()
            pt = E(x, y)
            Q = cofactor * pt
            if Q != E(0):
                return Q
    return cofactor * E.random_point()

def hash_pairing_to_int(gt_element, n):
    """
    H2: G_T -> Z/nZ
    Hash a target group element to an integer for XOR masking.
    We use a simple hash for teaching purposes.
    """
    # Convert the field element to an integer via its polynomial representation
    coeffs = gt_element.polynomial().coefficients(sparse=False)
    h = sum(int(c) * (1000^i) for i, c in enumerate(coeffs))
    return h % n

# Test the hash functions
Q_bob = hash_to_curve_id("[email protected]", E, n, cofactor)
print(f"H1('[email protected]') = {Q_bob}")
print(f"Order: {Q_bob.order()} (should be {n})")

# Different identities map to different points
Q_alice = hash_to_curve_id("[email protected]", E, n, cofactor)
print(f"H1('[email protected]') = {Q_alice}")
print(f"Different from Bob's? {Q_bob != Q_alice}")

Step 2: Extract. PKG Derives Bob's Private Key

When Bob registers with the PKG (after authenticating his identity), the PKG computes:

$$d_{\text{Bob}} = s \cdot H_1(\text{"[email protected]"})$$

This is Bob's private key, a curve point that only the PKG can compute (because only the PKG knows $s$). The PKG sends $d_{\text{Bob}}$ to Bob over a secure channel.

Note: the PKG knows everyone's private key. This is the key escrow property of IBE. It is appropriate for enterprise settings where the organization should be able to recover encrypted data.

# === Step 2: Extract. Derive Bob's private key ===

bob_id = "[email protected]"
Q_bob = hash_to_curve_id(bob_id, E, n, cofactor)

# PKG computes Bob's private key
d_bob = s * Q_bob

print(f"Bob's identity: '{bob_id}'")
print(f"H1('{bob_id}') = Q_bob = {Q_bob}")
print(f"Bob's private key: d_bob = s * Q_bob = {d_bob}")
print(f"\nOnly the PKG (who knows s = {s}) can compute this.")
print(f"Bob receives d_bob over a secure channel.")

Step 3: Encrypt. Alice Sends a Message to Bob's Identity

Alice wants to encrypt message $m$ (an integer mod $n$ in our toy version) to Bob. She only needs:

• Bob's identity string: "[email protected]"

• The public parameters: $P$ and $P_{\text{pub}} = sP$

She does not need Bob's public key certificate!

Encryption:

1. Compute $Q_{\text{Bob}} = H_1(\text{"[email protected]"})$

2. Pick random $r \in \mathbb{Z}/n\mathbb{Z}$

3. Compute ciphertext: $C = (r \cdot P, \; m \oplus H_2(e(Q_{\text{Bob}}, P_{\text{pub}})^r))$

The mask $H_2(e(Q_{\text{Bob}}, P_{\text{pub}})^r)$ is the key: it depends on the pairing of Bob's identity-derived point with the master public key.

# === Step 3: Encrypt to Bob's identity ===

def ibe_encrypt(message_int, recipient_id, P, P_pub, E, n, cofactor):
    """
    Boneh-Franklin Encrypt.
    message_int: integer in [0, n-1]
    Returns: (U, V) where U = rP, V = m XOR H2(e(Q_id, P_pub)^r)
    """
    Q_id = hash_to_curve_id(recipient_id, E, n, cofactor)
    Q_id_ext = E_ext(Q_id)
    P_pub_ext = E_ext(P_pub)
    
    # Compute the pairing e(Q_id, P_pub)
    g_id = Q_id_ext.weil_pairing(P_pub_ext, n)  # in G_T
    
    # Random r
    r = randint(1, n - 1)
    
    # U = rP
    U = r * P
    
    # Mask = H2(e(Q_id, P_pub)^r)
    mask = hash_pairing_to_int(g_id^r, n)
    
    # V = m XOR mask
    V = (message_int ^^ mask) % n
    
    return (U, V, r)  # r returned for debugging only

# Alice encrypts a message to Bob
plaintext = 9  # message (integer mod n)

U, V, r_used = ibe_encrypt(plaintext, bob_id, P, P_pub, E, n, cofactor)

print(f"Alice encrypts to '{bob_id}'")
print(f"Plaintext:  m = {plaintext}")
print(f"Random r:   r = {r_used}")
print(f"Ciphertext: U = rP = {U}")
print(f"            V = m XOR H2(e(Q_bob, P_pub)^r) = {V}")
print(f"\nAlice needed: Bob's email + public params. No certificate!")

Step 4: Decrypt. Bob Uses His Private Key

Bob receives ciphertext $(U, V)$ and decrypts using his private key $d_{\text{Bob}} = s \cdot Q_{\text{Bob}}$:

$$m = V \oplus H_2(e(d_{\text{Bob}}, U))$$

Why does this work? The key identity is:

$$e(d_{\text{Bob}}, U) = e(s \cdot Q_{\text{Bob}}, r \cdot P) = e(Q_{\text{Bob}}, P)^{sr}$$

And Alice's mask was:

$$e(Q_{\text{Bob}}, P_{\text{pub}})^r = e(Q_{\text{Bob}}, s \cdot P)^r = e(Q_{\text{Bob}}, P)^{sr}$$

Both compute $e(Q_{\text{Bob}}, P)^{sr}$. Alice using $r$ and $sP$, Bob using $sQ_{\text{Bob}}$ and $rP$. Bilinearity is the magic that makes these two paths meet.

# === Step 4: Bob decrypts ===

def ibe_decrypt(U, V, d_id, n):
    """
    Boneh-Franklin Decrypt.
    U, V: ciphertext components
    d_id: user's private key (curve point)
    Returns: plaintext integer
    """
    d_id_ext = E_ext(d_id)
    U_ext = E_ext(U)
    
    # Compute e(d_id, U) = e(sQ, rP) = e(Q, P)^{sr}
    pairing_val = d_id_ext.weil_pairing(U_ext, n)
    
    # Recover mask
    mask = hash_pairing_to_int(pairing_val, n)
    
    # Recover plaintext
    m = (V ^^ mask) % n
    return m

# Bob decrypts
recovered = ibe_decrypt(U, V, d_bob, n)

print(f"Bob decrypts with his private key d_bob = {d_bob}")
print(f"Ciphertext: U = {U}, V = {V}")
print(f"Recovered plaintext: m = {recovered}")
print(f"Original plaintext:  m = {plaintext}")
print(f"Correct? {recovered == plaintext}")
print()

# Show why it works: both paths compute the same pairing value
Q_bob_ext = E_ext(Q_bob)
alice_pairing = Q_bob_ext.weil_pairing(P_pub_ext, n)^r_used  # e(Q, sP)^r
bob_pairing = E_ext(d_bob).weil_pairing(E_ext(U), n)          # e(sQ, rP)

print(f"Alice computed: e(Q_bob, sP)^r = {alice_pairing}")
print(f"Bob computed:   e(sQ_bob, rP)  = {bob_pairing}")
print(f"Same? {alice_pairing == bob_pairing}")
print(f"\nBilinearity: e(Q,P)^{s}*{r_used} = e(Q,P)^{s * r_used % n} (mod {n})")

# === Verify: wrong identity cannot decrypt ===

# Eve has a private key for a different identity
eve_id = "[email protected]"
Q_eve = hash_to_curve_id(eve_id, E, n, cofactor)
d_eve = s * Q_eve  # Eve's legitimate key for her own identity

# Eve tries to decrypt Bob's ciphertext
eve_attempt = ibe_decrypt(U, V, d_eve, n)

print(f"Eve ('{eve_id}') tries to decrypt Bob's ciphertext...")
print(f"Eve's decryption: {eve_attempt}")
print(f"Correct plaintext: {plaintext}")
print(f"Eve got the right answer? {eve_attempt == plaintext}")
print()
print("Eve's private key d_eve = s * H1('[email protected]') produces a")
print("different pairing value than d_bob = s * H1('[email protected]').")
print("The message was encrypted to Bob's identity, not Eve's.")

Concept Map: Module 07 to Boneh-Franklin IBE

Module 07 Concept	IBE Application
Bilinear map $e(aP, bQ) = e(P,Q)^{ab}$	Decryption works: $e(sQ, rP) = e(Q, sP)^r$
Hash-to-curve $H_1$	Map identity string to curve point $Q_{\text{id}}$
Pairing computation	Both encryption mask and decryption mask
Pairing-friendly curve	Required for efficient pairing computation
DLP hardness in $G_T$	Security: cannot recover $s$ from $e(Q, sP)$
Non-degeneracy	Different identities produce different pairing values

IBE is the canonical example of pairings enabling something impossible without them: no non-pairing-based IBE scheme existed before Boneh-Franklin.

Summary

Concept	Key idea
Setup	PKG publishes $(P, sP)$ and keeps $s$ secret
Extract	PKG computes $d_{\text{id}} = s \cdot H_1(\text{id})$ for each user
Encrypt	Sender computes mask $H_2(e(Q_{\text{id}}, sP)^r)$ using only public params
Decrypt	Recipient computes the same mask via $e(d_{\text{id}}, rP) = e(Q_{\text{id}}, P)^{sr}$
Bilinear "meeting point"	Alice knows $r$ and $sP$, Bob knows $sQ$ and $rP$, and both reach $e(Q, P)^{sr}$
Key escrow	The PKG can derive any user's private key, replacing PKI certificates entirely

IBE eliminates the need for PKI certificates. Anyone can encrypt to an email address without first obtaining the recipient's public key. The trade-off is key escrow: the PKG can derive any user's private key.

---

Back to Module 07: Bilinear Pairings