Unbounded Distributed Broadcast Encryption and Registered ABE from Succinct LWE

We construct distributed broadcast encryption and registered attribute-based encryption (ABE) that support an arbitrary polynomial of users from the succinct LWE assumption. Specifically, if we take 𝜆 to be the security parameter and 𝑁 to be the number of users, we obtain the following:

• We obtain a distributed broadcast encryption scheme where the size of the public parameters, user public/secret keys, and ciphertexts are optimal (i.e., have size poly(𝜆, log 𝑁 )). Security relies on the poly(𝜆, log 𝑁 )-succinct LWE assumption. Previously, this was only known from indistinguishability obfuscation or witness encryption. All constructions that did not rely on these general tools could only support an a priori bounded number of users.

• We obtain a key-policy registered ABE scheme that supports arbitrary bounded-depth Boolean circuit policies from the poly(𝜆, 𝑑, log 𝑁 )-succinct LWE assumption in the random oracle model, where 𝑑 is the depth of the circuit computing the policy. The public parameters, user public/secret keys, and ciphertexts have size poly(𝜆, 𝑑, log 𝑁 ), which are optimal up to the poly(𝑑) factor. This is the first registered ABE scheme with nearly-optimal parameters. All previous schemes (including constructions based on indistinguishability obfuscation, witness encryption, or evasive LWE) either have ciphertexts that scale with the policy size and attribute length, or can only support a bounded number of users (with long public parameters and public keys that scale with the number of users).

a target vector z ∈ Z 𝑛 𝑞 , we write y ← B -1 (z) to denote sampling y ∈ Z 𝑚 𝑞 from a discrete Gaussian distribution conditioned on By = z. We write G to denote the standard gadget matrix [MP12].

ℓ-succinct LWE. Our constructions rely on the succinct LWE assumption introduced by Wee [Wee24]. For a parameter ℓ, the ℓ-succinct LWE assumption asserts that the following distributions are computationally indistinguishable: