Universal HPS ⇒ LR-PKE
Statement
Let be an -universal hash proof system with key approximation error for a hard subset membership problem , with hash values in , and let be a pairwise-independent hash function indexed by its seed , an average-case strong randomness extractor by the average-case leftover hash lemma — DORS08. The scheme below, with message space , is -leakage-resilient for
with no assumption beyond the hardness of , and its efficiency is that of . For this is the bound of NS09; for the same argument applies with the average guessing probability below — standard.
\begin{algorithm}
\algname{Algorithm}
\caption{Leakage-resilient 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$; $\sigma \getsr \bits^d$; $\pi := \mathsf{Pub}(s, x, w)$
\Return $(x, \sigma, \mathsf{Ext}(\pi, \sigma) \oplus M)$
\State $\Dec(\sk, (x, \sigma, \psi))$:
\Return $\psi \oplus \mathsf{Ext}(\mathsf{Priv}(k, x), \sigma)$
\end{algorithmic}
\end{algorithm}
Sketch
Projectivity lets the reduction, which holds and so answers every leakage query, compute the challenge mask from ; replacing the sampled by costs the subset error on instances in the support of the instance distribution, the others having probability at most , and replacing by costs the subset-membership advantage. For and an instance in the support of the instance distribution, the probability of predicting from , averaged over , is at most for the ideal family and so at most for ; so has average min-entropy at least given , and bits of leakage on lower it by at most , so by the leftover hash lemma is statistically close to uniform given ‘s view when .
Notes
- Without leakage, a smooth hash proof system gives CPA-secure encryption with the mask itself: HPS ⇒ CPA-secure PKE — CS02.
- Known hash proof systems instantiate the construction under DDH and its -Linear variants, quadratic residuosity and DCR — NS09. A new hash proof system raises the leakage to a fraction of the secret key: DDH ⇒ LR-PKE, -Linear ⇒ LR-PKE — NS09.