Computing on Unbounded Data with Attributes spanning Multiple Authorities

One Computation, Many Gatekeepers

Suppose a company wants the average salary of employees who hold both a driving license and a PhD — computed over encrypted HR records. Or a ministry wants mental-health statistics across students of many departments and universities. Each of these is a linear function on encrypted data (an inner product), gated by an access policy over attributes. The twist: the attributes aren’t owned by one party. A university issues “PhD,” a transport agency issues “driving license,” each department vouches for its own students.

Attribute-based inner-product FE (AB-IPFE) gives the computation-plus-access-control part: a key for a vector $\by$ and some attributes decrypts a ciphertext (carrying data $\bx$ under a policy $P$) to reveal $\ip{\bx}{\by}$ — only if the attributes satisfy $P$. But classical AB-IPFE assumes a single authority minting all keys. Real attributes live across many independent authorities that should never have to coordinate.

That decentralized setting is multi-authority AB-IPFE (MA-ABIPFE): each authority runs its own setup and issues keys for only the attributes under its control, with no inter-authority communication. A user gathers keys from whichever authorities certify their attributes and, if those satisfy the policy, learns $\ip{\bx}{\by}$.

The only prior MA-ABIPFE of Agrawal, Goyal, Tomida, TCC 2021 (AGT) works — but at a steep price, and that price is the story of this paper.

The Trouble with the State of the Art

That sets up a sharp open problem.

Our Answer: MA-ABUIPFE

The paper resolves it by formulating and building multi-authority attribute-based unbounded IPFE (MA-ABUIPFE), with three features the prior scheme lacked: (a) independent authorities control different attributes; (b) authorities join anytime, with no cap on how many can ever exist; (c) message and key vectors have no length fixed at setup — each authority generates its keys without committing to a vector length.

It comes in two flavours, and crucially it runs in fast prime-order groups under target-group assumptions (qualitatively weaker than source-group ones), while lifting the one-use restriction entirely.

The Starting Point: Unbounded IPFE by Hash-and-Pair

How do you make vectors unbounded? The trick comes from the unbounded IPFE of Dufour-Sans and Pointcheval (DP), itself built on DBDH. Given a public key $\dbo{\alpha}$, encryption amplifies entropy by pairing it with a hash applied to each coordinate’s index:

\[\CT_{\bx}:\ C_0=\dbo{r},\quad \lbrace\, C_i=\dbt{x_i}\cdot e(\dbo{\alpha},\, r\,\dbtw{\hash(i)}) \,\rbrace_{i\in\mathcal{I}}; \qquad \SK_{\by}:\ -\alpha\textstyle\prod_{j}\hash(j)^{y_j}.\]

Because the hash $\hash$ stretches to any index on the fly, no length need be fixed in advance. When the index sets match, the key vector $\by$ pulls $\dbt{\ip{\bx}{\by}}$ out of $\prod_j C_j^{y_j}$ and a single pairing $e(C_0, \SK_{\by})$. The natural plan: graft this hash-and-pair idea onto a DBDH-based multi-authority ABE (Datta–Komargodski–Waters) to get an unbounded multi-authority scheme. It almost works — and where it breaks is the heart of the paper.

The Obstacle: Encryption Doesn’t Know Who Will Decrypt

In the multi-authority world, the per-user keys from different authorities are tied together by a hash of the user’s global identity $\gid$ and key vector $\bu$ — something like $\hash(\gid\concat\bu\concat j\concat k\concat\mathcal{I})$. To extend an authority’s key component to an unbounded length, the encryptor would need to evaluate that very hash. But it can’t:

A plain hash-and-pair simply can’t let a data owner encrypt unbounded-length vectors here.

The Key Idea: Hash-Decomposition

The fix is a hash-decomposition mechanism: split the one problematic hash into a product of two independent hashes, sorted by who can compute what and when.

\[\hash(\gid\concat\bu\concat j\concat k\concat\mathcal{I}) \;=\; \hash_2(j\concat k\concat\mathcal{I}) \;\cdot\; \hash_3(\gid\concat\bu\concat j\concat k)\]

with the first factor depending only on indices (so the encryptor can compute it) and the second depending on $\gid,\bu$ (so it waits for decryption):

The $\hash_2$ half carries no $\gid$ or $\bu$, so the encryptor can use it to expand an authority’s public-key component $\dbo{y_{t,j}}$ into a target-group vector,

\[\dbt{y_{t,j,k}^{(2)}} = e(\dbo{y_{t,j}},\, \hash_2(j\concat k\concat\mathcal{I})),\]

baking the unbounded stretch into the ciphertext without ever seeing the user. The $\hash_3$ half, which does depend on $\gid,\bu$, is supplied at decryption. To stitch the two halves back together correctly, the ciphertext carries an extra layer of secret-sharing of zero (components $C_{4,i,j}$), so the pairing operation that a single-authority scheme would do in one shot is now distributed between the encryption and decryption algorithms:

\[e\big(\hash(\gid\concat\bu\concat j),\, \ip{C_{3,i,j}}{\bu}\big) \;\longrightarrow\; \textstyle\prod_{k} C_{3,i,j,k}^{\,u_k}\cdot e\big(C_{4,i,j},\, \hash_3(\gid\concat\bu\concat j\concat k)^{u_k}\big).\]

The left side is what a bounded multi-authority scheme computes in one pairing; the right side is the unbounded version, with the $\hash_2$-dependent work pre-baked into $C_{3,i,j,k}$ at encryption and only the $\hash_3$-dependent piece finished at decryption. That redistribution is exactly what lets a data owner encrypt vectors of unbounded length without knowing the decryptor. The large-universe upgrade then layers on the Rouselakis–Waters technique so attributes need never be enumerated at setup.

How Much Better?

Why It Matters

By distributing one stubborn hash across encryption and decryption, hash-decomposition turns a five-day, rigidly bounded, composite-order scheme into a prime-order one that decrypts in minutes, shrinks public keys by around 99%, drops the one-use restriction, and lets authorities and attributes — and the data itself — grow without limit. And it does so under DBDH, a long-studied target-group assumption weaker than what the prior scheme required, demonstrating that a functionality well beyond “all-or-nothing” access control can rest on the same footing as textbook ABE.

A useful by-product falls out along the way: a single-authority attribute-based unbounded IPFE from DBDH — the first AB-IPFE of any kind based on a target-group assumption, broadening the set of assumptions this primitive can stand on.