[Resource Topic] 2003/155: A Formal Proof of Zhu's Signature Scheme

Welcome to the resource topic for 2003/155

A Formal Proof of Zhu’s Signature Scheme

Authors: huafei zhu


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:
\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)).

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 .