Computing on Encrypted Data Without a Central Authority

Computation on Encrypted Data — But Who Holds the Keys?

Functional encryption (FE) is one of the most powerful generalizations of public-key encryption. Instead of all-or-nothing decryption, a holder of a function key for $f$ can take a ciphertext of $x$ and learn exactly $f(x)$ — and nothing more about $x$. That single idea captures access control, privacy-preserving analytics, and much of modern advanced cryptography.

There’s a catch, though, and it’s a big one: in standard FE a central authority holds a master secret key and hands out every function key. That authority can decrypt everything. This is the classic key-escrow problem — a single trusted party who must be trusted absolutely.

Registered FE (RFE) removes that party. Users generate their own keys and register their public keys with a transparent key curator that holds no secret at all. The curator’s only job is bookkeeping: combine everyone’s registered keys into one short master public key. No escrow, no trusted authority — yet decryption still yields exactly $f(x)$.

Our work asks a sweeping question: can we build registered FE for rich functionalities — fine-grained access control, Turing-machine policies, quadratic functions — from standard pairing assumptions, in a single unified framework? The answer is yes, and the engine behind it is a notion we call user-specific pre-constraining.

The Target: (Slotted) Registered Functional Encryption

Thanks to a “powers-of-two” compiler, it suffices to build the simpler slotted RFE (sRFE), where the number of users $L$ is fixed and there’s no dynamic update machinery to worry about. Here’s the whole pipeline:

Security demands that a user holding $\sk_i$ learns nothing about $x$ beyond $f_i(x)$. And there’s a sharp efficiency bar — compactness: the master public key, helper keys, and ciphertexts must scale only polylogarithmically in the number of users $L$. You cannot, for instance, afford to stuff a description of every user’s function into $\mpk$.

The Classical Recipe — and Why It Breaks

In the non-registered world, a beautiful line of work builds expressive FE from a simple template:

inner-product FE (IPFE) $+$ linear garbling $=$ FE for rich functions.

To see how, we first need the garbling gadget.

The gadget: arithmetic key garbling (AKGS)

An arithmetic key garbling scheme (AKGS) is a lightweight, one-time secure way to encode a computation. For a function $f$ and two secrets $\sigma_0,\sigma_1$, it offers three algorithms:

The simulator is what “one-time security” means: from the labels alone you learn nothing beyond $f(\bx)$ (encoded in $d$). Lin and Luo gave AKGS for arithmetic branching programs and for logspace Turing machines — which is exactly why the same framework reaches all of $\lbrace \mathsf{ABP}, \mathsf{L}, \mathsf{NL}\rbrace$.

Lifting it with IPFE

A one-time gadget isn’t enough on its own — reuse it twice and it leaks. The classical trick lifts it to full security using IPFE as a re-randomizer. Take key-policy ABE as the running example. To encrypt a message $\mu$ under attribute $\bx$, pick a fresh scalar $s$ and pack $(\mu, s(1,\bx))$ into an IPFE ciphertext; to make a key for policy $f$, garble it and pack the coefficient vectors into IPFE keys:

IPFE decryption pairs these up and reveals, in the target group, exactly the masked value and the randomized labels:

Now the linearity of $\Garble$ pays off: $s\mathbf{L} = \Garble(f, s\sigma_0, s\sigma_1; s\br)$, so running the linear $\Eval$ in the exponent yields $s\,\sigma_1 f(\bx) + s\,\sigma_0$. Following the convention that $f(\bx)=0$ means “authorized,” the $\sigma_1$ term vanishes, the decryptor learns the mask $s\sigma_0$, subtracts it from $d$, and recovers $\mu$ (a discrete log in $\Gt$ for a polynomial-size message space).

Why is it secure? A suitable IPFE (function-hiding or slotted) guarantees that only the encodings of $d$ and the labels $\vec\ell$ ever leak. A DDH-style assumption then makes $(s\sigma_0, s\sigma_1, s\br)$ indistinguishable from freshly sampled randomness — so each decryption looks like an independent honest garbling, and the one-time security of the AKGS lifts to full IND-CPA.

Why it breaks in the registration-based setting

This framework leans hard on two things: the ability to sample garbling randomness while making a key, and a function-hiding IPFE. Neither survives the move to registration. Porting it runs into three walls:

The Key Idea: Decompose the Garbling

The unlock is the very property the AKGS already gave us: its garbling is linear in the randomness (call it $\vec w$). That linearity lets a garbling split cleanly into two stages:

This maps exactly onto the two registration phases: the randomized half happens at setup, where randomness is allowed; the deterministic half happens at aggregation, where the function is finally known. Challenge 1 dissolves.

