Linear Computations with Predicates Hiding Attributes

$$ \newcommand{\ip}[2]{\langle #1, #2\rangle} \newcommand{\bx}{\mathbf{x}} \newcommand{\bw}{\mathbf{w}} \newcommand{\by}{\mathbf{y}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bk}{\mathbf{k}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bB}{\mathbf{B}} \newcommand{\dbi}[1]{[\![#1]\!]_1} \newcommand{\dbii}[1]{[\![#1]\!]_2} \newcommand{\Rp}{\mathcal{R}_p} \newcommand{\Rs}{\mathcal{R}_s} \newcommand{\SK}{\mathsf{SK}} \newcommand{\CT}{\mathsf{CT}} \newcommand{\sxdh}{\mathsf{SXDH}} $$

Based on joint work with Uddipana Dowerah, Subhranil Dutta, Aikaterini Mitrokotsa, and Sayantan Mukherjee — Unbounded Predicate Inner Product Functional Encryption from Pairings (Dowerah et al., 2023), appeared in the Journal of Cryptology. This post is an intuitive tour of the ideas; the paper carries the full constructions and proofs.

A Hospital, a Cloud, and a Statistic

Picture the Ministry of Health (MoH) wanting the average blood pressure of patients recently treated for influenza — computed over records that hospitals have encrypted and parked in a cloud. The MoH should learn that one statistic, and only for the patients matching a policy, without ever seeing the raw records or the sensitive identifiers attached to them.

This is exactly what attribute-based inner-product FE (AB-IPFE) promises. A hospital encrypts a patient’s vitals $\bx$ (temperature, heart rate, blood pressure, …) under an attribute $\bw$ (SSN, age, sex, eligible designations, …). A research centre holds a key for a policy $P$ and a weight vector $\by$. Decryption reveals the weighted statistic $\ip{\bx}{\by}$ — but only if the attribute satisfies the policy.

Hospital (data owner)
encrypts vitals $\bx$ under attribute $\bw$

→

$\CT_{\bx,\bw}$ on the cloud
attribute $\bw$ stays hidden

MoH (authority)
issues $\SK_{P,\by}$

→

Specialist (data user)

→

learns $\ip{\bx}{\by}$
iff $P(\bw)$ holds

SSN Race Age Sex Scientist ID attribute $\bw$ — orange entries must stay private

policy example $P:\ (5000 < \text{SSN} < 8000)\ \wedge\ (\text{Infectious Disease Specialist})$

Inner-product predicates are expressive — they capture disjunctions, polynomials, and CNF/DNF formulae — so this single primitive covers a lot of “search-then-aggregate” tasks. But deploy it with existing AB-IPFE and you hit two walls.

Wall 1 — bounded sizes

Existing AB-IPFE fixes a maximum data/attribute length at setup. The MoH cannot guess that bound in advance, and once chosen, the master public key — and every ciphertext a hospital ever produces — grows with the bound, even when the actual record is tiny.

Wall 2 — leaked attributes

Existing AB-IPFE reveals the attribute $\bw$ attached to a ciphertext. That hands the SSN, age, and other identifiers straight to the data user — a privacy breach the hospital cannot allow.

Our work removes both walls at once with unbounded, attribute-hiding predicate IPFE (UP-IPFE): no size bound at setup, and the ciphertext both hides $\bw$ and grows only with the data and attributes actually present.

What UP-IPFE Computes

A ciphertext $\CT_{\bx,\bw}$ carries a message $\bx$ and attribute $\bw$; a secret key $\SK_{\by,\bv}$ carries a key vector $\by$ and a predicate vector $\bv$. Decryption returns $\ip{\bx}{\by}$ — but only when two conditions line up: an index-set relation and a predicate $R(\bw,\bv)$.

$\CT_{\bx,\bw}$

$+$

$\SK_{\by,\bv}$

→

index relation holds?
permissive / strict

→

$R(\bw,\bv)=1$?
zero / non-zero

→

output $\ip{\bx}{\by}$

Because vectors are unbounded, they live on index sets, and two flavours of compatibility matter:

Index relation

Permissive $\Rp$: defined when $I_{\bv}\subseteq I_{\bw}$, summing over the smaller set.
Strict $\Rs$: defined only when $I_{\bw}=I_{\bv}$.

Predicate $R(\bw,\bv)$

Zero (UZP-IPFE): accept iff $\ip{\bw}{\bv}=0$.
Non-zero (UNP-IPFE): accept iff $\ip{\bw}{\bv}\neq 0$.

The security goal is attribute-hiding: an adversary holding many keys — both accepting and non-accepting with respect to the challenge — should learn nothing beyond $\ip{\bx}{\by}$ (and not even the attribute $\bw$). Full attribute-hiding allows arbitrary accepting and non-accepting keys; weak attribute-hiding restricts the predicate vectors of accepting keys so the attribute can’t simply be read off. The paper delivers two schemes at complementary points of this space.

Construction 1 — UZP-IPFE (the technical heart)

The first scheme is a public-key, permissive, zero-predicate UP-IPFE with full attribute-hiding in the standard model under $\sxdh$. Its starting point is the unbounded IPFE of Tomida and Takashima (TT18), whose index-encoding trick supplies both the unboundedness and the entropy needed to block illegitimate keys. Getting from there to an attribute-hiding predicate scheme takes a careful, four-step climb.

1Concatenate & randomize — one TT18 call; randomize to mask $\ip{\bx}{\by}$ when $\ip{\bw}{\bv}\neq 0$.

2Two independent calls — fixes permissiveness, but opens a mix-n-match attack.

3A middle route — two calls bound by a joint secret-sharing of zero.

4Separate bases — different DPVS bases to stop cross-pairing.

Step 1 — concatenate, then randomize

Pack $(\bx,\bw)$ as the message and $(\by,\bv)$ as the key into a single TT18 ciphertext and key. Correctness hands you the sum $\ip{\bw}{\bv} + \ip{\bx}{\by}$ — which is exactly $\ip{\bx}{\by}$ when $\ip{\bw}{\bv}=0$. To stop a non-accepting key ($\ip{\bw}{\bv}\neq 0$) from leaking, scale the attribute side by fresh randomness $\delta,\omega$:

TT18 decrypt

→

$\delta\omega\,\ip{\bw}{\bv} + \ip{\bx}{\by}$

$\ip{\bw}{\bv}=0\ \Rightarrow\ \ip{\bx}{\by}$
accepting: statistic revealed

$\ip{\bw}{\bv}\neq0\ \Rightarrow\ \text{masked}$
non-accepting: nothing leaks

Good intuition — but concatenation quietly breaks permissiveness (the merged index set no longer splits into the $\bx$- and $\bw$-parts), and the mask won’t line up across challenge attributes for non-accepting keys. Dead end.

Step 2 — two independent calls (and a new attack)

Encrypt $\bw$ and $\bx$ with two TT18 calls, and let the key be two TT18 keys, for $(\bv,I_{\bv})$ and $(\by,I_{\by})$. Permissiveness now holds on each side — but independence is too much freedom:

Mix-n-match attack. From keys $\SK_{\bv,\by}=(\mathsf{sk}_{\bv},\mathsf{sk}_{\by})$ and $\SK_{\bv',\by'}=(\mathsf{sk}_{\bv'},\mathsf{sk}_{\by'})$, an adversary splices a brand-new legitimate-looking key $\SK_{\bv,\by'}=(\mathsf{sk}_{\bv},\mathsf{sk}_{\by'})$ — recombining a predicate from one key with a function from another, breaking security.

