Cryptology ePrint Archive: Report 2007/273

Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles

Mihir Bellare and Sarah Shoup

Abstract: We show how the Fiat-Shamir transform can be used to convert three-move identification protocols into two-tier signature schemes (a primitive we define) with a proof of security that makes a standard assumption on the hash function rather than modeling it as a random oracle. The result requires security of the starting protocol against concurrent attacks. We can show that numerous protocols have the required properties and so obtain numerous efficient two-tier schemes. Our first application is an efficient transform of any unforgeable signature scheme into a strongly unforgeable one, which uses as a tool any two-tier scheme. (This extends work of Boneh, Shen and Waters whose transform only applies to a limited class of schemes.) The second application is new one-time signature schemes that, compared to one-way function based ones of the same computational cost, have smaller key and signature sizes.

Category / Keywords: public-key cryptography / Fiat-Shamir transform, signatures, identification protocols, one-time signatures

Publication Info: A preliminary version of this paper appears in the proceedings of PKC 2007. This paper is a preprint of a paper accepted by the IET Information Security journal and is subject to Institution of Engineering and Technology Copyright. When the final version is published, the copy of record will be available at IET Digital Library.

Date: received 12 Jul 2007, last revised 10 Apr 2008

Contact author: sshoup at cs ucsd edu

Available format(s): PDF | BibTeX Citation

Note: The full version of the paper includes additional proofs and a section on the relations between two-tier schemes and one-time schemes. This section also explains in more detail the advantages of using our Fiat-Shamir derived one-time schemes over existing one-time schemes.

Version: 20080410:214159 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]