1
$\begingroup$

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.

But I cannot understand the proof of Lemma 2 that the scheme is unforgeable.

Below image is part of the proof process. (p.281)

${M}$ is a machine constructed by a forger ${U^*}$, y is public key where ${y=g^x}$, ${F, H}$ is random oracles, and ${Info}$ means message.

enter image description here

Why ${M}$ outputs a valid signature with probability at least ${1-e^{-1}}$? (highlighted part)

Thanks.

$\endgroup$
2
$\begingroup$

If the probability (over random choice of the random tape $\rho$ and the random oracle $\mathcal{H}$) of a particular trial being successful is at least $\mu'$, then the probability that $1/\mu'$ independent trials* are unsuccessful is at most $(1-\mu')^{1/\mu'}$ --- this expression converges to $1/e$. The claim follows.

*Here, independence refers to the choice of $\rho$ and $\mathcal{H}$.

$\endgroup$

Your Answer

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

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