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:


  • 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?


1 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.

  • $\begingroup$ Ok, thanks! I think your point that the adversary's view is independent of what the challenger guesses has brought home an important message: The adversary is not trying to sabotage the challenger because it doesn't care about the challenger's background stuff with $\Theta$, only about having the right environment to forge a signature for $\Pi$. Right? But: Are you saying that the probability of abortion does not play any role here? Or are you saying that $P(\text{experiment not aborted } \wedge\, i^* = i)$ is exactly the same as $P(\text{Challenger guesses the right label})=1/q(k)?$ $\endgroup$
    – phi.nm
    Commented Aug 21, 2021 at 8:42
  • $\begingroup$ I also just understood that my second question ("Does $A$ pick a label for the forgery that it knows something about (= has used in a query)?") doesn't apply, because the proof considers two cases, and the part we're in handles the case "$A$ uses a queried label for the forgery" - I only didn't recognize that. Does that influence the probability of $i^*=i$? After all $\endgroup$
    – phi.nm
    Commented Aug 21, 2021 at 10:46
  • $\begingroup$ - sorry , previous comment continued - Does that influence the probability of $i^*=i$? After all, the proof says that the probability is "at least $1/q(k)$", not "equal to". My thoughts: The pool of possible labels is smaller (if anything), meaning the probability to guess correctly is higher (if anything). Right? Or does your explanation cover the "at least" part already, because that has something to do with the abortion? $\endgroup$
    – phi.nm
    Commented Aug 21, 2021 at 10:54
  • $\begingroup$ I don't know why the proof says probability "at least $1/q$" instead of "exactly $1/q$." But I can see that you can cause the actual probability to be $1/q'$, where $q'$ is the number of distinct time-values queried to the signing oracle. So $q'=q$ only if the adversary never repeats a time-value in a signing query, and otherwise $q'\le q$. If a signing query is not the first to use a particular time-value then it can't be the label of the forgery. Since $q'\le q$, then also $1/q' \ge 1/q$. Maybe this is what they have in mind by saying "probability at least $1/q$" ? $\endgroup$
    – Mikero
    Commented Aug 21, 2021 at 16:19
  • $\begingroup$ Ok, yes - that's what I was trying to say with my "pool of labels"-explanation :-) And $P(\text{Challenger guesses right label}) = P(\text{not aborted and guesses right label})$, because abortion only occurs when the label isn't guessed correctly, so they're the same event. Right? $\endgroup$
    – phi.nm
    Commented Aug 22, 2021 at 9:01

Your Answer

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

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