Paper 2017/870

Tightly-Secure Signatures from Five-Move Identification Protocols

Eike Kiltz, Julian Loss, and Jiaxin Pan


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.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2017
SignaturesFive-Move Identification ProtocolsFiat-ShamirTightness
Contact author(s)
eike kiltz @ rub de
julian loss @ rub de
jiaxin pan @ kit edu
2017-09-13: received
Short URL
Creative Commons Attribution


      author = {Eike Kiltz and Julian Loss and Jiaxin Pan},
      title = {Tightly-Secure Signatures from Five-Move Identification Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2017/870},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.