Quantitative reduction of Schnorr's identification scheme to DLP

Question

Question

I seek a quantitatively better proof of theorem 13.11 in Katz and Lindell's Introduction to Modern Cryptography (3^rd edition) (or nearly equivalently, theorem 19.1 in Dan Boneh and Victor Shoup's freely available A Graduate Course in Applied Cryptography). The proof is about the Schnorr identification scheme for a generic group $\mathcal G$ of prime order $q=\lvert\mathcal G\rvert$ and generator $g\in\mathcal G$, for the claim:

If the discrete-logarithm problem is hard relative to $\mathcal G$, then the Schnorr identification scheme is secure.

The scheme goes:

• Prover (P) draws private key $x\gets\mathbb Z_q$, compute and publishes public key $y:=g^x$, with integrity assumed.
• At each identification:
  1. Prover (P) draws $k\gets\mathbb Z_q$, computes and sends $I:=g^k$
  2. Verifier (V) draws and sends $r\gets\mathbb Z_q$
  3. Prover (P) computes and sends $s:=r\,x+k\bmod q$
  4. Verifier (V) checks whether $g^s\;y^{-r}\;\overset?=\;I$

The proof given is by contraposition. We assume a PPT algorithm $\mathcal A$ that, given $y$ but not $x$, successfully identifies with non-vanishing probability. We construct the following PPT algorithm $\mathcal A'$:

1. Run $\mathcal A(y)$, which is allowed to query and observe honest transcripts $(I,r,s)$, before reaching the next step.
2. When $\mathcal A$ outputs $I$, choose $r_1\gets\mathbb Z_q$ and give it to $\mathcal A$, which responds with $s_1$.
3. Run $\mathcal A(y)$ a second time with the same random tape and honest transcripts, and when it outputs (the same) $I$, choose $r_2\gets\mathbb Z_q$ with $r_2\ne r_1$ and give $r_2$ to $\mathcal A$.

   Eventually, $\mathcal A$, responds with $s_2$.

4. Compute $x:=(r_1-r_2)^{-1}(s_1-s_2)\bmod q$, solving the DLP.

Say step 2 completes with probability $\epsilon$. I get that the book's proof establishes step 3 completes with probability at least $\epsilon^2-1/q$, why step 4 solved the DLP, why the $\epsilon^2$ appears and why we need a large $q$ to approach that.

Can we reach a more quantitatively convincing reduction to the DLP ?

Unsatisfactory things are: the $\epsilon^2$, which can translate to low probability of success. We'd want a reduction where probability of success grows linearly with time spent, for low probability. Also, the probability of success is obtained averaged over all $y\in\mathcal G$, not for a particular DLP problem.

To make the first issue concrete: if $\mathcal A$ succeeds with probability $\epsilon=2^{-20}$ in $1$ second, the proof tells we can solve an average DLP with probability like $2^{-40}$ in $2$ seconds. That's not directly useful, even if we could turn it to probability $1/2$ in $2^{40}$ seconds (11 centuries). We want probability $1/2$ in $2^{21}$ seconds (25 days).

---

Tentative answer

This is my attempt, for criticism. I claim we can solve any particular DLP in $G$ with expected time $2t/\epsilon$ (and with probability $>4/5$ within time $3t/\epsilon$), plus time for identified tasks, assuming an algorithm $\mathcal A$ that identify for a random public key in time $t$ with non-vanishing probability $\epsilon$, and $q$ large enough we can discount hitting a particular value in a random choice in $\mathbb Z_q$.

Claimed proof:

First we build a new algorithm $\mathcal A_0$ that on input the description of the setup $(\mathcal G,g,q)$ and $h\in\mathcal G$

• uniformly randomly choose $u\gets\mathbb Z_q$
• computes $y:=h\;g^u$
• runs algorithm $\mathcal A$ with input $y$ serving as random public key
• whenever $\mathcal A$ requests an honest transcript $(I,r,s)$
  • uniformly randomly choose $r\gets\mathbb Z_q$ and $s\gets\mathbb Z_q$
  • compute $I:=g^s\;y^{-r}$
  • supply $(I,r,s)$ to $\mathcal A$, which is distinguishable from an honest transcript for public key $y$