Step 3 — a middle route: bind the two halves

The fix is a hybrid: still two parallel TT18 calls, but no longer independent. Tie the two key halves together with a joint secret-sharing of zero — shares $\lbrace \gamma_i,\widetilde{\gamma}_j\rbrace$ with $\sum_i\gamma_i+\sum_j\widetilde{\gamma}_j=0$ — and let the two ciphertext halves share a common randomness $z$ so the shares recombine exactly at decryption.

Secret Key — bound by $\sum \gamma + \widetilde{\gamma}=0$

$\mathsf{sk}_{\by}$ share $\gamma_i$

↕ joint zero-share

$\mathsf{sk}_{\bv}$ share $\widetilde{\gamma}_j$

splicing a foreign half breaks the zero-sum → mix-n-match blocked

Ciphertext — shared $z$

$\mathsf{ct}_{\bx}$ randomness $z$

↕ common $z$

$\mathsf{ct}_{\bw}$ randomness $z$

lets the holder recombine the shares at decryption

Concretely, in the dual pairing vector space (DPVS), with $\dbi{\cdot}$ / $\dbii{\cdot}$ denoting encodings in the two source groups:

\[\SK_{\by,\bv}:\quad \dbii{\bk_i=(\rho_i(-i,1),\,y_i,\,\gamma_i)\bB^{\ast}}\ \ \text{and}\ \ \dbii{\bk_j=(\widetilde{\rho}_j(-j,1),\,\omega v_j,\,\widetilde{\gamma}_j)\bB^{\ast}} \quad\text{s.t. }\textstyle\sum_i\gamma_i+\sum_j\widetilde{\gamma}_j=0,\] \[\CT_{\bx,\bw}:\quad \dbi{\bc_i=(\pi_i(1,i),\,x_i,\,z)\bB}\ \ \text{and}\ \ \dbi{\bc_j=(\widetilde{\pi}_j(1,j),\,\delta w_j,\,z)\bB}.\]

