IPPE ⇒ HVE

Standard model · KSW08 · security loss: tight up to an additive $2q/p$ for $q$ key queries when the challenge attributes are fixed first: a non-matching key’s encoded inner product vanishes on each challenge attribute with probability $1/p$

Statement

An attribute-hiding IPPE scheme of dimension $2n$ over ${\mathbb{Z}}_p$ yields an HVE scheme for patterns in $(\Sigma \cup \{\ast \}{)}^n$ with $\Sigma \subseteq {\mathbb{Z}}_p$: a pattern $v$ with wildcard set $S$ and an attribute $x$ are encoded as vectors whose inner product is ${\sum }_{i\notin S}{r}_i(x_i-v_i)$ for uniformly random coefficients $r_i$, which vanishes when $v$ matches $x$ and otherwise with probability $1/p$. Attribute-hiding transfers whenever an HVE adversary’s encoded queries stay admissible in the IPPE game, that is, unless it finds a non-matching attribute whose encoded inner product vanishes — KSW08.

Sketch

Encode $x$ as $(x_1,1,\dots ,x_n,1)$ and $v$ as $(r_1,-r_1{v}_1,\dots ,r_n,-r_n{v}_n)$ with $r_i=0$ for $i\in S$ and $r_i\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ otherwise, sampled at key generation; $\mathsf{Setup}$, $\mathsf{KeyGen}$, $\mathsf{Enc}$, $\mathsf{Dec}$ of the HVE scheme call the IPPE algorithms once each on the encoded vectors.

Notes

• IPPE attribute-hiding constrains ciphertexts, not keys, so a scheme may reveal its key vectors (for instance, append them in the clear). An adaptive HVE adversary can then read off the $r_i$ and choose a non-matching challenge attribute with zero encoded inner product, trivially when $\Sigma ={\mathbb{Z}}_p$; such a challenge is admissible in the HVE game but not in the IPPE game. The transfer therefore needs an extra hypothesis: the encoded key vectors are hidden, or HVE security is selective — folklore.