07e-identity-based-encryption.ipynb

Kernel: SageMath 10.5

Notebook 07e: Identity-Based Encryption

Module 07. Bilinear Pairings

---

Motivating Question. To send Alice an encrypted email, you first need her public key. But how do you get it? You look it up in a directory, verify a certificate, check a chain of trust... What if you could just encrypt directly to [email protected], no certificate needed? Identity-based encryption (IBE) makes this possible, and bilinear pairings are the key ingredient.

---

Prerequisites. You should be comfortable with:

• Bilinear maps: $e(aP, bQ) = e(P, Q)^{ab}$ (Notebook 07a)

• Pairing-friendly curves (Notebook 07c)

• BLS signatures (Notebook 07d), IBE uses the same pairing machinery

Learning objectives. By the end of this notebook you will be able to:

1. Explain why IBE is useful and how it differs from traditional public-key encryption.

2. Implement the Boneh-Franklin IBE scheme step by step.

3. Verify correctness using bilinearity.

4. Identify the key escrow problem and understand mitigation strategies.

1. The Certificate Problem

In traditional public-key encryption (RSA, ElGamal, ECIES):

1. Bob generates a key pair $(sk, pk)$.

2. Bob registers $pk$ with a Certificate Authority (CA).

3. The CA issues a certificate binding Bob's identity to $pk$.

4. Alice fetches Bob's certificate, verifies the CA's signature, extracts $pk$.

5. Then Alice can encrypt.

This infrastructure (PKI) is complex, expensive, and fragile. Certificate revocation is notoriously hard.

Shamir's 1984 vision: What if Bob's identity string (email, phone number, employee ID) is his public key? Then Alice doesn't need certificates at all, she just encrypts to [email protected].

Traditional PKE	Identity-Based Encryption
Bob generates $(sk, pk)$	Trusted authority generates master params
CA certifies $pk$ to Bob's identity	Bob's identity is his public key
Alice needs Bob's certificate	Alice needs only Bob's identity string
Revocation via CRL/OCSP	Revocation via key epochs (e.g., [email protected]‖2026)

2. IBE Architecture

An IBE scheme has four algorithms:

Algorithm	Who runs it	What it does
Setup	Private Key Generator (PKG)	Generates master secret $s$ and public parameters
Extract	PKG	Derives a private key $d_{\text{ID}}$ from the master secret and identity string
Encrypt	Anyone (sender)	Encrypts a message to an identity string using only public params
Decrypt	Key holder	Decrypts using the extracted private key

The PKG (Private Key Generator) is a trusted authority, like a CA, but it issues private keys rather than certificates.

Crypto foreshadowing. The PKG knows everyone's private key, this is the key escrow problem. We'll discuss mitigations at the end. In Module 09, we'll see how threshold secret sharing can distribute the PKG's trust across multiple parties.

3. Boneh-Franklin IBE: Setup

Boneh and Franklin (2001) gave the first practical IBE scheme, using bilinear pairings. Let's build it step by step on our toy curve.

Setup: The PKG:

1. Chooses a pairing-friendly curve with groups $G_1, G_2, G_T$ of prime order $n$.

2. Picks generators $g_1 \in G_1$, $g_2 \in G_2$.

3. Picks a random master secret $s \in \mathbb{Z}/n\mathbb{Z}$.

4. Computes the master public key $P_{\text{pub}} = s \cdot g_2 \in G_2$.

5. Publishes $(G_1, G_2, G_T, e, g_1, g_2, P_{\text{pub}}, H_1, H_2)$ as public parameters.

Here $H_1: \{0,1\}^* \to G_1$ maps identity strings to curve points, and $H_2: G_T \to \{0,1\}^\ell$ extracts a key from a pairing output.

# === Boneh-Franklin IBE: Setup ===

# Same supersingular curve as previous notebooks
p = 467  # prime, p ≡ 3 mod 4
E = EllipticCurve(GF(p), [1, 0])  # y^2 = x^3 + x, supersingular
card = E.cardinality()
n = 13   # prime factor of |E|
k = 2    # embedding degree
cofactor = card // n

# Extension field for G2 and GT
F2 = GF(p^k, 'a')
E_ext = E.change_ring(F2)

# Find G1 generator
while True:
    g1 = cofactor * E.random_point()
    if g1 != E(0) and n * g1 == E(0):
        break

g1_ext = E_ext(g1)

