Public-key encryption with keyword search
A public-key encryption with keyword search (PEKS) scheme lets anyone holding a receiver’s public key encrypt a keyword , and lets the receiver issue a trapdoor with which a third party tests whether an encrypted keyword is , learning nothing else about encrypted keywords for which it holds no trapdoor.
Syntax
A PEKS scheme is a tuple of efficient algorithms with keyword space — BDOP04:
- , a randomized algorithm outputting a public key and a secret key .
- , a randomized algorithm outputting a searchable encryption of a keyword .
- , an algorithm outputting a trapdoor for .
- , a deterministic algorithm outputting if it judges that encrypts , and otherwise.
Properties
Correctness
A PEKS scheme is -correct if for all and ,
over and the randomness of and . When , we say is perfectly correct.
Consistency
Correctness constrains on matching keywords; consistency constrains it on distinct ones. The adversary picks two distinct keywords and wins if the trapdoor for the second accepts an encryption of the first — ABC+05.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{consist}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar)$
\State $(W, W') \gets \calA(1^\secpar, \pk)$
\State $S \gets \mathsf{PEKS}(\pk, W)$; $T_{W'} \gets \mathsf{Trapdoor}(\sk, W')$
\Return $[W \ne W' \wedge \mathsf{Test}(\pk, S, T_{W'}) = 1]$
\end{algorithmic}
\end{algorithm}
A PEKS scheme is computationally consistent if for all efficient ,
is negligible. ABC+05 also define statistical consistency, which asks the same of computationally unbounded adversaries — ABC+05. As an object, consistent PEKS denotes a -correct, IND-CKA-secure and computationally consistent scheme.
Perfect consistency
A PEKS scheme is perfectly consistent if for all and all computationally unbounded — ABC+05: for every key pair in the support of and all keywords , with probability . The definition of BDOP04, in which outputs on every non-matching keyword, is perfect consistency — ABC+05. As an object, perfectly consistent PEKS denotes a -correct, IND-CKA-secure and perfectly consistent scheme.
Security against chosen-keyword attacks
The adversary obtains trapdoors for keywords of its choice, names two keywords for which it holds no trapdoor, and tries to tell which one the challenge encrypts. BDOP04 call the notion semantic security against an adaptive chosen keyword attack.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ind\text{-}cka}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, \sk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calO_{\mathrm{td}}(W) := \mathsf{Trapdoor}(\sk, W)$
\State $(W_0, W_1, \stA) \gets \calA^{\calO_{\mathrm{td}}}(1^\secpar, \pk)$
\Comment{$\calA$ may not query $\calO_{\mathrm{td}}$ on $W_0$ or $W_1$}
\State $S^* \gets \mathsf{PEKS}(\pk, W_b)$
\State $b' \gets \calA^{\calO_{\mathrm{td}}}(S^*, \stA)$
\Comment{$\calA$ may not query $\calO_{\mathrm{td}}$ on $W_0$ or $W_1$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
A PEKS scheme is IND-CKA-secure if for all efficient admissible ,
is negligible. The restriction is necessary: with , wins against every correct and consistent scheme by computing . As an object, PEKS denotes a -correct and IND-CKA-secure scheme. Without consistency the object exists unconditionally: the scheme with , and is perfectly correct, and its IND-CKA advantage is since does not depend on .
Variations
Temporary and identity-based keyword search
In public-key encryption with temporary keyword search (PETKS), a trapdoor for is issued for an interval of time periods and lets its holder test only encryptions of made in that interval; in identity-based encryption with keyword search (IBEKS), keywords are encrypted under the receiver’s identity in place of a public key — ABC+05.
Other results
- Under the bilinear Diffie–Hellman assumption, BDOP04’s pairing-based scheme is IND-CKA-secure in the random oracle model (BDH ⇒ PEKS) — BDOP04; it is also computationally consistent in the random oracle model — ABC+05.
- An anonymous IBE for arbitrary-length identities gives a consistent PEKS by encrypting a random string under the keyword as identity and appending that string (anonymous IBE ⇒ PEKS) — ABC+05; conversely, a perfectly consistent PEKS gives an IBE (PEKS ⇒ IBE) — BDOP04.
- A sender appends for the keywords of a message to a PKE encryption of the message, and a gateway holding routes the messages whose appended encryptions pass with — BDOP04.
- is public, so a holder of tests a guess by computing ; for a perfectly correct and consistent scheme the result is for and, except with negligible probability, for each fixed , so a trapdoor reveals its keyword whenever the keywords in use range over a set of polynomial size — standard. IND-CKA does not exclude this: the adversary holds no trapdoor for or .
Participates in
Builds on Public-key encryption with keyword search
- Perfectly consistent PEKS ⇒ IBE (BDOP04) (via Perfect consistency)
- Consistent PEKS ⇒ PEKS (via Consistency)
- Perfectly consistent PEKS ⇒ Consistent PEKS (via Perfect consistency)
Produces Public-key encryption with keyword search