7
$\begingroup$

Many signature schemes use forking lemma to prove security, like scheme in here.In short, that goes through a reduction technique which called oracle-replay attack to solve the difficult algorithmic problem, requiring two rounds of simulation for $\mathcal{F}$ to obtain two valid signature pairs $(m,r,e,s)$ and $(m,r,e',s')$,where $r$ is a "commitment", $e = H(m||r)$,$s$ and $s'$ is related to $m$, $r$ and $e$. But how to ensure the forger $\mathcal{F}$ will output the same message $m$ and $r$ ,since they may select randomly in each simulation?

see also [PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

We use the fact that forger $\mathcal{F}$ is nothing else but a Turing machine with some random tape. And since $\mathcal{F}$ is in our possession, we can choose the tape. Therefore, we can rerun $\mathcal{F}$ with the same tape, and behavior of $\mathcal{F}$ will be just the same (until the point where the oracle will return different value and desired "forking" occurs).

Improve this answer
$\endgroup$
2
  • $\begingroup$ if we see forger as a Turing machine, is the security argument reliable, or it is proved security in ideal world? Since in the simulation forger behaviors extremely different from which in practical and we may cannot make "forking" in real world $\endgroup$
    – Laura
    Apr 3, 2019 at 11:38
  • 2
    $\begingroup$ Right, we always prove security only in some "ideal" model. Regarding this model, the assumption about a Turing machine is pretty reasonable, so the proof (or, if you prefer, argument) is reliable. Btw, all the computational complexity theory is based mainly on Turing model, including even the Discrete Log Problem assumption. $\endgroup$
    – Mikhail Koipish
    Apr 4, 2019 at 6:34
2
$\begingroup$

The forger $F$ is a probabilistic Turing machine, i.e., a deterministic Turing machine with a random tape, but reusing the same random tape only cannot generate the same $(m,r)$.

In the simulation, the "outside" adversary $A$ (against some hard problem) runs $F$ in a black-box way and controls its random tape which contains fair random bits. For each $F$ execution, $A$ samples the random tape $r_F$ for $F$ and the random coins $r_H$ for answering random oracle $H$ queries. Note that for each sampled random tape, $A$ runs $F$ twice. In the second run, $A$ rewinds $F$ to the point where $H(m,r)$ was queried and then answers it with an independent random value $e'$. Because $A$ uses the same random tape $r_F$ and the same front portion (prior to answering $H(m,r)$) of $r_H$, $F$'s behaviour until querying $H(m,r)$ is fully determined and therefore will generate the same $(m,r)$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So, in this two simulations, forger $F$ is given by the same random tape, while the message m , "commitment " r is determined by this randomness, so m and r are the same. Can i think in this way ? Is "random tape" here given by simulation means as the randomness given by the challenger when interacting with the forger in the attack environment ? $\endgroup$
    – Laura
    Apr 5, 2019 at 3:12
  • $\begingroup$ @Laura To get the same (m,r), $A$ needs to fix both the same random tape used for $F$'s execution and the same random coins for answering queries (before $H(m,r)$) to the random oracle $H$. In the real world execution, the challenger only interacts with the forger and never determines its randomness. In the simulation, you can think $A$ pretends to be the challenger but has strong power, e.g., rewinding the forger. $\endgroup$
    – Shan Chen
    Apr 5, 2019 at 3:32
  • $\begingroup$ I see, then in this simulation, all things are the same except the answering queries from $H$(after $H(m,r)$)).And is the power that reduction A could fix the same random tape for adversary in this simulation also can be used reasonably used in other reduction proof? $\endgroup$
    – Laura
    Apr 5, 2019 at 4:02
  • $\begingroup$ @Laura Yes. Actually, in other reduction proofs, if you don't use forking lemma, then maybe not necessary to fix the same random tape for two executions. The "outside" $A$ still samples the random tape for the "inside" probabilistic black-box algorithm, but for each execution $A$ samples an independent random tape for it. This is useful in the sense that you can now view the "inside" algorithm as a deterministic algorithm running according to the tape. $\endgroup$
    – Shan Chen
    Apr 5, 2019 at 4:08
  • $\begingroup$ For every run, $A$ samples an independent random tape for forger, looks like the same as in the real world execution forger, run with the random tape by itself (both of them are in random distribution). So why we need $A$ to do that (samples an independent random tape for forger) or are there advantages when we view the "inside" algorithm as a deterministic algorithm? $\endgroup$
    – Laura
    Apr 5, 2019 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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