# Security proof of partially blind signature (schnorr signature based)

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.

Thanks.

## 1 Answer

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.

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