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

Mihir Bellare; Sarah Shoup

Paper 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.

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. 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.
Keywords: Fiat-Shamir transform signatures identification protocols one-time signatures
Contact author(s): sshoup @ cs ucsd edu
History: 2008-04-10: revised; 2007-07-16: received; See all versions
Short URL: https://ia.cr/2007/273
License: CC BY

BibTeX

@misc{cryptoeprint:2007/273,
      author = {Mihir Bellare and Sarah Shoup},
      title = {Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/273},
      year = {2007},
      url = {https://eprint.iacr.org/2007/273}
}