Welcome to the resource topic for
**2003/155**

**Title:**

A Formal Proof of Zhu’s Signature Scheme

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2003/155

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .