Registration Model for Functional Encryption: Linear Functions with Access Control

Computing on Encrypted Data — Without the Authority

Functional encryption (FE) lets a key for a function $f$ turn a ciphertext of $x$ into exactly $f(x)$ — and nothing else. Its most practical workhorse is inner-product FE (IPFE): messages and keys are vectors, and decryption reveals $\ip{\vecx}{\vecy}$. That single capability covers weighted means, polynomial evaluation, thresholds, biometric matching, and nearest-neighbour search — and it bootstraps richer classes like quadratic functions.

But classical FE carries a heavy assumption: a central authority holds a master secret key and mints every function key. That authority can decrypt everything — the key-escrow problem. The registration model removes it: users generate their own keys and register with a transparent key curator that holds no secret.

Here’s the catch this paper tackles. Registration had only been achieved for predicates — access control that reveals data all-or-nothing. Actual computation on encrypted data in the registration model — inner products, and inner products with access control — was open.

This work answers yes: the first registered IPFE and registered attribute-based IPFE (plus a general construction from indistinguishability obfuscation), all without a trusted authority.

The Registration Model

A one-time trusted setup samples a common reference string $\crs$. To join, a user samples its own $(\pk,\sk)$ and sends $\pk$ together with a function $f_\pk$ to the key curator. The curator’s job is purely deterministic bookkeeping — it holds no secret, so anyone could play the role: it aggregates each $(\pk, f_\pk)$ into the master public key $\mpk$ and hands the user a short helper decryption key $\hsk$.

The bar for “efficient” is sharp: the secret keys, master public key, and helper keys must be polylogarithmic in the number of users $L$ — i.e. $\poly(\secp, \ell_f, \log L)$ — and each user needs only $O(\log L)$ helper-key updates over the system’s lifetime. Encryption needs only $\mpk$ (not the big $\crs$), keeping it as fast as ordinary IPFE.

As is now standard, it suffices to build a slotted registered FE — where $L$ is fixed at setup and everyone registers in one shot — and then lift it to the dynamic version with a power-of-two transformation that costs only an $O(\log L)$ overhead.

Starting Point: Plain IPFE — and the Escrow

The classic IPFE of Abdalla, Bourse, De Caro, and Pointcheval works over a prime-order group:

\[\mpk=(g,\, g^{\vecalpha}),\qquad \ct=(g^{s\vecalpha+\vecx},\, g^s),\qquad \sk_{\vecy}=\ip{\vecalpha}{\vecy}.\]

To decrypt, raise $g^{s\vecalpha+\vecx}$ to $\vecy$ to get $g^{s\ip{\vecalpha}{\vecy}+\ip{\vecx}{\vecy}}$, strip the mask $g^{s\ip{\vecalpha}{\vecy}}$ using $g^s$ and the key $\ip{\vecalpha}{\vecy}$, and read off $\ip{\vecx}{\vecy}$ by a small discrete log.

The escrow lives in one place: the secret key $\sk_{\vecy}=\ip{\vecalpha}{\vecy}$ needs the master secret $\vecalpha$. In the registration model, the user must somehow get the benefit of that key without anyone holding $\vecalpha$. The fix unfolds over four attempts.

Building Registered IPFE in Four Attempts

Attempt 1 — one user

The decryptor doesn’t actually need $\sk_{\vecy}=\ip{\vecalpha}{\vecy}$; it only needs the mask $g^{s\ip{\vecalpha}{\vecy}}$. And in the registration model the master public key is allowed to depend on the registered vector $\vecy$. So let the user pick $r$, publish $\pk=g^r$, keep $\sk=r$, and have aggregation produce

\[\mpk=\bigl(g,\, g^{\vecalpha},\, W=g^{\,r+\ip{\vecalpha}{\vecy}}\bigr),\qquad \ct=\bigl(g^{s\vecalpha+\vecx},\, g^s,\, W^s=g^{\,sr+s\ip{\vecalpha}{\vecy}}\bigr).\]

The user computes $g^{sr}$ from $g^s$ and $r$, divides it out of $W^s$, and recovers the mask $g^{s\ip{\vecalpha}{\vecy}}$. No master secret needed. For a single user, done.

Attempt 2 — many users, naively

The obvious extension aggregates everyone into one $W$:

\[W=\prod_{i} g^{\,r_i+\ip{\vecalpha}{\vecy_i}} = g^{\sum_i r_i + \sum_i\ip{\vecalpha}{\vecy_i}}.\]

This is broken. The vectors aren’t tied to their owners, so honest secret keys can be re-pointed:

Attempt 3 — bind the vectors, then pair

Fix the binding with per-user randomness $\beta_i$ baked into the $\crs$ (as $g^{\beta_i}$, $g^{\beta_i\vecalpha}$, $g^{1/\beta_i}$). Now $\pk_i=g^{\beta_i r_i}$ and

