Chapter 6 - Ciphertext-Policy Attribute-Based Encryption (CP-ABE)

Why Traditional Crypto Doesn't Work in Cloud

Traditional cryptographic methods are not suitable for outsourced data in cloud environments.

Symmetric Encryption Issues

• Key distribution - difficult to securely share keys among many users
• Key revocation - challenging to revoke access without re-encrypting everything

Asymmetric Encryption Issues

• Slower performance - computationally expensive
• Renders multiple copies of ciphertext - much more storage needed to store CTs, requires re-encryptions when there is an update of the plain data

Think of it like this: If you want to share a file with 100 people using traditional encryption, you'd need to either share one key with everyone (risky) or encrypt the file 100 times with different keys (inefficient).

• ถ้าอาจารย์อยากแชร์ไฟล์ให้ทุกคนในห้อง จะ Encrypt ด้วย Key ของใครล่ะ?
  • ใช้ Public Key อาจารย์? → แล้วคนที่จะ Decrypt เอา Private Key จารย์มาจากไหน
  • แต่ถ้าใช้ Individual key ของนักเรียน โอโห้ ต้องมีกี่ copies of file วะ
    • More time of computation
    • Session Key ก็ไม่เวิร์ค ถ้ามีคน Withdraw course ล่ะ
• ก็เลยมีความคิดใหม่ก็คือใช้ Attribute-based นั่นเอง!!! จะเรียนกันวันนี้

What is Ciphertext-Policy Attribute-Based Encryption (CP-ABE)?

Key Characteristics

• Type of identity-based encryption
  • Uses one public key for the entire system
  • Master private key used to make more restricted private keys
• Very expressive rules for which private keys can decrypt which ciphertexts

Core Components

• Private keys have "attributes" or labels
  • Example: {SIIT student, CPE, 3rd Year, enroll > 90 credits}
• Ciphertexts have decryption policies
  • Example: (IT dept. AND manager) OR marketing

Attribute = characteristic of an object

Analogy: Think of attributes like security badges. Your private key is a collection of badges (SIIT student, CPE major, 3rd year). A ciphertext is like a locked room that requires certain badges to enter (must be IT dept AND manager, OR be in marketing).

Remote File Storage Challenges

Traditional Challenges

• Scalability
• Reliability
• Security (the main concern)

Server-Mediated Access Control

Good:

• Flexible access policies

Bad:

• Data vulnerable to compromise
• Must trust security of server

The server acts as a gatekeeper, but what if the gatekeeper is compromised?

Encrypting Files (Traditional Approach)

More secure, but loss of flexibility:

• New key for each file:
  • Must be online to distribute keys
• Many files with same key:
  • Fine-grained access control not possible

Fine-grained access control

