Deterministic public-key encryption

A deterministic public-key encryption (D-PKE) scheme is a public-key encryption scheme whose encryption algorithm is deterministic. Security asks that the encryptions of distinct, high-min-entropy messages, chosen independently of the public key, reveal no partial information about the messages — BBO07.

Syntax

A D-PKE scheme is a tuple of efficient algorithms with message space — BBO07:

  • , a randomized algorithm outputting a secret key and a public key.
  • , a deterministic algorithm encrypting .
  • , a deterministic algorithm outputting or .

For a vector of messages, .

Properties

Correctness

A D-PKE scheme is -correct if for all and ,

over . When , we say is perfectly correct.

PRIV security

The adversary is a pair : a message finder , which does not see , outputs a vector of messages and a target string about them, and a guesser , given and the encryption of a message vector, tries to output . The guesser receives the encryption of in the world and of an independent vector from a second run of in the world — BBO07.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{priv}\text{-}b}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(1^\secpar)$
\State $(\mathbf{x}_0, t_0) \gets \calA_m(1^\secpar)$; $(\mathbf{x}_1, t_1) \gets \calA_m(1^\secpar)$
\Comment{independent runs of an admissible $\calA_m$, which does not see $\pk$}
\State $g \gets \calA_g(\pk, \Enc(\pk, \mathbf{x}_b))$
\Return $[g = t_0]$
\end{algorithmic}
\end{algorithm}

The message finder is admissible with min-entropy if its vectors always have distinct components, all of the same length , and for every and every . A D-PKE scheme is PRIV-secure for min-entropy if for all efficient with admissible ,

is negligible. In the random oracle model both and query the oracle — BBO07. Distinct components and are necessary: equal messages have equal ciphertexts, and for , can encrypt a likely message itself and compare; the length condition plays the role of in CPA security — standard.

As an object, D-PKE denotes a -correct scheme that is PRIV-secure for every — BBO07 — and whose message space contains for some ; without the length bound no message finder is admissible and PRIV is vacuous — standard.

Variations

Security for block sources

A vector of messages is a block source with min-entropy if each has min-entropy at least conditioned on every value of . PRIV security for block sources restricts admissible to block sources, so it is weaker than PRIV, which lets the components be arbitrarily correlated as long as each has min-entropy — BFO08. BFO08 show it equivalent to single-message and indistinguishability-based formulations, and construct CPA- and CCA-secure D-PKE for block sources in the standard model, extending the lossy-trapdoor-function framework of PW08, with instantiations under number-theoretic assumptions — BFO08.

TODO: the min-entropy regime of PRIV security for block sources, stated from BFO08: which , relative to the message length , the definition and the constructions quantify over, and whether security holds for every such or for one. Register the notion as a variant once the regime is stated, with a weakening edge from D-PKE if the regime lies within .

Other results

  • In the random oracle model, any CPA-secure PKE yields a PRIV-secure D-PKE by deriving the encryption coins from a hash of the public key and the message (CPA-secure PKE ⇒ D-PKE) — BBO07.
  • D-PKE gives database encryption with search in time logarithmic in the size of the database, with privacy as strong as this constraint allows; BBO07 generalize it to efficiently searchable encryption, which trades privacy for search time by bucketization — BBO07.
  • BBO07’s RSA-based scheme RSA-DOAEP is length-preserving: a ciphertext has the length of its message — BBO07.

Participates in

Produces Deterministic public-key encryption