I seek a quantitatively better proof of theorem 13.11 in Katz and Lindell's Introduction to Modern Cryptography (3rd 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}$


  • 1
    $\begingroup$ Your analysis seems to make sense. You might need to apply the Splitting Lemma of Pointcheval-Stern (Lemma 1 here) to analyse the running time since the probability space is not totally independent: you have a space $\mathcal{X}\times\mathcal{Y}$ with some property and given a random sample $(X,Y)$ from this space that is 'good', the goal is to estimate the probability of a correlated sample $(X,Y')$ with a random $Y'$ is also 'good'. Am I missing something here? $\endgroup$
    – ckamath
    Jun 26 '21 at 11:07
  • 1
    $\begingroup$ I'm trying to find a simpler proof route than the splitting lemma, and if I'm not rigorous, I miss at what point. My reasoning is that the restart has at least the same probability to succeed as any run from origin, because we restart from a point in a run that succeeded (and the linked theorem/assertion of mine, which I think is rigorous and useful). The probability that the restart uses $r_2=r_1$ (thus is unusable) is $1/q$ per rerun, thus bounded by $\lfloor3/\epsilon\rfloor/q$ [re-fixed] is we make all the runs sufficient for $4/5$ probability. I don't think I make any other approximation. $\endgroup$
    – fgrieu
    Jun 26 '21 at 12:19
  • $\begingroup$ So, if I understood correctly, you are interested in a counterexample where a non-rigorous analysis fails? $\endgroup$
    – ckamath
    Jun 26 '21 at 14:26
  • 1
    $\begingroup$ I'm asking if there is a hole in my proof, or a simpler one leading to a comparably good quantitative bound (when applied as in the paragraph before tentative answer). A way to exhibit a hole in the proof would be a counterexample $\mathcal A$ (which can be built on to of a DLP oracle) with probability $\epsilon$ of success within time $t$, but $\mathcal A_1$ not the claimed $>4/5-\lfloor3/\epsilon\rfloor/q$ probability of success after $\lfloor3/\epsilon\rfloor$ runs (start and restart combined) of the counterexample $\mathcal A$. $\endgroup$
    – fgrieu
    Jun 26 '21 at 14:42

$ \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.

  • $\begingroup$ @fgrieu: this appeared on eprint today (to appear at Crypto'21). $\endgroup$
    – ckamath
    Jul 23 '21 at 5:22

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.

  • $\begingroup$ I have only met EUF-CMA and EUF-DCMA in the context of signature. Here the context is a 3-round identification scheme/protocol, thus can be the basis of a signature scheme, thru the FIat-Shamir transform, if we add a hash, and a message to sign; here, there's neither, and EUF-CMA vs EUF-DCMA is about the interactive vs non-interactive choice of messages. The closest is $I$, but my mind hurts at why my proof makes the choice of $I$ interactive where the original proof makes it non-interactive. Update: Katz's book on signature looks great! $\endgroup$
    – fgrieu
    Jun 24 '21 at 5:36
  • $\begingroup$ @fgrieu In general, most of identification schemes were non-interactive. In my impression, the Schnorr identification scheme was also called Sigma protocol belonging to challenge-response authentication method. As you said, it can be transfromed to non-interactive scheme by using FIat-Shamir method. But I do not understand what makes your mind hurt, in the whole process of proof, S plays the role of signer or verifer to interact with A to meet what A wants. So we dont need to care with how the A generates I or signature s in PPT, in other words, we can think of A as a blackbox. $\endgroup$
    – ming alex
    Jun 24 '21 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.