International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Mihir Bellare
Sarah Shoup
Download:
URL: http://eprint.iacr.org/2007/273
Search ePrint
Search Google
Abstract: We provide a positive result about the Fiat-Shamir (FS) transform in the standard model, showing how to use it to convert three-move identification protocols into two-tier signature schemes 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 a two-tier scheme based efficient transform of any unforgeable signature scheme into a strongly unforgeable one. (This extends Boneh, Shen and Waters [BSW06] 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.
BibTeX
@misc{eprint-2007-13554,
  title={Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Fiat-Shamir transform, signatures, identification protocols, one-time signatures},
  url={http://eprint.iacr.org/2007/273},
  note={A preliminary version of this paper appears in the proceedings of PKC 2007. This is the full version. sshoup@cs.ucsd.edu 13706 received 12 Jul 2007},
  author={Mihir Bellare and Sarah Shoup},
  year=2007
}