1 of 29

Attribute-Based Encryption

Brent Waters

2 of 29

Access Control

🗶

3 of 29

Access Control by Encryption

Idea: Need secret key to access data

SK

4 of 29

Realistic Data Sharing

Problem: Disconnect between policy and mechanism

OR

Professor

AND

CS255-TA

PhD

?

Kelly:

“Professor”

“Admissions”

Sarah:

“CS255-TA”

“PhD”

  • Burden on provider

5 of 29

A Fundamental Gap

OR

Professor

AND

CS255-TA

PhD

Complex

Infrastructure

  • Key Lookup
  • Group Key Management
  • Online-Service
  • Complex
  • Several Keys

6 of 29

A New Vision

OR

Professor

AND

CS255-TA

PhD

Attribute-Based Encryption

Complex

Infrastructure

OR

Professor

AND

CS255-TA

PhD

7 of 29

Attribute-Based Encryption: A New Perspective

Public Parameters

Access Predicate: f( )

f( )

SK

Cred.=X

If f(X)=1

8 of 29

Why Attribute-Based Encryption?

Late Binding Access Control:

e.g. Network Logs

9 of 29

Why Attribute-Based Encryption?

Late Binding Access Control:

e.g. Network Logs

2ef92a295cbb

98bc39dea94c

...

SRC IP=123.12.6.8

Date=12/5/07

  • Encrypt packet payload, tag with metadata

SK

Src:123.3.4.77 AND

Date: 12/5/07

  • Distribute capabilities later

10 of 29

Why Attribute-Based Encryption?

Efficiency:

OR

Dean Eng.

AND

Professor

C.S.

vs.

Scales with policy complexity

11 of 29

Why Attribute-Based Encryption?

AND

ACLU

?

Receiver Privacy:

Salary > 1M

12 of 29

Attribute-Based Encryption for Formulas [SW05]

PK

MSK

“CS255-TA”

“PhD”

“CS255-TA”

“Undergrad”

OR

Professor

AND

CS255-TA

PhD

✔

🗶

🗶

✔

✔

🗶

🗶

OR

Professor

AND

CS255-TA

PhD

SK

SK

Key Authority

✔

Line of Research: [SW05, GPSW06, BSW07, BW07, OSW07,KSW08…]

13 of 29

A First Approach

Question: Can we build attribute-based encryption from standard techniques?

Attempt: Public Key Encryption + Secret Sharing

14 of 29

Secret Sharing [S78,B78,BL86]

OR

A

AND

B

C

  • Ideas extend to more complex sharing

s

s

ShareA = s

ShareB = r

ShareC = s-r

  • Use finite field e.g. Zp

15 of 29

A First Approach

Combine S.S. and PKE

SKSarah:

“A”

SKKevin:

“B”

AND

A

B

PKA

SKB

PKB

SKA

EA(R)

EB(M-R)

R

?

M-R

M

Collusion Attack!

16 of 29

Collusion Attacks: The Key Threat

Kevin:

“CS255-TA”

“Undergrad”

OR

Professor

AND

CS255-TA

PhD

James:

“PhD”

“Graphics”

Need: Key “Personalization”

Tension: Functionality vs. Personalization

17 of 29

Elliptic Curve Techniques

G : multiplicative of prime order p. (Analogy: Zq*)

High Level: Single Multiplication

Key for satisfying functionality + personalization

​

Bilinear map e: G×G → GT

e(ga, gb) = e(g,g)ab ∀a,b∈Zp, g∈G

​

Intuitive Hardness Discrete Log:

Given: g, ga Hard to get: a

18 of 29

System Setup

19 of 29

Key Generation

SK

‘t’ ties components together

Personalization!

20 of 29

Key Personalization (Intuition)

SK

SK

Kevin:

“CS255-TA”

…

James:

“PhD”

…

Random t

Random t’

Components are incompatible

(Formal security proofs in papers)

21 of 29

Encryption

M

OR

y1

AND

y2

y3

n leaf nodes

y1, ... yn

f ( ) =

Share1=s

Share2=r

Share3=s-r

s

CT:

22 of 29

Making it work

CT:

Goal: Compute and cancel to get M

“CS255-TA”

“PhD”

Message Randomization

23 of 29

Making it work

CT:

“CS255-TA”

“PhD”

SK:

Message Randomization

Personalized Randomization

New goal: Personalized to user

Use Bilinear Map for Decryption

24 of 29

Making it work

OR

Professor

AND

CS255-TA

PhD

“CS255-TA”

“PhD”

  • Shares are personalized

(Use Bilinear-Map)

  • Linearly Combine

Personalized Randomization

25 of 29

Security

Theorem: System is (semantically) secure under chosen key attack

Number Theoretic Assumption:

Bilinear Diffie-Hellman Exponent [BBG05]

26 of 29

Attribute-Based Encryption Encryption Summary

Complex

Infrastructure

OR

Professor

AND

CS255TA

PhD

  • Tension: Functionality vs. Personalization

[SW05, GPSW06,PTMW06, BSW07, OSW07]

  • Fundamental Change: Public Key Cryptography

27 of 29

Other Advances

ABE from Learning with Errors GVW13

    • Quantum Resistance
    • Circuit Functionality

Registered ABE HLWW23

    • Removes central authority

28 of 29

FIPS and ABE?

29 of 29