How was the adversary's success probability calculated in this 2002 paper by Dodis, Katz, Xu, Yung about key-insulated signature schemes?

Question

In this paper ("Strong key insulated signature schemes" by by Dodis, Katz, Xu, Yung (2002)), I understand most of the proof for Lemma 1 (pg. 9); I struggle with how some of the probability is calculated though.

No need to read the paper, I think, all you need is the following:

Context

• Adversary $A$ breaks (the "new") scheme $\Pi$
• Challenger $A'$ wants to break the underlying scheme $\Theta$ using $A$
• The signing oracle takes as input a message and a time period $i$
• The maximum number of queries to the signing oracle is $q(k)$

Confusing part:

At some point,challenger $A'$ draws a random $r \in \{1,..,q(k)\}$ and then looks at the $r^{th}$ signing query that $A$ makes.

• If this query has as input a time period that was already used in a previous signing query, then abort the experiment.
• If this is the first time that this time period (denoted $i^*$) is queried, proceed.
• If $A$ at any time queries or has queried the "key exposure" oracle for time period $i^*$, also abort (key exposure = revealing the secret key for the queried period).

In the end, $A$ forges a signature for a time period $i$. (Adaptively, I think, so $i$ is not fixed in the beginning but A chooses it at the end.)

Then the paper says:

With probability at least $1/q(k)$, the experiment is not aborted and $i^∗ = i$ [..].

My guess

$P(\text{experiment not aborted } \wedge\, i^∗ = i) =\\ P(\text{period }i^* \text{not queried before } r^{th} \text{signing query } \wedge\, \text{no key exposure query for }i^* \wedge\, i^∗ = i )$

What now? I don't see how computing this can be so obvious; I can think of so many questions:

• Are those events all independent and therefore $P(\text{period }i^* \text{not queried before } r^{th} \text{signing query } \wedge\, \text{no key exposure query for }i^* \wedge\, i^∗ = i ) = P(\text{period }i^* \text{not queried before } r^{th} \text{signing query })*P(\text{no key exposure query for }i^*)*P( i^∗ = i )?$
• Is $P( i^∗ = i )=1/q(k)$ or is the probability higher that the adversary picks an $i$ for the forgery that they know something about (= that they have queried before)? Or do we assume that $A$'s queries are random? Why would we assume that?
• Is $P(\text{period }i^* \text{not queried before } r^{th} \text{signing query })$ the same for all $r$ or is it higher for small $r$ (="early" queries)? Does it depend on whether $P( i^∗ = i )$?

I'm honestly baffled that this probability is given without further explanation, I must be missing something elementary. Can you help?

Answer 1

The adversary $A$ breaks scheme $\Pi$ by generating some kind of forgery. Every forgery can be assigned some label $i$. This label $i$ is chosen by the adversary, but there are only a polynomial number of choices for $i$.

The reduction algorithm can set things up to look just like the world that $A$ expects. Additionally, the reduction algorithm can set things up with a specific $i^*$ in mind, so that if the adversary produces a forgery whose label happens to be $i^*$, then the reduction algorithm can successfully break scheme $\Theta$. Importantly, and this may be the thing you're missing, $A$'s view of things is independent of $i^*$. In other words, no matter what specific $i^*$ the reduction has in mind, it always produces a perfectly faithful simulation of the world that $A$ expects.

How should the reduction algorithm choose $i^*$? It cannot predict in advance what label the adversary's forgery will have. So instead it will choose $i^*$ uniformly at random from among the polynomially many choices.

Why does this work? Eventually the adversary outputs a forgery, and the forgery has some label $i$. If the adversary's entire view is independent of the choice of $i^*$, then the adversary's choice of $i$ is independent of the choice of $i^*$. Since $i^*$ is uniformly distributed and independent of $i$, we can say that $\Pr[i=i^*] = \frac{1}{\mbox{# of choices}}$.

---

In your setting, the "label" $i$ of a forgery is (apparently -- I followed your instruction to not actually read the paper) the index of the first signing-oracle query that is made using the time period named in the forgery. If the reduction algorithm can predict which signing-oracle query will be the first one made under the time period of the adversary's forgery, then it will do something special in response to that query (embed some information that will help it break $\Theta$). Of course it cannot predict this property of the forgery, so it guesses. There are only $q(k)$ possibilities for the identity of this "special" query.

In your setting, there is also some aborting going on, but this is a distraction to the real probability question. What's really going on is this: The reduction is only successful in breaking $\Theta$ when its guess $i^*$ equals the label $i$ of $A$'s forgery. The authors here are saying that the reduction might as well give up (i.e., abort) when it sees that its guess is going to be wrong. It would have been fine if they wrote the reduction algorithm to never abort, and instead just make a blind "stab in the dark" at breaking $\Theta$ in these cases.