But we need a building block that can compute an inner product and multiply by a matrix that was fixed earlier, at setup. That building block is the heart of the paper.

The Engine: Inner Products with User-Specific Pre-Constraining

We introduce an sRFE for a functionality we call pre-constrained inner product (Pre-IP). Compared to ordinary inner-product sRFE, the setup gets to bake in a user-specific matrix $\bT_i$ up front:

Now embed the garbling pieces into these matrices: the randomness $\vec w_i$ goes into the pre-constraint $\bT_i$ (chosen at setup), and the deterministic function matrix $\bL_i$ goes into $\bV_i$ (chosen at aggregation). Decryption multiplies them together and reconstructs the garbling. In the simplest case it really is this clean:

which is exactly the garbling $(\vec p_{i,1}, \vec p_{i,2})$ of user $i$’s function — and applying the garbling’s decoder gives $\vec z\,h_i(\vec x)\tr$.

Two more subtleties get handled by the same tool:

One-time security made many-time. A garbling is only one-time secure, so decrypting twice with one key could leak. We split the garbling randomness into a slot-specific part hidden in $\bT_i$ and a ciphertext-specific part carried by $\bU$ — so every ciphertext effectively gets a fresh garbling.

Sidestepping function-hiding (Challenge 2). Instead of function-hiding indistinguishability, we prove simulation security. The trick that makes it work: our simulator is given the decryption result in the source groups $\Gi$ and $\Gii$ — but not in $\Zp$.

Group elements for free (Challenge 3). Because the randomness now lives in $\bT_i$ (fixed at setup) rather than in the registered functions, we can evaluate the product $\impiii{\bU\,\bT_i}$ directly in the groups and randomize it via the bilateral $\MDDH$ (i.e. bilateral $k$-Lin) assumption — so users never need to register vectors of group elements.

Putting It Together: a Modular Framework

With Pre-IP in hand, the rest is modular. Combine Pre-IP with a garbling scheme for a function class $\cF \in \lbrace \mathsf{ABP}, \mathsf{L}, \mathsf{NL} \rbrace$ to get an sRFE for an intermediate functionality Pre-1AWS$_\cF$, parameterized by a pre-constraining matrix $\bM$:

where $h$ is a vector of functions from $\cF$, $\vec x$ is the public input and $\vec z$ the private input. Then generic compilers lift this to the full target functionalities — and these compilers work for any $\cF$, so future garbling schemes plug right in.

What We Get

Instantiating the framework yields several firsts, all from the standard (bilateral) $k$-Lin assumption in asymmetric pairing groups:

• Registered ABE for logspace Turing machines ($\mathsf{L}$ and $\mathsf{NL}$) — the first such schemes. The public parameters scale only with the TM’s number of states, independently of attribute length and the time/space bounds, so the system verifies unbounded-length attributes. This settles an open question of Zhu et al. (Asiacrypt 2023).
• Registered FE for attribute-based attribute-weighted sums (AB-AWS) - the first RFE for AB-AWS with the function class realized by $\mathsf{ABP}$ / $\mathsf{L}$ / $\mathsf{NL}$. A function $f=(g,h)$ on input $(\vec y,(\lbrace \vec x_j, \vec z_j\rbrace_{j\in [N]}))$ (unbounded $N$) returns $\sum_{j \in [N]} h(\vec x_j)^{\tr} \vec z_j$ iff the policy $g(\vec y)=0$, with public attributes $\vec y, \vec x_j$ and private $\vec z_j$.
• Registered FE for attribute-based quadratic functions (AB-QF) with compact ciphertexts — the first quadratic RFE with built-in access control. A function $f=(g,h)$ on input $(\vec y,(\vec z_1,\vec z_2))$ returns $(\vec z_1\otimes\vec z_2)\,h\tr$ iff the policy $g(\vec y)=0$, with public attribute $\vec y$ and private $(\vec z_1,\vec z_2)$.

IP = inner product, QF = quadratic functions, AWS = attribute-weighted sums; "Adp / Sel / SelSta / Sel*" = adaptive / selective / selective-with-static-corruptions / very-selective; "weak QF" = quadratic with fixed functions.

Why It Matters

The throughline is a single, reusable design: a generic compiler that fuses a specialized inner-product RFE (our Pre-IP) with information-theoretic garbling, transferring the classical Lin–Luo recipe into the registration-based world. Pre-IP cleanly encapsulates all the registration logic and hands the compiler exactly what it needs — fresh, user-specific garbling randomness sampled at setup and concealed until decryption.

The payoff is registered FE that is expressive (Turing-machine policies, quadratic functions), access-controlled, compact, and simulation-secure — all without a trusted key authority, and from standard pairing assumptions.