# Find G2 generator (in extension field, linearly independent from G1)
cofactor_ext = E_ext.cardinality() // n
while True:
    g2 = cofactor_ext * E_ext.random_point()
    if g2 != E_ext(0) and n * g2 == E_ext(0):
        if g2.weil_pairing(g1_ext, n) != 1:
            break

# PKG's master secret
s = randint(1, n - 1)  # master secret
P_pub = s * g2          # master public key

print("=== PKG Setup ===")
print(f"Curve: y² = x³ + x over F_{p}")
print(f"Subgroup order: n = {n}")
print(f"Embedding degree: k = {k}")
print(f"G1 generator: g1 = {g1}")
print(f"G2 generator: g2 = {g2}")
print(f"\nMaster secret: s = {s}  (PKG keeps this secret!)")
print(f"Master public key: P_pub = s·g2 = {P_pub}")
print(f"\nPairing base: e(g1, g2) = {g1_ext.weil_pairing(g2, n)}")

4. Hash Functions

We need two hash functions:

• $H_1: \{0,1\}^* \to G_1$, maps an identity string to a point in $G_1$.

• $H_2: G_T \to \mathbb{Z}/n\mathbb{Z}$, derives a symmetric key from a pairing output.

In practice, $H_1$ is a hash-to-curve function and $H_2$ is a key derivation function (KDF). For our toy example, we'll use simplified versions.

