Source-linked AI summary
Attribute-Based Encryption for Circuits from Multilinear Maps
Amit Sahai, Brent Waters
TL;DR
General-circuit ABE remained difficult because prior constructions were essentially limited to fanout-one or NC1-style circuits and suffered from backtracking concerns. The paper introduces a multilinear-map construction using “move forward and shift,” achieving Key-Policy and Ciphertext-Policy ABE with selective security under a multilinear generalization of BDDH.
Problem
Prior ABE constructions were essentially limited to NC1 or fanout-one circuits, while achieving ABE for general circuits remained a central open challenge.
Method
The paper constructs circuit ABE from multilinear maps using a “move forward and shift” technique that prevents backtracking.
Results
The construction supports arbitrary-fanout circuits and both Key-Policy and Ciphertext-Policy ABE, with selective security under the decision k-multilinear assumption.
Takeaways & Limitations
Multilinear maps provide the paper’s route to general-circuit ABE by preventing reversal of the forward computation step used in decryption.
Takeaways & Limitations
Security is selective and relies on the decision k-multilinear assumption, with the setup fixing a maximum depth ℓ = k − 1.
Abstract
from arXiv · showhide
In this work, we provide the first construction of Attribute-Based Encryption (ABE) for general circuits. Our construction is based on the existence of multilinear maps. We prove selective security of our scheme in the standard model under the natural multilinear generalization of the BDDH assumption. Our scheme achieves both Key-Policy and Ciphertext-Policy variants of ABE.
1 Introduction
The paper addresses the difficulty of extending ABE beyond fanout-one circuits by introducing a multilinear-map methodology for arbitrary-fanout circuits. It presents Key-Policy and Ciphertext-Policy constructions with selective security under a multilinear BDDH-type assumption.
- Motivation: ABE generalizes public-key encryption by specifying who may decrypt through attributes, with Key-Policy and Ciphertext-Policy variants.In Key-Policy ABE, ciphertexts carry Boolean descriptors while keys are associated with access policies.
- Motivation: Existing ABE constructions were limited essentially to NC1, making general-circuit ABE a central open challenge.NC1 consists of logarithmic-depth circuits, equivalently polynomial-size Boolean formulas.
- Backtracking Attack: Backtracking attacks exploit satisfied and unsatisfied branches in fanout greater than one, allowing false satisfaction to propagate along another circuit path.In GPSW-style decryption, an OR gate can reveal values for an unsatisfied input, which becomes dangerous when that input feeds another gate.
- Scope: The main construction handles layered monotone circuits, while standard transformations and universal circuits extend functionality to general circuits and Ciphertext-Policy ABE.The setup parameters n and ℓ are polynomially bounded and fixed during system setup.
- Construction and Assumption: The construction uses multilinear maps and commits setup to a maximum circuit depth ℓ = k − 1, proving security under the decision k-multilinear assumption.The framework provides a sequence of groups supporting successive map operations, and the assumption generalizes decision BDH.
- Techniques: Its core technique, “move forward and shift,” prevents backtracking without relying on sophisticated linear secret-sharing schemes.For an OR gate, the forward-only map prevents the attacker from reversing the move-forward step; analogous mechanisms handle AND gates.
2 Preliminaries
The preliminaries reduce general Boolean circuits to monotone layered circuits and define the multilinear-group and circuit notation used by the construction. These restrictions preserve functionality with at most polynomial circuit-size overhead.
- General Circuits vs. Monotone Circuits: De Morgan transformations convert any Boolean circuit into an equivalent monotone circuit with negations only at input wires.The construction combines a circuit with its recursively negated counterpart.
- General Circuits vs. Monotone Circuits: The resulting monotone circuit has size at most twice the original and identical depth.Inputs correspond to attributes, including explicit attributes for negated attributes in the small-universe setting.
- Multi-linear Maps: The multilinear framework generates k prime-order groups and supports maps e_i,j: G_i × G_j → G_i+j whenever i + j ≤ k.Canonical generators and successive group levels support the construction’s bounded number of pairing operations.
- Multi-linear Maps: The decision k-multilinear problem asks whether a structured element in G_k can be distinguished from a random group element.The challenger samples the group sequence and random exponents before forming the challenge.
- Circuit Notation: The exposition restricts circuits to single-output, layered, monotone circuits whose gates are binary AND or OR gates.A circuit is represented as f = (n, q, A, B, GateType), with wires and gate-input functions explicitly defined.
- Circuit Notation: These circuit restrictions are mainly expository: general circuits can be recovered, and equivalent layered circuits require only polynomial-factor size increase.The paper states that the restrictions do not impact functionality.
3 Our Construction
The construction gives a Key-Policy ABE scheme for circuits, using multilinear maps and a public-index ciphertext format. Keys encode circuits, while decryption evaluates the circuit on the ciphertext descriptor and succeeds exactly when the output is 1.
- Construction overview: The scheme uses Key-Policy ABE: keys are associated with circuits f, ciphertexts with inputs x, and decryption succeeds when f(x) = 1.The ciphertext reveals x efficiently; only the message M is hidden.
- Construction overview: Setup fixes the input length n and maximum circuit depth ℓ, with circuits represented as layered circuits of that depth.The layered restriction is described as mainly simplifying exposition, while n and ℓ are polynomially bounded.
- Key generation: Key generation assigns randomness to wires and creates a header plus wire-specific components for input wires, OR gates, and AND gates.The secret key contains the circuit description, header component, and components for every wire.
- Decryption: Pairing operations move satisfied-wire values to the next group, while shift components produce the value required at the current wire.For an OR gate, either satisfied input can be used; for an AND gate, both inputs are required.
- Decryption: Decryption first computes a header value, then evaluates satisfied wires bottom-up so each depth-j wire combines values from depth j −1.For a satisfied wire w at depth j, the algorithm computes Ew = (g_j+1)^srw and ultimately tests the output against CM.
- Security mechanism: The construction prevents backtracking because pairing cannot be reversed from group Gj+1 to group Gj, blocking false satisfaction along higher-fanout paths.This mechanism addresses the attack that limits earlier constructions to fanout-one circuits.
4 Proof of Security
The proof reduces any selective-security attack on the ABE construction to solving a decision multilinear assumption. The simulator preserves depth-dependent invariants while generating keys and uses the challenge tuple to distinguish encryptions.
- Reduction: A polynomial-time attacker against depth-ℓ circuits yields a polynomial-time solver for the decision ℓ+1-multilinear assumption.The reduction is stated for selective security with monotonic circuit access structures.
- Initialization: The reduction receives group descriptions, g, gs, multilinear powers, and a challenge element T that is either structured or random.The simulator uses the supplied multilinear terms and iterated pairings during setup.
- Challenge ciphertext: The simulator generates the challenge ciphertext after the attacker declares x*, using the set of input indices where x* has value 1.If T is structured, the ciphertext encrypts 1; if T is random, it is an encryption of 0 with high probability.
- Key simulation: For each wire, the simulator maintains a depth-based invariant distinguishing the cases f_w(x*) = 0 and f_w(x*) = 1.At zero-valued wires, the simulated randomness contains multilinear challenge terms; at one-valued wires, it contains zero plus known randomization.
- Key simulation: Input, OR, and AND wire keys are generated separately, with cancellations enabling the simulator to compute required components from multilinear maps.The proof also notes that the relevant random-looking distributions hold perfectly over Z_p in the stated cases.
- Final step: The output-wire invariant enables a final cancellation when computing the header component, after which the reduction guesses whether T was structured or random from the adversary’s message guess.The reduction interprets a guess of 1 as evidence that T was structured and a guess of 0 as evidence that T was random.