Fuzzy identity-based encryption

Fuzzy identity-based encryption (Fuzzy IBE) is an extension of IBE in which identities are represented as sets of descriptive attributes drawn from a universe $\mathcal{U}$. A key for attribute set $\omega$ can decrypt a ciphertext encrypted under attribute set ${\omega }^{\prime }$ if and only if the two sets overlap by at least $t$ attributes: $|\omega \cap {\omega }^{\prime }|\ge t$. This threshold-based partial matching makes Fuzzy IBE suitable for biometric identities, where noise prevents exact matching. Sahai and Waters (2005) introduced Fuzzy IBE as the conceptual precursor to attribute-based encryption.

Syntax

A Fuzzy IBE scheme is a tuple of efficient algorithms $\mathsf{FIBE}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to attribute universe $\mathcal{U}$, threshold $t\in \mathbb{N}$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$:

• $\mathsf{Setup}(1^{\lambda },\mathcal{U},t)\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},\omega )\to {\mathsf{sk}}_{\omega },$ is a (possibly randomized) algorithm that takes $\mathsf{msk}$ and an attribute set $\omega \subseteq \mathcal{U}$, outputting a secret key ${\mathsf{sk}}_{\omega }$,
• $\mathsf{Enc}(\mathsf{pp},{\omega }^{\prime },m)\to c,$ is a randomized algorithm that takes $\mathsf{pp}$, an attribute set ${\omega }^{\prime }\subseteq \mathcal{U}$ used as the encryption identity, and $m\in \mathcal{M}$, outputting $c\in \mathcal{C}$,
• $\mathsf{Dec}({\mathsf{sk}}_{\omega },c)\to m,$ is a deterministic algorithm that takes ${\mathsf{sk}}_{\omega }$ and $c$, outputting $m\in \mathcal{M}$ or $\perp$.

Decryption succeeds if and only if $|\omega \cap {\omega }^{\prime }|\ge t$.

Properties

Correctness

A Fuzzy IBE scheme is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$, attribute sets $\omega ,{\omega }^{\prime }\subseteq \mathcal{U}$ with $|\omega \cap {\omega }^{\prime }|\ge t$, and $m\in \mathcal{M}$,

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

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

IND-FIBE-CPA Security

The adversary queries the key generation oracle for attribute sets of its choice. Admissibility requires that no queried set $\omega$ has $|\omega \cap {\omega }^{\ast }|\ge t$, since such a key would decrypt the challenge ciphertext.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{fibe\text{-}cpa}}_{\mathsf{FIBE},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pp, \msk) \gets \Setup(1^\secpar, \calU, t)$; $b \getsr \bits$
\State $\calO_{\mathrm{key}}(\omega) := \KeyGen(\msk, \omega)$
\State $(\omega^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{key}}}(1^\secpar, \pp)$
\Comment{$\calA$ may not have queried $\calO_{\mathrm{key}}(\omega)$ for $|\omega \cap \omega^*| \ge t$}
\State $c^* \gets \Enc(\pp, \omega^*, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}}(c^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{key}}(\omega)$ for $|\omega \cap \omega^*| \ge t$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A Fuzzy IBE scheme $\mathsf{FIBE}$ is IND-FIBE-CPA-secure if for all efficient admissible $\mathcal{A}$,

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

is negligible.

IND-sFIBE-CPA Security (Selective)

In the selective variant, the adversary commits to ${\omega }^{\ast }$ before $\mathsf{Setup}$ runs.

Variations

Small-universe vs. large-universe

In small-universe Fuzzy IBE, the attribute universe $\mathcal{U}$ is fixed and encoded into $\mathsf{pp}$ at $\mathsf{Setup}$ time. In large-universe variants, attributes can be arbitrary strings drawn lazily, typically at the cost of larger parameters.

Other results

• Fuzzy IBE generalizes IBE: setting $t=1$ and $|\omega |=|{\omega }^{\prime }|=1$ recovers exact-identity matching
• Fuzzy IBE is subsumed by KP-ABE: a threshold-$t$ formula over $|\mathcal{U}|$ attributes is expressible as a monotone Boolean formula
• SW05 introduced Fuzzy IBE and gave the first construction under the Selective-ID security model — SW05