Tightly-Secure Signatures from Five-Move Identification Protocols

Eike Kiltz; Julian Loss; Jiaxin Pan

Paper 2017/870

Tightly-Secure Signatures from Five-Move Identification Protocols

Eike Kiltz, 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.

Metadata

Available format(s): PDF
Publication info: Published by the IACR in ASIACRYPT 2017
Keywords: Signatures Five-Move Identification Protocols Fiat-Shamir Tightness
Contact author(s): eike kiltz @ rub de
julian loss @ rub de
jiaxin pan @ kit edu
History: 2017-09-13: received
Short URL: https://ia.cr/2017/870
License: CC BY

BibTeX

@misc{cryptoeprint:2017/870,
      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},
      url = {https://eprint.iacr.org/2017/870}
}