def H1(identity_string, E, n, cofactor):
    """
    Hash an identity string to a point in G1.
    Simplified: hash the string, try x-coordinates until we find a point.
    """
    h = hash(identity_string) % (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()
            P = E(x, y)
            Q = cofactor * P
            if Q != E(0):
                return Q
    return cofactor * E.random_point()


def H2(gt_element, n):
    """
    Hash a GT element to Z/nZ (key derivation).
    Simplified: use Python's hash on the string representation.
    """
    return ZZ(hash(str(gt_element)) % n)


# Test H1: different identities map to different points
Q_alice = H1("[email protected]", E, n, cofactor)
Q_bob = H1("[email protected]", E, n, cofactor)
print(f"H1('[email protected]') = {Q_alice}")
print(f"H1('[email protected]')   = {Q_bob}")
print(f"Both have order {Q_alice.order()} (should be {n})")
print(f"Different identities → different points? {Q_alice != Q_bob}")

5. Key Extraction

When Bob wants his private key, he authenticates to the PKG (shows his passport, proves he owns [email protected], etc.). The PKG then computes:

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

This is Bob's private key, a point in $G_1$. The PKG sends it to Bob over a secure channel.

Misconception alert. "The PKG is like a CA." Not quite, a CA never sees your private key. The PKG computes your private key. This is a fundamental difference and the source of the key escrow problem.

def ibe_extract(identity, s, E, n, cofactor):
    """
    PKG extracts a private key for the given identity.
    d_ID = s * H1(identity)
    """
    Q_id = H1(identity, E, n, cofactor)
    d_id = s * Q_id
    return d_id


# Bob requests his private key from the PKG
bob_id = "[email protected]"
d_bob = ibe_extract(bob_id, s, E, n, cofactor)

print(f"Bob's identity: '{bob_id}'")
print(f"H1(Bob) = {H1(bob_id, E, n, cofactor)}")
print(f"Bob's private key: d_Bob = s · H1(Bob) = {d_bob}")
print(f"Order of d_Bob: {d_bob.order()} (should divide {n})")

Checkpoint 1. Key extraction is just scalar multiplication, exactly like BLS signing! In BLS, the signer computes $\sigma = sk \cdot H(m)$. In IBE, the PKG computes $d_{\text{ID}} = s \cdot H_1(\text{ID})$. The mathematical structure is identical; the meaning is different (signature vs. private key).

6. Encryption

Alice wants to send a secret message $m$ to Bob. She knows only:

• Bob's identity string [email protected]

• The public parameters $(g_1, g_2, P_{\text{pub}}, H_1, H_2)$

Encrypt(ID, $m$):

1. Compute $Q_{\text{ID}} = H_1(\text{ID}) \in G_1$.

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

3. Compute $U = r \cdot g_2 \in G_2$.

4. Compute the shared key: $\text{key} = H_2(e(Q_{\text{ID}}, P_{\text{pub}})^r)$.

5. Compute $V = (m + \text{key}) \bmod n$.

6. The ciphertext is $(U, V)$.

The crucial observation: Alice computes $e(Q_{\text{ID}}, P_{\text{pub}})^r$ using only public information, she never needs Bob's private key or even a certificate.

def ibe_encrypt(identity, message, g1_ext, g2, P_pub, E, E_ext, n, cofactor):
    """
    Encrypt a message (integer mod n) to an identity string.
    Returns ciphertext (U, V) where U ∈ G2 and V ∈ Z/nZ.
    """
    # Step 1: Hash identity to G1
    Q_id = H1(identity, E, n, cofactor)
    Q_id_ext = E_ext(Q_id)

    # Step 2: Random r
    r = randint(1, n - 1)

    # Step 3: U = r * g2
    U = r * g2

    # Step 4: Shared key from pairing
    pairing_val = Q_id_ext.weil_pairing(P_pub, n)  # e(Q_ID, P_pub)
    key = H2(pairing_val^r, n)                      # H2(e(Q_ID, P_pub)^r)

    # Step 5: Mask the message
    V = (message + key) % n

    return (U, V), r  # return r too for demonstration


# Alice encrypts a message to Bob
m = 7  # secret message (an integer mod 13)
(U, V), r_used = ibe_encrypt(bob_id, m, g1_ext, g2, P_pub, E, E_ext, n, cofactor)

print(f"=== Encryption ===")
print(f"Alice encrypts to identity: '{bob_id}'")
print(f"Plaintext message: m = {m}")
print(f"Random r = {r_used}")
print(f"\nCiphertext:")
print(f"  U = r·g2 = {U}")
print(f"  V = (m + key) mod n = {V}")
print(f"\nAlice used NO certificate and NO public key from Bob!")
print(f"She only needed the string '{bob_id}' and the public params.")

7. Decryption

Bob receives ciphertext $(U, V)$ and uses his private key $d_{\text{Bob}} = s \cdot H_1(\texttt{"[email protected]"})$.

Decrypt($d_{\text{ID}}$, $(U, V)$):

1. Compute the shared key: $\text{key} = H_2(e(d_{\text{ID}}, U))$.

2. Recover the message: $m = (V - \text{key}) \bmod n$.

Why does this work? Let's trace the math:

$$e(d_{\text{ID}}, U) = e(s \cdot H_1(\text{ID}),\; r \cdot g_2) = e(H_1(\text{ID}), g_2)^{sr}$$$$e(Q_{\text{ID}}, P_{\text{pub}})^r = e(H_1(\text{ID}),\; s \cdot g_2)^r = e(H_1(\text{ID}), g_2)^{sr}$$

Both equal $e(H_1(\text{ID}), g_2)^{sr}$! Bilinearity lets the decryptor's secret $s$ (inside $d_{\text{ID}}$) and the encryptor's randomness $r$ (inside $U$) combine, even though neither party knows the other's secret value.

def ibe_decrypt(d_id, ciphertext, E_ext, n):
    """
    Decrypt a ciphertext (U, V) using the extracted private key d_ID.
    """
    U, V = ciphertext

    # Step 1: Recover the shared key using the private key
    d_id_ext = E_ext(d_id)
    pairing_val = d_id_ext.weil_pairing(U, n)  # e(d_ID, U)
    key = H2(pairing_val, n)

    # Step 2: Unmask the message
    m = (V - key) % n
    return m


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

print(f"=== Decryption ===")
print(f"Bob uses his private key: d_Bob = {d_bob}")
print(f"Ciphertext: (U, V) = ({U}, {V})")
print(f"\nRecovered message: m = {m_recovered}")
print(f"Original message:  m = {m}")
print(f"Correct? {m_recovered == m}")

8. Correctness Verification

Let's explicitly verify that the pairing values match, this is the heart of why IBE works.

# Show the pairing equality explicitly
Q_bob = H1(bob_id, E, n, cofactor)
Q_bob_ext = E_ext(Q_bob)
d_bob_ext = E_ext(d_bob)

# Encryptor computes: e(Q_ID, P_pub)^r
enc_pairing = Q_bob_ext.weil_pairing(P_pub, n)^r_used

# Decryptor computes: e(d_ID, U) = e(d_ID, r*g2)
dec_pairing = d_bob_ext.weil_pairing(U, n)

print("=== Pairing Equality (Correctness Proof) ===")
print(f"\nEncryptor computes:")
print(f"  e(H1(ID), P_pub)^r = e(H1(ID), s·g2)^r")
print(f"                     = e(H1(ID), g2)^(s·r)")
print(f"                     = {enc_pairing}")
print(f"\nDecryptor computes:")
print(f"  e(d_ID, U)         = e(s·H1(ID), r·g2)")
print(f"                     = e(H1(ID), g2)^(s·r)")
print(f"                     = {dec_pairing}")
print(f"\nEqual? {enc_pairing == dec_pairing}")
print(f"\nBilinearity lets s and r 'meet' inside the pairing!")

Checkpoint 2. The correctness of IBE rests on the same bilinearity property as BLS verification:

• BLS: $e(sk \cdot H(m), g_2) = e(H(m), sk \cdot g_2)$, the signer's secret moves from one argument to the other.

• IBE: $e(s \cdot H_1(\text{ID}), r \cdot g_2) = e(H_1(\text{ID}), s \cdot g_2)^r$, the PKG's secret and the encryptor's randomness combine.

In both cases, bilinearity is the "bridge" that connects values computed by different parties.

9. Wrong Identity Cannot Decrypt

What if Eve (with identity [email protected]) tries to decrypt a message encrypted for Bob?

# Eve gets her own private key from the PKG
eve_id = "[email protected]"
d_eve = ibe_extract(eve_id, s, E, n, cofactor)

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

print(f"Eve's identity: '{eve_id}'")
print(f"Eve's private key: d_Eve = {d_eve}")
print(f"\nEve tries to decrypt Bob's ciphertext:")
print(f"  Recovered: {m_eve}")
print(f"  Actual:    {m}")
print(f"  Correct?   {m_eve == m}")
print(f"\nEve gets: e(s·H1(Eve), r·g2) = e(H1(Eve), g2)^(sr)")
print(f"Bob gets: e(s·H1(Bob), r·g2) = e(H1(Bob), g2)^(sr)")
print(f"\nH1(Eve) ≠ H1(Bob), so the pairing values differ → wrong key!")

10. Multiple Recipients Demo

Let's show the complete flow with multiple users.

# Complete demo: PKG extracts keys for 3 users, messages encrypted/decrypted
users = ["[email protected]", "[email protected]", "[email protected]"]
private_keys = {}

print("=== PKG Extracts Private Keys ===")
for uid in users:
    d = ibe_extract(uid, s, E, n, cofactor)
    private_keys[uid] = d
    print(f"  {uid}: d = {d}")

print(f"\n=== Encrypt to Each User ===")
messages = {"[email protected]": 3, "[email protected]": 7, "[email protected]": 11}

ciphertexts = {}
for uid, msg_i in messages.items():
    ct, _ = ibe_encrypt(uid, msg_i, g1_ext, g2, P_pub, E, E_ext, n, cofactor)
    ciphertexts[uid] = ct
    print(f"  To {uid}: m={msg_i} → CT=({ct[0]}, {ct[1]})")

print(f"\n=== Each User Decrypts ===")
for uid in users:
    ct = ciphertexts[uid]
    m_dec = ibe_decrypt(private_keys[uid], ct, E_ext, n)
    original = messages[uid]
    print(f"  {uid}: decrypted {m_dec}, original {original}, correct? {m_dec == original}")

print(f"\n=== Cross-Decryption (Should Fail) ===")
# Bob tries to decrypt Alice's message
m_wrong = ibe_decrypt(private_keys["[email protected]"], ciphertexts["[email protected]"], E_ext, n)
print(f"  Bob decrypts Alice's CT: {m_wrong} (original: {messages['[email protected]']}, correct? {m_wrong == messages['[email protected]']})")

11. The Key Escrow Problem

The elephant in the room: the PKG knows everyone's private key. It can decrypt any message in the system.

Issue	Explanation
Eavesdropping	PKG can decrypt all ciphertexts
Impersonation	PKG can forge decryption keys for any identity
Single point of failure	Compromise of $s$ breaks everything
Legal compulsion	Government can force PKG to reveal keys

Mitigations

Strategy	How It Helps
Threshold PKG	Master secret $s$ is shared among $t$-of-$n$ servers; no single server knows $s$
Certificateless PKE	User combines PKG-derived key with self-generated key; PKG alone can't decrypt
Key epochs	Use identity "[email protected]‖2026-Q1", keys expire naturally, limiting damage window
Audit logging	PKG logs all key extractions; anomalous requests are flagged

# Demonstrate the key escrow problem:
# The PKG can decrypt anything!

# Suppose Alice encrypts a secret to Bob
secret_msg = 9
(U_secret, V_secret), _ = ibe_encrypt(
    "[email protected]", secret_msg, g1_ext, g2, P_pub, E, E_ext, n, cofactor
)

print("=== Key Escrow Demonstration ===")
print(f"Alice encrypts m={secret_msg} to [email protected]")
print(f"Ciphertext: (U, V) = ({U_secret}, {V_secret})")

# PKG can re-derive Bob's key (it knows s)
d_bob_rederived = ibe_extract("[email protected]", s, E, n, cofactor)
m_spied = ibe_decrypt(d_bob_rederived, (U_secret, V_secret), E_ext, n)

print(f"\nPKG re-derives Bob's key: d_Bob = {d_bob_rederived}")
print(f"PKG decrypts: m = {m_spied}")
print(f"Correct? {m_spied == secret_msg}")
print(f"\n⚠ The PKG can read ALL messages, this is the key escrow problem!")
print(f"Unlike traditional PKE, users do NOT generate their own private keys.")

Checkpoint 3. Key escrow is not a bug, it's inherent to IBE's design. If the identity string alone determines the public key, then whoever can compute $s \cdot H_1(\text{ID})$ can decrypt. The question is whether the trade-off (no certificates) is worth the trust assumption (honest PKG). For enterprise email encryption within a company, it often is. For end-to-end encryption between strangers, it's not.

12. Key Revocation via Time Periods

An elegant feature of IBE: natural key revocation. Instead of complex certificate revocation lists (CRLs), encode a time period into the identity:

$$\text{ID} = \texttt{"[email protected]‖2026-Q1"}$$

Bob gets a new private key each quarter. Old keys automatically stop working for new ciphertexts.

# Time-based key revocation demo
bob_q1 = "[email protected]||2026-Q1"
bob_q2 = "[email protected]||2026-Q2"

# PKG extracts keys for different periods
d_bob_q1 = ibe_extract(bob_q1, s, E, n, cofactor)
d_bob_q2 = ibe_extract(bob_q2, s, E, n, cofactor)

print(f"Bob's Q1 key: {d_bob_q1}")
print(f"Bob's Q2 key: {d_bob_q2}")
print(f"Different? {d_bob_q1 != d_bob_q2}")

# Encrypt to Q2 identity
msg_q2 = 5
(U_q2, V_q2), _ = ibe_encrypt(
    bob_q2, msg_q2, g1_ext, g2, P_pub, E, E_ext, n, cofactor
)

# Bob's Q2 key decrypts correctly
m_q2 = ibe_decrypt(d_bob_q2, (U_q2, V_q2), E_ext, n)
print(f"\nEncrypted to '{bob_q2}': m = {msg_q2}")
print(f"Decrypt with Q2 key: {m_q2} (correct? {m_q2 == msg_q2})")

# Bob's Q1 key cannot decrypt Q2 messages!
m_wrong_q = ibe_decrypt(d_bob_q1, (U_q2, V_q2), E_ext, n)
print(f"Decrypt with Q1 key: {m_wrong_q} (correct? {m_wrong_q == msg_q2})")
print(f"\n→ Old keys automatically expire! No revocation lists needed.")

13. IBE vs. Traditional PKE

Feature	Traditional PKE (RSA/EC)	IBE (Boneh-Franklin)
Public key	Random (must be looked up)	Identity string (known a priori)
Certificates needed?	Yes (PKI infrastructure)	No
Private key generation	User generates own	PKG derives from master secret
Key escrow	No (user controls key)	Yes (PKG knows all keys)
Revocation	CRLs, OCSP (complex)	Time-based identities (elegant)
Encryption offline?	Need certificate first	Yes, only need identity string
Mathematical basis	Integer factoring / ECDLP	Bilinear pairings (BDHP)
Key size overhead	None	Pairing parameters must be published

Crypto foreshadowing. The Boneh-Franklin IBE can be extended to Hierarchical IBE (HIBE) where key extraction is delegated down an organizational tree. For instance, a company PKG derives a department key, and the department derives employee keys, without the root PKG being involved in every extraction. HIBE connects to the lattice-based constructions in Module 08, where Gentry, Peikert, and Vaikuntanathan showed how to build IBE from lattice assumptions, achieving post-quantum security.

14. Exercises

Exercise 1 (Worked): Full IBE Round Trip

Problem. Set up a fresh IBE system. Extract private keys for [email protected] and [email protected]. Have Alice encrypt the message $m = 10$ to Bob. Have Bob decrypt. Verify correctness.

Solution:

# Exercise 1: Worked solution

# Fresh setup (reusing curve params)
s_ex = randint(1, n - 1)
P_pub_ex = s_ex * g2
print(f"PKG master secret: s = {s_ex}")
print(f"Master public key: P_pub = {P_pub_ex}")

# Extract keys
d_alice_ex = ibe_extract("[email protected]", s_ex, E, n, cofactor)
d_bob_ex = ibe_extract("[email protected]", s_ex, E, n, cofactor)
print(f"\nAlice's key: {d_alice_ex}")
print(f"Bob's key:   {d_bob_ex}")

# Alice encrypts to Bob
m_ex = 10
(U_ex, V_ex), _ = ibe_encrypt(
    "[email protected]", m_ex, g1_ext, g2, P_pub_ex, E, E_ext, n, cofactor
)
print(f"\nAlice encrypts m={m_ex} to [email protected]")
print(f"Ciphertext: U={U_ex}, V={V_ex}")

# Bob decrypts
m_dec_ex = ibe_decrypt(d_bob_ex, (U_ex, V_ex), E_ext, n)
print(f"\nBob decrypts: m = {m_dec_ex}")
print(f"Correct? {m_dec_ex == m_ex}")

# Alice cannot decrypt (wrong key)
m_alice_try = ibe_decrypt(d_alice_ex, (U_ex, V_ex), E_ext, n)
print(f"\nAlice tries to decrypt: m = {m_alice_try} (correct? {m_alice_try == m_ex})")

Exercise 2 (Guided): Broadcast Encryption to a Mailing List

Problem. You want to encrypt a message so that anyone on [email protected] can decrypt. With IBE, simply encrypt to that identity string. The PKG extracts one shared private key for the mailing list and distributes it to all team members.

Implement this:

1. Extract a private key for "[email protected]".

2. Encrypt $m = 4$ to "[email protected]".

3. Show that each team member (who has the shared key) can decrypt.

4. Show that an outsider cannot.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Extract the team's private key
# d_team = ibe_extract("[email protected]", s, E, n, cofactor)

# TODO 2: Encrypt m = 4 to the team identity
# (U_team, V_team), _ = ibe_encrypt(
#     "[email protected]", 4, g1_ext, g2, P_pub, E, E_ext, n, cofactor
# )

# TODO 3: Decrypt with the team key (simulating each member having it)
# for name in ["Alice", "Bob", "Charlie"]:
#     m_dec = ibe_decrypt(d_team, (U_team, V_team), E_ext, n)
#     print(f"{name} decrypts: {m_dec}")

# TODO 4: Show an outsider ([email protected]) cannot decrypt
# d_dave = ibe_extract("[email protected]", s, E, n, cofactor)
# m_dave = ibe_decrypt(d_dave, (U_team, V_team), E_ext, n)
# print(f"Dave (outsider) decrypts: {m_dave} (correct? {m_dave == 4})")

Exercise 3 (Independent): Attribute-Based Identity

Problem.

1. Instead of email addresses, use attribute strings as identities. Define three roles: "role:admin", "role:engineer", "role:intern".

2. Extract private keys for each role.

3. Encrypt a confidential message ($m = 12$) to "role:admin".

4. Show that only the admin key can decrypt.

5. Discuss: how could you encrypt to "admin OR engineer" using IBE? What are the limitations compared to full attribute-based encryption (ABE)?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
IBE Setup	PKG generates master secret $s$, publishes $P_{\text{pub}} = s \cdot g_2$
Key Extraction	$d_{\text{ID}} = s \cdot H_1(\text{ID})$, PKG derives private key from identity
Encryption	$U = r \cdot g_2$, key $= H_2(e(H_1(\text{ID}), P_{\text{pub}})^r)$, uses only public info
Decryption	key $= H_2(e(d_{\text{ID}}, U))$, bilinearity ensures same key
Key escrow	PKG knows all private keys, mitigate with threshold PKG or certificateless PKE
Revocation	Encode time periods in identity: "[email protected]‖2026-Q1"

This concludes Module 07 on bilinear pairings. We've gone from the abstract definition of bilinear maps, through the Weil pairing and pairing-friendly curves, to two major applications: BLS signatures and identity-based encryption. The common thread is bilinearity, the ability to "move" scalars between pairing arguments, connecting values computed by different parties.

---

Module complete! Next: Module 08: Lattices and Post-Quantum Cryptography