Paper 2016/191

Optimal Security Proofs for Signatures from Identification Schemes

Eike Kiltz, Daniel Masny, and Jiaxin Pan

Abstract

We perform a concrete security treatment of digital signature schemes obtained from canonical identification schemes via the Fiat-Shamir transform. If the identification scheme is rerandomizable and satisfies the weakest possible security notion (key-recoverability), then the implied signature scheme is unforgeability against chosen-message attacks in the multi-user setting in the random oracle model. The reduction loses a factor of roughly Qh, the number of hash queries. Previous security reductions incorporated an additional multiplicative loss of N, the number of users in the system. As an important application of our framework, we obtain a concrete security treatment for Schnorr signatures. Our analysis is done in small steps via intermediate security notions, and all our implications have relatively simple proofs. Furthermore, for each step we show the optimality of the given reduction via a meta-reduction.

Note: This work subsumes and extends ePrint report 2015/1122.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
SignaturesIdentificationSchnorrtightness
Contact author(s)
eike kiltz @ rub de
History
2017-11-29: last of 2 revisions
2016-02-23: received
See all versions
Short URL
https://ia.cr/2016/191
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/191,
      author = {Eike Kiltz and Daniel Masny and Jiaxin Pan},
      title = {Optimal Security Proofs for Signatures from Identification Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/191},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/191}},
      url = {https://eprint.iacr.org/2016/191}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.