Tight Bounds on Uniform-Challenge Reductions from Sigma Protocols via Hitting Games - Introduction
Our Results
Interactive Sigma Protocols
Definition 1.1 (Black-box reductions, informal)
Algorithm $R$ is a black-box reduction from the $(t_2, \varepsilon_2)$-security of game $G_2$ to the $(t_1, \varepsilon_1)$-security of game $G_1$, if given any $A$ that breaks the $\varepsilon_2$-security of $G_2$, algorithm $R^A$ breaks the $\varepsilon_1$-security of $G_1$.
In addition, when charging $t_2$ steps for each $A$-call, $R^A$ runs in time $t_1$.
Definition 1.2 (Uniform-challenge reductions, informal)
A black-box reduction from the security of $G_\Sigma$ is uniform-challenge, if it samples the challenges it sends to $A$ uniformly and independently (in the challenge space specified by $\Sigma$).
Theorem 1.3 (Emulating uniform-challenge reductions, informal)
Let $R$ be a uniform-challenge reduction from the $(t_\Sigma, \varepsilon_\Sigma)$-security of $G_\Sigma$ to the $(t_G, \varepsilon_G)$-security of a game $G$.
Then, there exists an adversary $A$ that $\varepsilon_\Sigma$-breaks the security of $G_\Sigma$ and a (non oracle-aided) algorithm $R$ such that following holds:
- The execution of $(R, G)$ is $DH$-close to that of $(R^A, G)$ (in statistical distance), for $DH$ being the probability that $R^A$ asks $A$ two (different) challenges on which $A$ returns valid answers.
- The running time of $R$ is at most that of $R$ in $R^A$ (i.e., its running time without incurring any overhead for the oracle calls).
Corollary 1.4 (Bounds on uniform-challenge reductions, informal)
For any uniform-challenge reduction from the $(t_\Sigma, \varepsilon_\Sigma)$-security of $G_\Sigma$ to the $(t_G, \varepsilon_G)$-security of a game $G$:
if $G$ is $(t_G, t_G^2/s)$-secure, then
$$
\sqrt{\varepsilon_\Sigma} \in \Omega(t_\Sigma/\sqrt{s})
$$
Non-interactive Sigma Protocols
Definition 1.5 (Weakly-programming, black-box reductions, informal)
A black-box reduction from the security of $G_\Sigma^H$ is weakly programming
if when emulating an adversary $A$ that breaks the security of $G_\Sigma^H$, the reduction answers its oracle calls uniformly:
on input $x$ it either returns the answer it gave previously on $x$, or returns a uniform element in the domain,
i.e., “it resamples the oracle answer”.
on input $x$ it either returns the answer it gave previously on $x$, or returns a uniform element in the domain,
i.e., “it resamples the oracle answer”.
Corollary 1.6 (Bounds on weakly-programming reductions, informal)
For any weakly-programming reduction from the $(t_\Sigma, \varepsilon_\Sigma, b)$-security of $G_\Sigma^H$ to the $(t_G, \varepsilon_G)$-security of a game $G^H$:
if $G^H$ is $(t_G, t_G^2/s)$-secure
then $$ \varepsilon_\Sigma \in \Omega(\sqrt{b}\cdot t_\Sigma/\sqrt{s}) $$ if $(t_G/t_\Sigma)\varepsilon_\Sigma < 1$ and $$ \varepsilon_\Sigma \in \Omega(b \cdot t_G t_\Sigma/s) $$ otherwise.
if $G^H$ is $(t_G, t_G^2/s)$-secure
then $$ \varepsilon_\Sigma \in \Omega(\sqrt{b}\cdot t_\Sigma/\sqrt{s}) $$ if $(t_G/t_\Sigma)\varepsilon_\Sigma < 1$ and $$ \varepsilon_\Sigma \in \Omega(b \cdot t_G t_\Sigma/s) $$ otherwise.
High-Moment Reductions: Interactive Sigma Protocols
Corollary 1.7 (Bounds on uniform-challenge, higher-moment, reductions, informal)
For $d \ge 2$ and a uniform-challenge reduction from the $(t_\Sigma, \varepsilon_\Sigma, d)$-security of $G_\Sigma$ to the $(t_G, \varepsilon_G)$-security of a game $G$:
if $G$ is $(t_G, t_G/s, d)$-secure then $\varepsilon_\Sigma^{2-1/d} \in \Omega(t_\Sigma^d/s)$.
if $G$ is $(t_G, t_G/s, d)$-secure then $\varepsilon_\Sigma^{2-1/d} \in \Omega(t_\Sigma^d/s)$.
High-Moment Reductions: Non-interactive Sigma Protocols
Corollary 1.8 (Bounds on weakly-programmable, higher-moment, reductions)
For $d \ge 2$ and a weakly-programming reduction from the $(t_\Sigma, \varepsilon_\Sigma, d, b)$-security of $G_\Sigma$ to the $(t_G, \varepsilon_G)$-security of a game $G$:
if $G$ is $(t_G, t_G/s, d)$-secure
then $$ \varepsilon_\Sigma^{2-1/d} \in \Omega(b \cdot t_\Sigma^d/s) $$ if $(t_G^{1/d}/t_\Sigma)\varepsilon_\Sigma < 1$ and $$ \varepsilon_\Sigma^d \in \Omega(b \cdot t_\Sigma^d/s) $$ otherwise.
if $G$ is $(t_G, t_G/s, d)$-secure
then $$ \varepsilon_\Sigma^{2-1/d} \in \Omega(b \cdot t_\Sigma^d/s) $$ if $(t_G^{1/d}/t_\Sigma)\varepsilon_\Sigma < 1$ and $$ \varepsilon_\Sigma^d \in \Omega(b \cdot t_\Sigma^d/s) $$ otherwise.