Cryptology ePrint Archive: Report 2016/191
Optimal Security Proofs for Signatures from Identification Schemes
Eike Kiltz and 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.
Category / Keywords: public-key cryptography / Signatures, Identification, Schnorr, tightness
Date: received 23 Feb 2016, last revised 21 Mar 2016
Contact author: eike kiltz at rub de
Available format(s): PDF | BibTeX Citation
Note: This work subsumes and extends ePrint report 2015/1122.
Version: 20160321:204914 (All versions of this report)
Short URL: ia.cr/2016/191
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]