1 of 32

Registered Attribute-Based Encryption

Susan Hohenberger George Lu Brent Waters David Wu

2 of 32

Public Key Encryption

pk

sk

ct

3 of 32

Attribute Based Encryption [SW05, GPSW06]

pk

sk_{faculty + CS}

sk_{faculty + math}

sk_{student + CS}

ct_{CS AND faculty}

One inconvenience of PKE, especially when it’s so widespread, is that there’s a lot of public keys to keep track of. For every person you want to communicate to, you need to know their public key.

It’d be a lot more convenient to be able to multiple individuals through a single public key.

A solution to this problem is notion of attribute-based encryption, where, instead of encrypting to individuals, you have a master public key, and an authority which can issue secret keys corresponding to attributes. For example, maybe you have a school, and the attributes you care about are if you’re of student or a teacher and your department. Ciphertexts are encrypted to a policy, say you only want faculty in CS to read this message, and *anyone* who has a key which fulfills the policy can read the message. Also note that for security, other users, even if they have the attributes in combination, should not be able to decrypt

Describe collusion

Boolean function

Bring in key escrow here as

4 of 32

Key Exfiltration Problem

pk

sk_{faculty + CS}

sk_{faculty + math}

sk_{student + CS}

msk

5 of 32

Registration Based Encryption [GHMR18]

mpk’’

mpk

mpk'

pk₁

pk₂

pk₃

sk₁

sk₂

sk₃

id₁

id₃

id₂

ct_id₁

No Master Secret!

6 of 32

“Trivial” RBE

mpk’’

mpk

mpk'

pk₁

pk₂

pk₃

sk₁

sk₂

sk₃

id₁

id₃

id₂

ct_id₁

mpk independent of number of users!

7 of 32

Central Authority vs Key Curator

Computes compact master keys
Security holds even with access to curator state
Requires interaction

Computes compact master keys
Internal state compromises security
Noninteractive key issuing

8 of 32

Registered Attribute Based Encryption

mpk

_{faculty + CS}

_{faculty + math}

_{student + CS}

ct_{CS AND faculty}

9 of 32

Results

Registered Attribute-Based Encryption for bounded users

From composite order bilinear groups
Monotone boolean formulas policies

Registered Attribute-Based Encryption for unbounded users

From obfuscation
General circuits policies

10 of 32

Improvement from Prior Work

Monotone Boolean Formulas
Concrete efficiency
Black box

Identities/Point Functions
Large ciphertexts
Obfuscation or hash garbling

[GHMR18, GHM⁺19, GV20, CES21]

Construction 1

11 of 32

Limitations

Bounded Users
Structured Reference String
Quadratic CRS and curator state

Unbounded Users
Uniform Random String
Linear curator state

Construction 1

[GHMR18, GHM⁺19, GV20, CES21]

12 of 32

Background

Scheme constructed in composite order bilinear groups

Composite Order

Bilinear

13 of 32

Slotted Aggregation

mpk’’

mpk

mpk'

mpk

14 of 32

Slotted Aggregation

mpk

…

15 of 32

Roadmap

Attribute Based Encryption

1-User Registered ABE

Semihonest L-User Registered ABE

Malicious L-User Registered ABE

16 of 32

ABE in Bilinear Groups [GPSW06,LOS⁺10]

Encryption:

Ciphertext:

e(g,g)^αs

e(g,h)^t^s

e(g,U_ρ(x))^ts

g^αh^t

g^t

U_w^t : w ∈ S

μ⋅ e(g,g)^αs

g^s

h^s^xU_w_x^s

h

e(g,g)^α

U_w = g^u^w : w ∈ U

Decryption:

g

Conjunction Policies ∧ w_x : x ∈ [N]

*Replace additive secret sharing with linear secret sharing to support monotone Boolean formula

e(g,h)^t^s

The starting point of our construction is going to be an ABE scheme

[Lewko, Okamoto, Sahai, Takashima, and Waters]

As a bit of a disclaimer, for simplicity, what I’m showing here omits some randomization terms that would be needed to show security.

First we have to generate a description of our group.

A bunch of group elements are generated, and unless otherwise noted, any new letters are going to be drawn uniformly from the group or ZN if its an exponent.

First off, we have some group elements involved in encryption and decryption

This Is what our ciphertext looks like when encrypting a message mu

How decryption proceeds is that you’ll notice mu is blinded by this term in the target group. The ciphertext gives us gs, so in order to remove is, we just need to pair it with a g alpha. But g alpha never actually appears alone

Where this exponent t is the master secret key

Single Conjunction

17 of 32

ABE in Bilinear Groups [GPSW06,LOS⁺10]

Encryption:

Ciphertext:

e(g,g)^αs

e(g,h)^t^s

e(g,U_ρ(x))^ts

g^αh^t

g^t

U_w^t : w ∈ S

μ⋅ e(g,g)^αs

g^s

h^s^xU_w_x^s

h

e(g,g)^α

U_w = g^u^w : w ∈ U

Decryption:

g

Conjunction Policies ∧ w_x : x ∈ [N]

*Replace additive secret sharing with linear secret sharing to support monotone Boolean formula

e(g,h)^t^s

g^s

e(g,U_ρ(x))^ts

The starting point of our construction is going to be an ABE scheme

[Lewko, Okamoto, Sahai, Takashima, and Waters]

As a bit of a disclaimer, for simplicity, what I’m showing here omits some randomization terms that would be needed to show security.

