\documentclass{conjura-conjecture}

\newcommand{\Fun}{\mathsf{Fun}}
\newcommand{\Adv}{\mathbf{Adv}}
\newcommand{\Gm}{\mathsf{Game}}
\newcommand{\Pred}{\mathrm{Pred}}
\newcommand{\Ext}{\mathrm{Ext}}
\newcommand{\ExtP}{\mathrm{Ext}\text{-}\mathrm{pub}}
\newcommand{\pred}{\mathrm{pred}}
\newcommand{\ext}{\mathrm{ext}}
\newcommand{\extpub}{\textup{ext-pub}}
\newcommand{\sd}{\mathit{sd}}
\renewcommand{\sample}{\stackrel{{\scriptscriptstyle\$}}{\leftarrow}}
\newcommand{\SD}{\mathrm{SD}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\ret}{\textbf{return}\ }

\runninghead{LEFTOVER HASH LEMMA CONJECTURES}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Randomness Extraction from Unpredictable Random-Oracle Sources}
\cjsubtitle{Two Leftover-Hash-Lemma Conjectures}
\cjstatus{Statement: human-written, not yet formalized.}
\cjcategory{Information-Theoretic Cryptography.}

\vspace{0.4em}

\noindent\textbf{Setting.}
Fix nonempty finite sets $\calK$ (seeds), $\calD$ (inputs), $\calR$ (outputs), and write
$K := |\calK|$, $D := |\calD|$, $R := |\calR|$. Let $\Fun(\calK \times \calD, \calR)$ be the set of
all functions $\calK \times \calD \to \calR$, let $\SD(\cdot,\cdot)$ denote statistical distance and
$U_{\calR}$ the uniform distribution on $\calR$. The source $S$, the predictor $P$ and the
distinguisher $\mathsf{D}$ of Figure~\ref{fig:games} are computationally unbounded and receive the
\emph{entire} function table of $H$ as an explicit input. The two extraction games differ only in
whether the seed $\sd$ is kept secret from $\mathsf{D}$ or given to it.

\begin{figure}[ht]
\centering
\fbox{\begin{minipage}[t]{0.85\linewidth}
\underline{$\Gm\ \Pred^{S}_{P}$}\\[2pt]
$H \sample \Fun(\calK \times \calD, \calR)$;\quad
$(x,z) \sample S(H)$;\quad
$x' \sample P(H,z)$\\
$\ret (x = x')$
\end{minipage}}

\smallskip
\fbox{\begin{minipage}[t]{0.85\linewidth}
\underline{$\Gm\ \Ext^{S}_{\mathsf{D}}$ (secret seed)}\\[2pt]
$H \sample \Fun(\calK \times \calD, \calR)$;\quad
$(x,z) \sample S(H)$;\quad $\sd \sample \calK$\\
$y_0 \leftarrow H(\sd,x)$;\quad $y_1 \sample \calR$;\quad
$b \sample \{0,1\}$\\
$b' \sample \mathsf{D}(H, y_b, z)$;\quad
$\ret (b = b')$
\end{minipage}}

\smallskip
\fbox{\begin{minipage}[t]{0.85\linewidth}
\underline{$\Gm\ \ExtP^{S}_{\mathsf{D}}$ (public seed)}\\[2pt]
$H \sample \Fun(\calK \times \calD, \calR)$;\quad
$(x,z) \sample S(H)$;\quad $\sd \sample \calK$\\
$y_0 \leftarrow H(\sd,x)$;\quad $y_1 \sample \calR$;\quad
$b \sample \{0,1\}$\\
$b' \sample \mathsf{D}(H, \sd, y_b, z)$;\quad
$\ret (b = b')$
\end{minipage}}
\caption{Prediction game (top) and the two extraction games: secret seed (middle) and public seed
(bottom). The first argument of $S$, $P$ and $\mathsf{D}$ is the \emph{full function table} of $H$;
the games $\Ext$ and $\ExtP$ differ only in whether $\mathsf{D}$ receives $\sd$.}
\label{fig:games}
\end{figure}

\begin{definition}\label{def:games}
Set $\Adv^{\pred}_{\calK,\calD,\calR,S}(P) := \Pr[\Pred^{S}_{P} \Rightarrow 1]$ and
\[
  \Adv^{\ext}_{\calK,\calD,\calR}(S,\mathsf{D}) := 2\Pr[\Ext^{S}_{\mathsf{D}} \Rightarrow 1] - 1 ,
\]
\[
  \Adv^{\extpub}_{\calK,\calD,\calR}(S,\mathsf{D}) := 2\Pr[\ExtP^{S}_{\mathsf{D}} \Rightarrow 1] - 1 .
\]
A source $S$ is \emph{$\epsilon$-unpredictable} if
$\Adv^{\pred}_{\calK,\calD,\calR,S}(P) \le \epsilon$ for every unbounded predictor $P$.
\end{definition}

\begin{conjecture}[Secret seed]\label{conj:main}
There is a universal constant $c > 0$, independent of $\calK$, $\calD$, $\calR$ and $\epsilon$, such
that for all nonempty finite $\calK, \calD, \calR$, all $\epsilon \in (0,1]$, every
$\epsilon$-unpredictable source $S$ and every unbounded distinguisher $\mathsf{D}$,
\[
  \Adv^{\ext}_{\calK,\calD,\calR}(S,\mathsf{D})
  \;\le\; \delta(\epsilon, K, D, R)
  \;:=\; c \cdot \sqrt{\frac{\epsilon R + \log_2 D}{K}} \; .
\]
\end{conjecture}

\begin{conjecture}[Public seed]\label{conj:pub}
There is a universal constant $c > 0$, independent of $\calK$, $\calD$, $\calR$ and $\epsilon$, such
that for all nonempty finite $\calK, \calD, \calR$, all $\epsilon \in (0,1]$, every
$\epsilon$-unpredictable source $S$ and every unbounded distinguisher $\mathsf{D}$,
\[
  \Adv^{\extpub}_{\calK,\calD,\calR}(S,\mathsf{D})
  \;\le\; \delta_{\mathrm{pub}}(\epsilon, K, D, R)
  \;:=\; c \cdot \Bigl( \sqrt{\epsilon R} + \sqrt{\frac{\log_2 D}{K}} \,\Bigr) .
\]
\end{conjecture}

\end{document}
