I read a representative paper about partially blind signature.

Abe and Okamoto - "provably secure partially blind signature".

They suggested a partially blind signature scheme based on Schnorr signature.

In the security proof section, they proved that the scheme is secure against adaptive chosen message attack using ID reduction scheme.

They assume a single-info adversary, $U^{*}$ that violates unforgeability for infinitely many sizes.

And the machine ${M}$ is constructed by a forger ${U^*}$.

Firstly, ${M}$ select $b$ (0 or 1, randomly) and assigns $(y, z)=(g^{x}, z_{0}g^{\gamma})$ if $b=0$, or $(y, z)=(z_{0}g^{\gamma}, g^{w})$ if $b=1$.

$\gamma, x$ (or $w$) is chosend randomly.

Random oracle $F$ is defined so that it returns appropriate value of $z$ according to above selection.

Let's assume that $b=0$.

If $U^{*}$ is successful with probability at least $\eta$, then the author says we can find a random tape string for $U^{*}$ with probability at least 1/2 such that $U^{*}$ succeeds with probability $\eta/2$.

I cannot understand what 'finding a random tape' means.

Does it mean finding $\gamma$ and $x$?

Why is it 1/2 and $\eta/2$ ?

Below is a capture of the paper.

enter image description here

enter image description here Thanks.


1 Answer 1


It follows by the probing strategy/heavy-row lemma, which traces back to [Oka,FFS]. Read §6 in this paper for a nicer explanation.

References: [Oka]: Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. CRYPTO 1992. [FFS]: Feige, Fiat and Shamir. Zero-knowledge proofs of identity. JoC 1988.

  • $\begingroup$ Another good resource on the heavy row lemma is Hazay/Lindell's textbook: "Efficient secure two party protocols," Chapter 6.3 - "Proofs of Knowledge" $\endgroup$
    – Grifball
    Commented Apr 9, 2022 at 13:50

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.