**A Formal Proof of Zhu's Signature Scheme**

*huafei zhu*

**Abstract: **Following from the remarkable works of Cramer and Shoup \cite{CS}, three trapdoor hash signature variations have been
presented in the literature: the first variation was presented in CJE'01 by Zhu \cite{Zhu}, the second variation was
presented in SCN'02 by Camenisch and Lysyanskaya \cite{CL} and the third variation was presented in PKC'03 by Fischlin
\cite{Fis}. All three mentioned trapdoor hash signature schemes have similar structure and the security of the last two
modifications is rigorously proved. We point out that the distribution of variables derived from Zhu's signing oracle
is different from that generated by Zhu's signing algorithm since the signing oracle in Zhu's simulator is defined over
$Z$, instead of $Z_n$. Consequently the proof of security of Zhu's signature scheme should be studied more precisely.
We also aware that the proof of Zhu's signature scheme is not a trivial work which is stated below:
\begin{itemize}
\item the technique presented by Cramer and Shoup \cite{CS} cannot be applied directly to prove the security of Zhu's
signature scheme since the structure of Cramer-Shoup's trap-door hash scheme is double deck that is easy to simulate a
signing query as the order of subgroup $G$ is a public parameter;
\item the technique presented by Camenisch and
Lysyanskaya \cite{CL} cannot be applied directly since there are extra security parameters $l$ and $l_s$ guide the
statistical closeness of the simulated distributions to the actual distribution;
\item the technique presented by
Fischlin cannot be applied directly to Zhu's signature scheme as the security proof of Fischlin's signature relies on a
set of pairs $(\alpha_i, \alpha_i \oplus H(m_i))$ while the security proof of Zhu's signature should rely on a set of
pairs $(\alpha_i, H(m_i))$.
\end{itemize}

In this report, we provide an interesting random argument technique to show that Zhu's signature scheme immune to adaptive chosen-message attack under the assumptions of the strong RSA problem as well as the existence of collision free hash functions.

**Category / Keywords: **

**Date: **received 5 Aug 2003, last revised 8 Aug 2003

**Contact author: **zhuhf at zju edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20030808:075709 (All versions of this report)

**Short URL: **ia.cr/2003/155

[ Cryptology ePrint archive ]