Im trying to comprehend a proof from the paper "Efficient Identity Based Signature Schemes Based on Pairings"(2002) by Florian Hess. At one point of the proof for Theorem 2 I don't understand how the cardinality is concluded. Summarized my problem is the following:
We have a machine C that replays a machine B at most $\frac{2}{\epsilon_B} + \frac{14n_2}{\epsilon_B}$ times where $\epsilon_B$ is the probability for machine B to suceeds on its own and where $n_2$ is the number of queries B asks. By replaying B machine C produces two valid signatures $(\mu_1,r)$ and $(\mu_2,r)$ with message hash $h_1(m,r)$ and $h_2(m,r)$ for the same m,r. The first $\frac{2}{\epsilon_B}$ are to generate the first signature and the $\frac{14n_2}{\epsilon_B}$ replays are to produce the second signature by applying the forking lemma. The forking lemma is applied in regard to a random tape $\delta \in (\mathbb{Z} / l \mathbb{Z})^\times \times (\mathbb{Z} / l \mathbb{Z})^\times $ which is used to answer the $n_2$ queries for $h(m,r)$. Every entry of $\delta$ is used as $(v,w)$ to answer the queries. The value of $m,r$ stays the same up until the point $\beta$ where the random tape forks: $\delta =(\delta_j)$ for $j<\beta$. From this the conclusion is drawn that the $h_i(m,r)$ are randomly chosen from the set of successful hash values $\delta_\beta$ which has the cardinality $\geq \frac{\epsilon_B(l-1)^2}{14n_2}$ (with $l$ being the security parameter). Why is the cardinality of this set $\geq \frac{\epsilon_B(l-1)^2}{14n_2}$?


Your Answer

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

Browse other questions tagged or ask your own question.