First we have to generate a description of our group.

A bunch of group elements are generated, and unless otherwise noted, any new letters are going to be drawn uniformly from the group or ZN if its an exponent.

First off, we have some group elements involved in encryption and decryption

This Is what our ciphertext looks like when encrypting a message mu

How decryption proceeds is that you’ll notice mu is blinded by this term in the target group. The ciphertext gives us gs, so in order to remove is, we just need to pair it with a g alpha. But g alpha never actually appears alone

Where this exponent t is the master secret key

Single Conjunction

18 of 32

ABE in Bilinear Groups [GPSW06,LOS⁺10]

Encryption:

pk

Ciphertext:

e(g,g)^αs

g^αh^t

g^t

U_w^t : w ∈ S

μ⋅ e(g,g)^αs

g^s

h^s^xU_w_x^s

g^s

h

e(g,g)^α

U_w = g^u^w : w ∈ U

Decryption:

sk

g

Conjunction Policies ∧ w_x : x ∈ [N]

*Replace additive secret sharing with linear secret sharing to support monotone Boolean formula

The starting point of our construction is going to be an ABE scheme

[Lewko, Okamoto, Sahai, Takashima, and Waters]

As a bit of a disclaimer, for simplicity, what I’m showing here omits some randomization terms that would be needed to show security.

First we have to generate a description of our group.

A bunch of group elements are generated, and unless otherwise noted, any new letters are going to be drawn uniformly from the group or ZN if its an exponent.

First off, we have some group elements involved in encryption and decryption

This Is what our ciphertext looks like when encrypting a message mu

How decryption proceeds is that you’ll notice mu is blinded by this term in the target group. The ciphertext gives us gs, so in order to remove is, we just need to pair it with a g alpha. But g alpha never actually appears alone

Where this exponent t is the master secret key

Single Conjunction

19 of 32

1-User Registered ABE

sk

sk_{faculty + math}

msk

pk

hsk

crs

faculty +

math

mpk

ct_{faculty OR CS}

ct_{faculty AND CS}

20 of 32

1-User Registered ABE

U_w^t =1

g^u^w : w ∈ U

ABE.pk

U_w = g^u^w

U_w = 1

R = g^r

mpk

R = g^r

w₁ ∧ w₂ ∧ w₃ ∧ …

∧ R

21 of 32

Extending to L-User (Key Aggregation)

Idea –multiply mpk’s of 1-user scheme together!

pk_i = ({U_i,w },R_i )

Compact

Deterministic

22 of 32

Cross-Term Cancellation

e( , )

e( , ) =

e(g,R₂)^v^t

R₂^t

User 2

g^v

e(g,R₁)^v^t

e(g,R₃)^v^t

g^t

g^t³

g^t¹

R₁^t²

R₃^t²

²

e( , )

·

²

Conceptually similar to techniques used for constructing vector commitments [CF11] or batch arguments [WW22]

R^t= g^rt= (g^t)^r

23 of 32

Cross Term Cancellation

R₃^t²= g^r³^t²= (g^t²)^r³

U_3,w^t²= g^u^3,w^t²

crs

24 of 32

Key Validation

R_i =

mpk

???

g^rⁱ

mpk'

Q_i = P_i^rⁱ

crs

P_i

25 of 32

Key Validation

T_i =

mpk

???

g^rⁱ

mpk'

26 of 32

Registered ABE Security

mpk

_{faculty + CS}

_{faculty + math}

_{student + CS}

ct_{CS AND faculty}

m₀, m₁

m_b

crs

27 of 32

Security Proof

_{“Normal” Slot}

_{“Semi-Functional” Slot}

_{“Semi-Functional” Ciphertext}

_{“Normal” Ciphertext}

To execute our security proof, we’re going to use the dual-system methodology, which has been used in proving some crypto primitives including many of the prior works on non-registered ABE. So in this framework, we’re going to introduce the idea of semi-functional slots and ciphertexts. What does it mean for either a key or slot to be semi-functional? Well as you’d expect, a key registered to a normal slot will be able to properly decrypt a normal ciphertext. And a semi-functional slot matched with a normal ciphertext or vice versa can also decrypt properly. But! When a user attempts to use a semi-functional key to decrypt a semi-functional ciphertext, it fails.

Underneath the hood, if you remember from much earlier in the talk, the way these semi-functional slots and ciphertexts are made is composite order…

28 of 32

Security Proof

??

29 of 32

Security Proof

ct_{CS AND faculty}

_{faculty + CS}

_{student + CS}

30 of 32

Conclusion

Defined registered ABE
Construct first registered ABE schemes

First registered scheme to make black box use of crypto
Registered ABE for general circuits

Followup Works

Registered Functional Encryption from iO [DP23, FFM⁺23]
Registered Inner Product Predicate Encryption from pairing [FFM⁺23]

Open Questions

Large Attribute Universe registered ABE?
Generic transformation from X to registered X?

31 of 32

Upcoming Work

Improved Asymptotic and Concrete Efficiency

Prime Order Construction
Nearly-Linear CRS

U_i^t^j = g^uⁱ^t^j: i ≠ j ∈ [n]

U_k^t^k = g^u^k^t^k: k ∈ [n]

u_i ,t_i = a^dⁱ

= g^a^di+dj

= g^a^2dk

d_i + d_j ≠ 2d_k

O(n^1+o(1))

32 of 32

Thank you!

Read our paper on eprint 2022/1500