Inner-product predicate encryption

Inner-product predicate encryption (IPPE) is a form of predicate encryption in which keys and ciphertexts are each associated with vectors over ${\mathbb{Z}}_p$. A key for vector $v\in {\mathbb{Z}}_p^n$ can decrypt a ciphertext for vector $x\in {\mathbb{Z}}_p^n$ if and only if $⟨v,x⟩=0(\mathrm{mod}p)$. IPPE achieves full attribute-hiding: a ciphertext hides both the encrypted payload and the attribute vector $x$. It subsumes HVE and, via inner-product encodings, supports disjunctions, CNF/DNF formulas, and polynomial evaluation—making it the practical ceiling before full predicate encryption.

Syntax

An IPPE scheme is a tuple of efficient algorithms $\mathsf{IPPE}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to prime $p$, dimension $n$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$:

• $\mathsf{Setup}(1^{\lambda },p,n)\to (\mathsf{pp},\mathsf{msk}),$ is a randomized algorithm that outputs public parameters $\mathsf{pp}$ and master secret key $\mathsf{msk}$,
• $\mathsf{KeyGen}(\mathsf{msk},v)\to {\mathsf{sk}}_v,$ is a (possibly randomized) algorithm that takes $\mathsf{msk}$ and a predicate vector $v\in {\mathbb{Z}}_p^n$, outputting a secret key ${\mathsf{sk}}_v$,
• $\mathsf{Enc}(\mathsf{pp},x,m)\to c,$ is a randomized algorithm that takes $\mathsf{pp}$, an attribute vector $x\in {\mathbb{Z}}_p^n$, and $m\in \mathcal{M}$, outputting $c\in \mathcal{C}$,
• $\mathsf{Dec}({\mathsf{sk}}_v,c)\to m,$ is a deterministic algorithm that takes ${\mathsf{sk}}_v$ and $c$, outputting $m\in \mathcal{M}$ or $\perp$.

Decryption succeeds if and only if $⟨v,x⟩=0(\mathrm{mod}p)$.

Properties

Correctness

An IPPE scheme is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, $v,x\in {\mathbb{Z}}_p^n$ with $⟨v,x⟩=0(\mathrm{mod}p)$, and $m\in \mathcal{M}$,

$$\mathrm{Pr}\left[\mathsf{Dec}(\mathsf{KeyGen}(\mathsf{msk},v),\mathsf{Enc}(\mathsf{pp},x,m))=m\right]\ge 1-\epsilon ,$$

over $(\mathsf{pp},\mathsf{msk})\leftarrow \mathsf{Setup}(1^{\lambda },p,n)$ and randomness of $\mathsf{KeyGen}$ and $\mathsf{Enc}$.

Full Attribute-Hiding Security

In the full attribute-hiding game, the adversary submits two ciphertext candidates $(x_0,m_0)$ and $(x_1,m_1)$ and receives an encryption of one of them. Admissibility requires that every queried key vector $v$ is consistent with both candidates: $⟨v,x_0⟩=0\iff ⟨v,x_1⟩=0(\mathrm{mod}p)$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ah}}_{\mathsf{IPPE},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pp, \msk) \gets \Setup(1^\secpar, p, n)$; $b \getsr \bits$
\State $\calO_{\mathrm{key}}(v) := \KeyGen(\msk, v)$
\State $((x_0, m_0), (x_1, m_1), \stA) \gets \calA^{\calO_{\mathrm{key}}}(1^\secpar, \pp)$
\Comment{For all queried $v$: $\langle v, x_0 \rangle = 0$ iff $\langle v, x_1 \rangle = 0$ (mod $p$)}
\State $c^* \gets \Enc(\pp, x_b, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}}(c^*, \stA)$
\Comment{Same admissibility constraint holds throughout}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An IPPE scheme $\mathsf{IPPE}$ is attribute-hiding if for all efficient admissible $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{IPPE},\mathcal{A}}^{\mathrm{ah}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{IPPE},\mathcal{A}}^{\mathrm{ah}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Payload-only hiding

Dropping the attribute-hiding requirement yields a simpler payload-hiding variant: the adversary commits to a single $x^{\ast }$ and submits two messages, with the constraint that no queried $v$ satisfies $⟨v,x^{\ast }⟩=0(\mathrm{mod}p)$.

Zero inner product vs. non-zero

Some formulations flip the predicate: decryption succeeds when $⟨v,x⟩\ne 0$. This is equivalent up to a simple transformation (append a constant coordinate) and is sometimes more natural for access control.

Other results

• IPPE generalizes HVE: a conjunctive pattern predicate over ${\Sigma }^n$ can be encoded as an inner-product predicate by choosing an alphabet embedding into ${\mathbb{Z}}_p$
• IPPE is incomparable to KP-ABE and CP-ABE: IPPE achieves full attribute-hiding but only captures inner-product predicates, while KP/CP-ABE supports arbitrary monotone Boolean formulas but leaks the access policy
• KSW08 introduced IPPE and showed that inner products encode disjunctions, polynomial equations, and CNF/DNF formulas; the scheme is proved attribute-hiding under the decisional linear assumption — KSW08