\[W=\prod_{i} g^{\,\beta_i(r_i+\ip{\vecalpha}{\vecy_i})},\qquad \ct=\bigl(g_T^{s},\, g_T^{s\vecalpha+\vecx},\, W^s\bigr),\quad g_T=e(g,g).\]

Each user’s thread is now separated by its own $\beta_i$ — but the price is that unmasking needs a pairing. User $i$ pairs $W^s$ with $g^{1/\beta_i}$:

\[e(W^s,\, g^{1/\beta_i}) = g_T^{\,sr_i}\cdot g_T^{\,s\ip{\vecalpha}{\vecy_i}}\cdot \underbrace{\prod_{j\neq i} g_T^{\,s\beta_j r_j/\beta_i}\cdot \prod_{j\neq i} g_T^{\,s\beta_j\ip{\vecalpha}{\vecy_j}/\beta_i}}_{\textsf{cross terms}}.\]

The user strips $g_T^{sr_i}$ using $r_i$ — but the cross terms from all the other slots are still in the way. Removing them is the final hurdle.

Attempt 4 — cancel the cross terms via registration

The elegant move: make each user help future decryptors cancel its contribution. The $\crs$ gains components $g^{1/\gamma}$ and $g^{\gamma\beta_j/\beta_k}$, and at registration user $i$ additionally publishes $\lbrace g^{\gamma\beta_i r_i/\beta_j}\rbrace_{j\neq i}$ inside its public key. Aggregation then folds these into helper keys that carry exactly the cross-term mass:

\[\mpk=\Bigl(g_T,\, g_T^{\vecalpha},\, g_1^{1/\gamma},\, W=\textstyle\prod_{i} g_1^{\,\beta_i(r_i+\ip{\vecalpha}{\vecy_i})}\Bigr),\qquad \hsk_i=\prod_{j\neq i}\bigl(g_2^{\,\beta_j\gamma r_j/\beta_i}\cdot g_2^{\,\beta_j\gamma\ip{\vecalpha}{\vecy_j}/\beta_i}\bigr),\]

with ciphertext $\ct=(g_T^{s},\, g_T^{s\vecalpha+\vecx},\, g_1^{-s/\gamma},\, W^s)$. Now user $i$ can compute and remove the cross terms, leaving precisely the mask $g_T^{s\ip{\vecalpha}{\vecy_i}}$ — and out comes $\ip{\vecx}{\vecy_i}$. Both $\mpk$ and $\hsk_i$ stay compact, $\poly(\secp, n, \log L)$, exactly as a slotted registered FE demands. This function-aggregation technique — binding each registered vector to its slot and shipping the cancellation material in the public key — is the paper’s core engine.

Adding Access Control: Registered ABIPFE

Plain IPFE is powerful but fragile: every released key leaks a linear view of the data. Attribute-based IPFE (ABIPFE) gates each inner product behind an access policy. The paper builds a registered ABIPFE by fusing two aggregations:

Each user now registers a vector $\vecy_i$ and an attribute set $\Att_i$; encryption happens under a policy $P=(\bM,\rho)$ expressed as a linear secret-sharing scheme (shares $\mathbf{u}=\bM\mathbf{v}$ of a secret $s$, reconstructable exactly when the attributes satisfy $P$). The trick is to randomize the IPFE component $W^s$ with a fresh $h\leftarrow\Gi$:

\[\ct=\bigl(g_T^{s},\; g_T^{s\vecalpha+\vecx},\; g_1^{-s/\gamma},\; g_1^{-s/\pi},\; h^{s}W^{s},\; h^{\ip{\mathbf{v}}{\mathbf{m}_k}}\,T_{\rho(k)}^{s}\bigr).\]

Decryption now produces an extra masking factor $e(h,g_2)^{s/\beta_i}$, which a user can cancel only if its attribute set $\Att_i$ satisfies the policy — using the same cross-term-cancellation idea, now applied to the attribute side. Unauthorized users, even holding valid IPFE keys, cannot strip the mask and learn nothing about $\ip{\vecx}{\vecy_i}$. The master public key and helper keys remain compact, $\poly(\secp, \lvert\mathcal{U}_{\mathsf{att}}\rvert, n, \log L)$.

The Bigger Picture

Alongside the pairing-based schemes, the paper gives a general registered FE for arbitrary functions from indistinguishability obfuscation, which even supports an exponential number of users (its slotted $\crs$ grows only with $\log L$). The pairing-based constructions, like all known pairing-based registered ABE, support a bounded user count (their slotted $\crs$ is $O(L^2)$).

The takeaway: registration is no longer limited to access control. With function-aggregation — binding registered vectors to slots and distributing the cancellation material through public keys — we get genuine computation on encrypted data, optionally behind fine-grained policies, with no trusted authority and from standard pairings.