HPS ⇒ CPA-secure PKE
Statement
Let be an -smooth hash proof system with key approximation error for a hard subset membership problem with instance error and subset error . The scheme below, with message space , is IND-CPA-secure when is negligible: for every efficient there is an efficient with — CS02.
\begin{algorithm}
\algname{Algorithm}
\caption{Encryption from a hash proof system}
\begin{algorithmic}
\State $\KeyGen(1^\secpar)$: $\Lambda \gets \mathsf{I}(1^\secpar)$; $k \gets \mathsf{HPS}.\KeyGen(\Lambda)$; $s := \mathsf{Proj}(k)$; $\pk := (\Lambda, s)$; $\sk := k$
\State $\Enc(\pk, m)$: sample $(x, w)$ with the sampler of $\calM$; $\pi := \mathsf{Pub}(s, x, w)$
\Return $(x, m \cdot \pi)$
\State $\Dec(\sk, (x, e))$:
\Return $e \cdot \mathsf{Priv}(k, x)^{-1}$
\end{algorithmic}
\end{algorithm}
Sketch
Projectivity lets the reduction, which holds , compute the challenge mask as . An instance outside the support of the instance distribution occurs with probability at most ; on the others, replacing the sampled by costs . Replacing by costs the subset-membership advantage. On instances in the support, is then -close to the ideal family’s triple, which smoothness makes -close to for uniform , itself -close to ; a uniform mask hides perfectly. Each of the two challenge worlds is thus within of the same uniform-mask experiment.
Notes
- Adding to the ciphertext the value of an extended universal-2 hash proof system on , checked at decryption, gives IND-CCA2 security: Universal-2 HPS ⇒ CCA-secure PKE — CS02.
- For a universal hash proof system, a variant that passes the mask through a randomness extractor tolerates leakage of a bounded number of bits of , with no further assumption: Universal HPS ⇒ LR-PKE — NS09.