• if $\mathcal A$ outputs $I$ within it's allocated run time $t$, making an attempt to authenticate
  • (note: we'll restart from here)
  • uniformly randomly chooses $r\gets\mathbb Z_q$ and passes it to $\mathcal A$
  • if $\mathcal A$ outputs $s$ within it's allocated run time $t$
    • checks $g^s\;y^{-r}\;\overset?=\;I$ and if so, outputs $(u,r,s)$
    • otherwise, aborts without result.

Algorithm $\mathcal A_0$ is a PPT algorithm that for any fixed input $h\in\mathcal G$ has at each run probability $\epsilon$ to outputs $(u,r,s)$, because $\mathcal A$ is run under the conditions defining $\epsilon$.

We make a new algorithm $\mathcal A_1$ that on input the setup $(\mathcal G,g,q)$ and $h\in\mathcal G$

• Repeatedly run $\mathcal A_0$ with that input until it outputs $(u,r_1,s_1)$. Each run has probability $\epsilon$ to succeed, thus this step is expected to require $t/\epsilon$ time running $\mathcal A$.
• Restart $\mathcal A_0$ from the noted restart point (equivalently: rerun it from start with the same input and random tape up to the restart point, with fresh randomness after the restart point), until it outputs $(u,r_2,s_2)$. Each run has probability at least $\epsilon$ to succeed (proof follows from that theorem on non-decreasing probability of success of an algorithm I try to ask a reference for), thus this step is expected to require no more than $t/\epsilon$ time running $\mathcal A$.
• In the (assumed overwhelmingly likely) case $r_1\ne r_2$, compute and output $z:=s_1-s_2-u\bmod q$.

In that outcome, both runs of $\mathcal A_0$ that produced $(u,r_1,s_1)$ and $(u,r_2,s_2)$ have checked $g^{s_i}\;y^{-{r_i}}=I$ with $y=h^u$ for the same $u$ and $I$ that $\mathcal A_0$ determined, and the $h$ we gave at input of $\mathcal A_1$. Therefore $\mathcal A_1$ found $z$ with $h=g^z$, thus solving the DLP for arbitrary $h$. It's expected run time spent in $\mathcal A$ is at most $2t/\epsilon$, and the rest makes $\mathcal O(\log(q))$ group operations for each run of $\mathcal A$ and each honest transcript it requires.

---

$\lfloor3/\epsilon\rfloor$ runs of $\mathcal A$ are enough for at least two of them to succeed with probability better than $1-4\,e^{-3}>4/5$: see this plot of $1-(1-\epsilon)^{\lfloor3/\epsilon\rfloor}-\lfloor3/\epsilon\rfloor\,\epsilon\,(1-\epsilon)^{\lfloor3/\epsilon\rfloor-1}$

Answer 1

$ \newcommand{\sR}{\mathcal{R}} \newcommand{\sG}{\mathcal{G}} \newcommand{\sB}{\mathcal{B}} $

This is the best rigorous analysis I could come up with -- it uses the Splitting Lemma, but decided to type it up anyway hoping someone might find it useful (please feel free to point out any errors).

(The analysis below is for a fixed DLP instance, but the ideas can be extended easily.)

Splitting Lemma [Lemma 1, PS]: Let $\sG\subseteq\sR_-\times\sR_+$ be such that $$\Pr_{(\rho_-,\rho_+)\in\sR_-\times\sR_+}[(\rho_-,\rho_+)\in\sG]\geq\epsilon.$$ For any $\beta<\epsilon$, define $$\sB:=\left\{(\rho_-,\rho_+)\in\sR_-\times\sR_+:\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG\right\}.$$ The following hold:

1. $\Pr[\sB|\sG]\geq\beta/\epsilon$ and
2. $\Pr_{\rho_+'\in\sR_+}[(\rho_-,\rho_+')\in\sG|(\rho_-,\rho_+)\in\sB]\geq \epsilon-\beta.$

Here, $\sG$ is the set of 'good' random coins in the sense these lead to the adversary being successful and $\sB\subseteq\sG$ is the subset of 'better' random coins in the sense that a rewind and replay using these coins is likely to be successful. The first conclusion of the lemma is that a good coins is better with probability at least $\beta/\epsilon$ and the second conclusion is that resampling a better coin will lead to a good coin with probability at least $\epsilon-\beta$.

The analysis of the first part of reduction is straightforward: the probability that all the $1/\epsilon$ executions fail is $1-(1-\epsilon)^{1/\epsilon}$. Let's assume, wlog, that the last execution succeeded. Let's denote the coins used by the adversary in this execution before and after the rewinding point by $\rho_-$ and $\rho_+$, respectively. By the Splitting Lemma, the probability that at least one of the replays succeeds is $$\frac{\beta}{\epsilon}\left((1-(1-(\epsilon-\beta))^{1/\epsilon}\right).$$ Here, $\beta/\epsilon$ is the probability that the last execution (which we know is good) is better (by conclusion $1$) and $(\epsilon-\beta)$ inside the braces is the probability that a resampling of the better coin leads to a good coin (by conclusion $2$).

To optimise the equation above, set $\beta=\epsilon(1-\epsilon)$ (which is close to $\epsilon$). This yields a success probability $(1-\epsilon)(1-(1-\epsilon^2)^{1/\epsilon})$.

[PS]: Pointcheval and Stern, Security Arguments for Digital Signatures and Blind Signatures, JoC 2000.

Answer 2

Let me try to answer your question:)

First of all, according to your description(I did not have the book you mentioned), this question belongs to provable security theory. The general idea of provable security is that: assuming that there an algorithm/adversary A can break a crypto-based scheme with non-negligible probablity e, then a simulator/challenger S can solve an instance of the mathematical problem, the scheme is based on by interacting with A with non-negligible probablity **e' <= e** determined by failure probability.

What's more, the process of security proof should be based on an adversary attack game/model, such as IND-CPA, EUF-CMA, etc., which defines the abilities of an adversary in that particular model. So, I think the proof given in your question part was based on EUF-DCMA, and the proof in your answer part was based on EUF-CMA.

In a simulation world created by simulator, the simulator can have some super power, by which it could solve an instance of a hard problem in real world according to the output of the adversary. The super power in the above proof is so-called rewind, a famous rewind simulation lemma, to extract secret value from adversary's outputs.

Now, let's take a look at the original proof. To sovle the DLP, the simulator rewinds A at the step 3. That is the A was ran twice, therefore the probability of successfully extracting x is $e'=e*e=e^2$, due to this being a continous event. Furthermore, in the step 3, the probability of $r_1=r_2$ is $1/q$. So, we also need to minus $1/q$ to fix the final sucessful probability $e'=e^2-1/q$.

The process of security proof is a kind of thought experiment, like Schroedinger's Cat(maybe not appropriate), we have no need to put it into a real experiment. It is sufficient that we just reduce the security of the scheme to one or more hard problems.

The proof process you claimed is very interesting and out of my knowledge. There was a wonderful book to further understand provable security.