• The ability to enforce the access privilege to the individual user.
• Fine-grained คือ ชื่อของ access control ที่ใช้ ความสามารถของ ACLs (Access Control List
  • Enforce the AC policy based on attributes of users (userID, grade, ...)
• อันนี้แหละที่สามารถตั้งค่าได้ใน Google Cloud Storage
• Uniform (Coarse-grained) AC ตรงกันข้ามกันกับ Fine-grained นะคับ คือ เราจะไม่สามารถระบุสิทธิการเข้าถึงของแต่ละไฟล์ใน bucket ได้ มันจะระบุสิทธิได้ทั้ง bucket เลย (หรือที่เรียกว่า bucket level permission) โดยที่จะมีผลกับทุกไฟล์ใน bucket นั้นๆ เลยเท่านั้น
  • Enforce the access privilege to the group of users.
  • Enforce or define the policy based on role.

CP-ABE: The Solution

The Wishlist (What we want)

• Encrypted files for untrusted/semi-trusted storage
• Setting up keys is offline (no need for constant online presence)
• No online, trusted party mediating access to files or keys
• Highly expressive (meaningful access policy) and fine-grained access policies (specify individual user access)
  • access = read/write

How CP-ABE Achieves This

CP-ABE provides Cryptographic-based Access Control = Encryption + Access Control (Authorization)

• User private keys given list of "attributes"
  • The key is generated from a set of attributes
  • Example: Key = {SIIT student, CPE, 3rd Year, enroll > 90 credits}
  • SIIT = Attribute Authority (AA)
• Files are encrypted under "policy" over those attributes
  • Policy to encrypt files
• Can only decrypt if attributes satisfy policy

Example Scenario

PK (Public Key)
MSK (Master Secret Key)

SK_Sarah: "manager", "IT dept." <- (These are attributes)
SK_Kevin: "manager", "sales"

Policy: (IT dept. AND manager) OR marketing

จะเป็นแบบนี้เสมอ Leave node เป็น attribute, แล้วเชื่อมด้วย logical operator

• Sarah can decrypt ✓ (has "IT dept." AND "manager")
• Kevin cannot decrypt ✗ (has "manager" but not "IT dept.", and not in "marketing")

Collusion Attacks: The Key Threat

What is a Collusion Attack?

• Important potential attack
• Users should not be able to combine keys
• Essential, almost defining property of ABE
• Main technical trick of CP-ABE scheme: preventing collusion

Example of Collusion Attack

SKSarah: "A", "C"
SKKevin: "B", "D"

Policy: A AND B

Question: Can Sarah and Kevin combine their keys to decrypt?

Answer: NO! CP-ABE prevents this.

A Misguided Approach (Why Simple Solutions Don't Work)

If we simply used separate public key encryption for each attribute:

PKA  PKB  PKC  PKD
SKA  SKB  SKC  SKD

M = M₁ + M₂
C = (EA(M₁), EB(M₂))

Sarah could decrypt $E_A(M_1)$ and Kevin could decrypt $E_B(M_2)$, then they could combine to get $M$! This is why collusion resistance is crucial.

Mathematical Foundation

Symbol Definitions

Background

$|G| = |G_T| = p$
$g \in G, \langle g \rangle = G$
$e : G \times G \to G_T$
$\forall a, b \in \mathbb{Z}^p, \quad e(g^a, g^b) = e(g,g)^{ab}$

Bilinearity Property: This property allows us to "move" exponents around in pairings, which is crucial for the decryption process.

CP-ABE Scheme Details

In CP-ABE, we have attribute authority, which need to generate PK and MSK (Initialization phase)

MSK is needed to generate users’ secret key. And will be distributed (SK) to each user. Which is different นะ (แต่ละ $SK$ อะ) เพราะว่าแต่ละ user มี attribute ที่ต่างกัน เช่น (studentID)

Setup

Random values chosen from $\mathbb{Z}^p$:
$\boxed{\alpha, \beta \xleftarrow{R} \mathbb{Z}^p}$
$\boxed{PK = (g, g^\beta, e(g,g)^\alpha)}$
$\boxed{MSK = (\beta, g^\alpha)}$

KeyGen(MK, S)

The key generation algorithm takes as input:

• A set of attributes $S$
• Outputs a key that identifies with that set

The algorithm:

1. Chooses a random $r \in \mathbb{Z}_p$
2. Then random $r_j \in \mathbb{Z}_p$ for each attribute $j \in S$
3. Computes the key as:

$\boxed{SK = \left(D = g^{(\alpha+r)/\beta}, \quad \forall j \in S : \quad D_j = g^r \cdot H(j)^{r_j}, D'_j = g^{r_j}\right)}$

Key Insight: The random value $r$ "binds" all key components together. Each user gets a different random $r$, making keys from different users incompatible for combination.

Encrypt(PK, M, T)

The encryption algorithm encrypts a message $M$ under the tree access structure $T$.

For each node $x$ in the tree, the algorithm chooses a polynomial $q_x$ such that:

• The degree $d_x$ of polynomial $q_x$ is one less than the threshold value $k_x$ of that node
• That is, $d_x = k_x - 1$

Starting with the root node $R$:

1. Algorithm chooses a random $s \in \mathbb{Z}_p$ and sets $q_R(0) = s$
2. Then chooses $d_R$ other points of the polynomial $q_R$ randomly to define it completely

For any other node $x$:

• Sets $q_x(0) = q_{\text{parent}(x)}(\text{index}(x))$
• Chooses $d_x$ other points randomly to completely define $q_x$

Let $Y$ be the set of leaf nodes in $T$. The ciphertext is then constructed by:

$\boxed{CT = \left(\mathcal{T}, \quad \tilde{C} = Me(g,g)^{\alpha s}, \quad C = h^s, \quad \forall y \in Y : \quad C_y = g^{q_y(0)}, C'_y = H(\text{att}(y))^{q_y(0)}\right)}$

How it works: The secret $s$ is "shared" across the access tree using polynomial secret sharing. Only if you have enough attributes to satisfy the policy can you reconstruct $s$.

Decrypt(CT, SK)

We first define a recursive algorithm DecryptNode(CT, SK, x) that takes as input:

• A ciphertext $CT = (\mathcal{T}, \tilde{C}, C, \forall y \in Y : C_y, C'_y)$
• A private key SK associated with a set $S$ of attributes
• A node $x$ from $\mathcal{T}$

If the node $x$ is a leaf node, let $i = \text{att}(x)$ and define:

If $i \in S$, then:

$\boxed{\text{DecryptNode}(CT, SK, x) = \frac{e(D_i, C_x)}{e(D'_i, C'_x)}}$
Expanding this:
$= \frac{e(g^r \cdot H(i)^{r_i}, h^{q_x(0)})}{e(g^{r_i}, H(i)^{q_x(0)})}$
$= e(g,g)^{rq_x(0)}$

If $i \notin S$, then DecryptNode(CT, SK, x) = $\perp$.

No pairing → no reconstruction: Without the matching attribute, the user cannot compute the necessary pairing value.

Decryption Process

The user computes the pairing:
$e(C_i, D_i) = e(H(A_i)^s, H(A_i)^{(\alpha+r)/\beta})$
By bilinearity:
$e(C_i, D_i) = e(H(A_i), H(A_i))^{s(\alpha+r)/\beta}$
After reconstructing the access tree using Lagrange interpolation, the user obtains:
$e(C, g^\alpha) = e(g^s, g^\alpha) = e(g,g)^{\alpha s}$
Finally, the user computes:
$\boxed{M = C' \cdot e(C, g^\alpha)^{-1}}$

Pairing Operations

What is a Pairing Operation?

A pairing function maps two elements from a cyclic group $G_1$ to another group $G_2$:

$e : G_1 \times G_1 \to G_2$

It satisfies the key bilinearity property:

$\boxed{e(g^a, g^b) = e(g,g)^{ab}}$

This means:

• If we take two values $g^a$ and $g^b$ in $G_1$, applying the pairing function gives a result that is equivalent to exponentiation in $G_2$.

Example Calculation

Let's assume the following values for a small cryptographic system:

• Prime order $p = 101$ (to keep calculations simple)
• Generator $g = 2$ in group $G_1$
• Random exponents $a = 5, b = 7$

Step 1: Compute Values in $G_1$
$A = g^a \mod p = 2^5 \mod 101 = 32$
$B = g^b \mod p = 2^7 \mod 101 = 128 \mod 101 = 27$
Now we have $A = g^a = 32$ and $B = g^b = 27$.

Step 2: Compute Pairing Directly

Using the pairing property:
$e(A, B) = e(g^a, g^b) = e(g,g)^{ab}$
We compute the exponent:
$ab = 5 \times 7 = 35$
Now, applying pairing $e(g,g)$:
$e(g,g)^{35} = 2^{35} \mod 101$
We compute $2^{35} \mod 101$:
$2^{35} \mod 101 = 97$
So, $e(32, 27) = 97$

Why is Pairing Important?

Pairing helps in CP-ABE for:

1. Verification – Ensuring a user's attributes satisfy the access policy.
2. Decryption – Allowing only authorized users to compute the correct decryption key.

At a leaf node with attribute $i$, decryption computes:

$\text{DecryptNode}(x) = \frac{e(D_i, C_x)}{e(D'_i, C'_x)} = e(g,g)^{rq_x(0)}$

This succeeds only if:

• the user possesses attribute $i$
• the secret key contains the matching components $(D_i, D'_i)$

If $i \notin S$:

$\text{DecryptNode}(x) = \perp$

Pairings ensure that only valid attributes produce valid shares!

Computation Cost of Pairing

Pairing operations are computationally expensive compared to:

• Exponentiation operations in $G_1$ and $G_2$
• Multiplications in the group

ตารางข้างล่างนี้จำให้ได้นะ

Since decryption in CP-ABE requires multiple pairings, optimizing these operations is crucial.

Policy Features

Leaf Nodes

• Test for presence of string attribute in key
• Also numerical attributes and comparisons
  • Example: hire_date < 2002, exec. level >= 5

Internal Nodes

• AND gates
• OR gates
• Also k of n threshold gates (e.g., "2 of 3")

Example Policy Tree

ACP1
├── OR
    ├── 2 of 3
    │   ├── exec. level >= 5
    │   ├── sales
    │   └── IT dept.
    └── AND
        ├── manager
        └── OR
            ├── marketing
            └── hire date < 2002

Reading the policy: "You can decrypt if you are (executive level 5 or higher, OR in sales, OR in IT dept - at least 2 of these 3) OR (you are a manager AND (in marketing OR hired before 2002))."

CP-ABE (เพิ้มตเิม)

• Cryptographic-based Access Control

• Find-grained AC

  • Enforce (policy) through user attributes

• It combines AC policy + Encryption

  • Yes, be we use policy to encrypt the data!

• Enforace AC policy over traditional encryption, AES, RSA, ECC → Encryption + Access policy

• One-to-many

• Costs: Pairing Operation > Exponentiation > Multiplication

• Encrypt Data and shared on cloud storage to share to multiple users

• What algorithms to be used? Fast, Secure, and Fine-grained!

Data Encryption

คำตอบมาตรฐานในงานจริงคือ Hybrid Encryption:
🔐 โครงสร้างที่นิยมใช้

• ใช้ AES เข้ารหัสไฟล์จริง (เร็วมาก เหมาะกับไฟล์ใหญ่)
  • $\mathrm{Enc}_{\text{AES/ChaCha20}}(M, \text{SymKey}) = CT_M$

• ใช้ CP-ABE เข้ารหัส AES key อีกที

• โดยฝัง policy ไว้ใน ciphertext

เก็บ:
Encrypted file (AES)
Encrypted AES key (CP-ABE)
✅ ทำไมต้องแบบนี้?
CP-ABE (pairing-based crypto) → ช้า ถ้าเอาไปเข้ารหัสไฟล์ใหญ่ตรง ๆ
AES → เร็วมาก
รวมกัน = Fast + Secure + Fine-grained ✔️

แล้วถ้า Revoke ล่ะ?

Revocation (user) in CP-ABE

• #MidtermExam ของปีที่แล้ว
• Any user is revoked?
  → Yes, but not for free 😅
• ปัญหา: CP-ABE แบบพื้นฐาน ไม่มี revocation ในตัว
• วิธีตรงไปตรงมาที่สุด:
  • ต้อง Re-encrypt
    • สร้าง SymKey ใหม่
    • Encrypt ข้อมูลใหม่ด้วย AES
    • Encrypt SymKey ใหม่ด้วย CP-ABE policy ที่ ตัด user ที่โดน revoke ออก (ก็คือต้องเปลี่ยนเป็น $T’$)
    • AA updates secret keys (SKs) of all active users and redistributes to them.
• สรุป:

If a user is revoked, the data owner needs to re-encrypt the data (or at least the key).

ถ้าจะเขียนให้ดูวิชาการขึ้นนิด:

• Revocation usually requires:
  • Re-keying and re-encryption, or
  • Using advanced schemes (e.g., attribute expiration, proxy re-encryption, or time-based attributes)

Revocation (Attribute) in CP-ABE

• ใน CP-ABE:
  • Policy อยู่ใน ciphertext
  • User ถือ secret key ที่ผูกกับ set of attributes
• ถ้า revoke แค่ attribute เดียว (เช่น studentNumber):
  • ผู้ใช้หลายคนอาจมี attribute นี้
  • แต่เรา ไม่อยาก revoke ทุกคน แค่บางคน
    → ดังนั้น ลบ attribute ออกจากระบบเฉย ๆ ไม่พอ

1. นิยาม attribute ใหม่ (versioning)
   • เช่น:
     • เดิม: studentNumber
     • ใหม่: studentID_v2
2. Update policy:
   • จาก $T$ → $T'$
   • เปลี่ยนให้ใช้ studentID_v2 แทน studentNumber
3. Re-encrypt:
   • สร้าง SymKey ใหม่
   • Encrypt ข้อมูลใหม่ด้วย AES
   • Encrypt SymKey ใหม่ด้วย CP-ABE ภายใต้ policy $T'$
4. AA (Attribute Authority)
   • แจก secret keys ใหม่ให้ เฉพาะผู้ใช้ที่ยัง valid
   • คนที่โดน revoke จะ ไม่ได้ attribute เวอร์ชันใหม่ → ถอดรหัสไม่ได้
     สรุป:

Attribute revocation in basic CP-ABE requires re-keying, policy update, and re-encryption.

Version อาจารย์

• If the revoked attribute is used in any T, you need to update T and re-encrypt on ciphertext encrypted by T.

Encryption and Decryption Details

Encryption

• Use general secret sharing techniques to model policy
• One ciphertext component per leaf node
• Size of CT is proportional to number of leaf nodes (number of attributes) in the Policy

Decryption

• Uses Lagrange interpolation "in the exponents"

Why "in the exponents"? We're working with encrypted values like $g^s$, not $s$ directly. Lagrange interpolation allows us to reconstruct the secret from shares even when those shares are "hidden" in exponents.

Highlights From Our Scheme: Private Key Generation

The Binding Mechanism

$\text{desired attributes: } x_1, x_2, \ldots x_n \in {0,1}^*$

$r, r_{x_1}, r_{x_2}, \ldots r_{x_n} \xleftarrow{R} \mathbb{Z}^p$

$SK = \left(g^{(\alpha+r)/\beta}, \quad g^r \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}, \quad \vdots \quad g^r \cdot H(x_n)^{r_{x_n}}, g^{r_{x_n}}\right)$

Key points:

• "Binds" key components to each other (through the shared random $r$)
• Makes components from different keys incompatible
• Key to preventing collusion attacks

Why this works: Every key component contains the secret random value $r$. Since Sarah's $r_{\text{Sarah}}$ is different from Kevin's $r_{\text{Kevin}}$, their key components won't work together when trying to decrypt.

CP-ABE Advantages and Disadvantages

Advantages

• Support fine-grained Access Control
• Flexible and Scalable key management (each user has only one key)
• Multiple user access (with no 3rd party online mechanism)
• Data owner can define his/her own policy to encrypt the data

Disadvantage

• Public key encryption (a kind of) - slow performance
• Not suitable for encrypting big files

Solution: In practice, CP-ABE is often used to encrypt a symmetric key, which is then used to encrypt the actual large file. This hybrid approach combines the flexibility of CP-ABE with the efficiency of symmetric encryption.

CP-ABE Performance

Encryption Performance

• Encryption performance is based on:
  • Size of AC policy (number of attributes)
  • File size

Attribute or User Revocation - Drawbacks

What if there is an attribute or user revoked?

• Re-encrypt all ciphertexts (containing revoked attributes) = Re-encryption cost
• Re-generate key to all users whose key contains revoked attributes = Re-key generation cost → Re-distribute keys

This is a significant limitation in dynamic environments where users frequently join and leave.

Implementation: The cp-abe Toolkit

Command Examples

$ cpabe-setup
 
$ cpabe-keygen -o sarah_priv_key pub_key master_key \
  sysadmin it_dept 'office = 1431' 'hire_date = 2002'
 
$ cpabe-enc pub_key security_report.pdf \
  "(sysadmin and (hire_date < 2005 or security_team)) or \
   2 of (executive_level >= 5, audit_group, strategy_team))"

Performance Benchmarks

Benchmarked on 64-bit AMD 3.7 GHz workstation

• Essentially no overhead beyond group operations in PBC library

Availability

• Available as GPL source at Advanced Crypto Software Collection (ACSC)
• New project to bring very recent crypto to systems researchers
• Bridge the gap between theory and practice
• Total of 8 advanced crypto projects currently available
• http://acsc.csl.sri.com

Security

Proven secure, including collusion resistance

The scheme makes two main assumptions:

• Assumes random oracle model
• Assumes generic group model

Generic Group Model

• "Black box" heuristic similar to random oracle model
• Good future work: scheme without this assumption

These are cryptographic assumptions that essentially say "the only way to break this is by brute force" - which is computationally infeasible for properly chosen parameters.

Attribute Based Encryption: Related Work

• Has additional policy hiding property, but needs online, semi-trusted server to perform encryption

References

[1] Sahai, Waters. Eurocrypt 2005.
[2] Pirretti, Traynor, McDaniel, Waters. CCS 06.
[3] Goyal, Pandey, Sahai, Waters. CCS 06.
[4] Kapadia, Tsang, Smith. NDSS 07.

Summary

CP-ABE provides a powerful solution for fine-grained access control in cloud storage:

✅ What it solves:

• Flexible, expressive access policies
• One key per user (scalable key management)
• Offline key setup
• No trusted online mediator
• Collusion resistance

⚠️ Limitations:

• Slower than symmetric encryption
• Revocation is costly
• Not ideal for very large files (use hybrid encryption)

Best use case: Encrypting data with complex, attribute-based access requirements in untrusted cloud environments.