Cryptology ePrint Archive: Report 2017/870

Tightly-Secure Signatures from Five-Move Identification Protocols

Eike Kiltz and Julian Loss and Jiaxin Pan

Abstract: We carry out a concrete security analysis of signature schemes obtained from five-move identification protocols via the Fiat-Shamir transform. Concretely, we obtain tightly-secure signatures based on the computational Diffie-Hellman (CDH), the short-exponent CDH, and the Factoring (FAC) assumptions. All our signature schemes have tight reductions to search problems, which is in stark contrast to all known signature schemes obtained from the classical Fiat-Shamir transform (based on three-move identification protocols), which either have a non-tight reduction to a search problem, or a tight reduction to a (potentially) stronger decisional problem. Surprisingly, our CDH-based scheme turns out to be (a slight simplification of) the Chevallier-Mames signature scheme (CRYPTO 05), thereby providing a theoretical explanation of its tight security proof via five-move identification protocols.

Category / Keywords: Signatures, Five-Move Identification Protocols, Fiat-Shamir, Tightness

Original Publication (in the same form): IACR-ASIACRYPT-2017

Date: received 7 Sep 2017

Contact author: eike kiltz at rub de, julian loss at rub de, jiaxin pan at kit edu

Available format(s): PDF | BibTeX Citation

Version: 20170913:212030 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]