The first two coordinates encode the index (the source of unboundedness), the third the vector entry, and the last the binding randomness.

Step 4 — separate bases stop cross-pairing

One subtlety remains: with overlapping index sets, an adversary could pair $\bk_i$ with $\bc_j$ and $\bk_j$ with $\bc_i$ — crossing the wires — to obtain $\delta\ip{\bw}{\by}+\omega\ip{\bx}{\bv}$ and leak information about $\bx$.

same basis $\bB$ everywhere
$\bk_i\times\bc_j,\ \bk_j\times\bc_i$ pair up → leak

⇒

$(\bB,\bB^{\ast})$ for $(\bx,\by)$
$(\widetilde{\bB},\widetilde{\bB}^{\ast})$ for $(\bw,\bv)$
cross-pairings land in incompatible spaces → vanish

The result is a full attribute-hiding UZP-IPFE that protects message and attribute against an adversary as strong as a TT18 adversary and a full attribute-hiding zero-predicate adversary combined — achieved by extending the TT18 framework from “hiding an unbounded message” to “hiding an unbounded message and attribute.”

Construction 2 — UNP-IPFE (simple, generic, succinct keys)

The second scheme flips several choices: secret-key, strict, non-zero-predicate, with weak attribute-hiding in the stronger simulation model under bilateral $k$-Lin. Its headline feature is constant-size secret keys — independent of the (unbounded) vector lengths.

The route is a classic transformation: encode the attribute alongside the payload, and recover the payload only when $\ip{\bw}{\bv}\neq 0$. Here the “payload” is itself an inner product, so encrypt the tensor $\bx\otimes\bw$:

encrypt $\bx\otimes\bw$
via UQFE (compact)

→

$\ip{\bx}{\by}\cdot\ip{\bw}{\bv}$ and $\ip{\bw}{\bv}$

→

divide out $\ip{\bw}{\bv}$
get $\ip{\bx}{\by}$ if $\ip{\bw}{\bv}\neq0$

The identity $\ip{\bx\otimes\bw}{\by\otimes\bv}=\ip{\bx}{\by}\cdot\ip{\bw}{\bv}$ does the work. The snag is that a tensor naively makes the ciphertext quadratic in the vector lengths; computing that quadratic term with an unbounded quadratic FE (UQFE) instead keeps the ciphertext linear:

$\SK_{\by,\bv}:\ \mathsf{qsk}_{\by\otimes\bv},\ \mathsf{isk}_{\bv} \qquad\qquad \CT_{\bx,\bw}:\ \mathsf{qct}_{\bx,\bw},\ \mathsf{ict}_{\bw}$

A UQFE handles the quadratic $\bx\otimes\bw$ part with compact ciphertexts; a plain unbounded IPFE recovers $\ip{\bw}{\bv}$.

This yields a simulation-secure UNP-IPFE with compact ciphertexts and constant-size keys — and motivates a question the paper also takes up: building a simulation-secure UQFE with constant keys and compact ciphertexts, since the only prior UQFE is indistinguishability-based with linear-size keys.

The Two Schemes at a Glance

Scheme	Setting	Index relation	Predicate	Attribute-hiding	Assumption	Notable
UZP-IPFE	public key	permissive	zero ($\ip{\bw}{\bv}=0$)	full, IND, semi-adaptive	SXDH	standard model
UNP-IPFE	secret key	strict	non-zero ($\ip{\bw}{\bv}\neq0$)	weak, SIM, semi-adaptive	bilateral $k$-Lin	constant-size keys

Why It Matters

Back to the hospital. With UP-IPFE, the MoH never fixes a size bound at setup, so hospitals encrypt records of whatever size they have, and ciphertexts stay proportional to the actual data. The sensitive attributes — SSN, age, sex — are hidden inside the ciphertext, yet a research centre with the right policy key still extracts exactly the authorized statistic $\ip{\bx}{\by}$ and nothing more.

To our knowledge these are the first unbounded AB-IPFE schemes that are simultaneously attribute-hiding and unbounded — one maximizing security (full attribute-hiding in the standard model), the other maximizing succinctness (constant-size keys, simulation security) — turning a clean theoretical primitive into something that fits the messy, unbounded shape of real data.

Want the formal definitions, the dual-system security proofs, and the full UQFE discussion? They’re in the paper (Dowerah et al., 2023) and at ePrint 2023/483.