Paper 2003/155

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.