From identification to signatures, tightly: A framework and generic transforms

Relations between security notions and summary of transformations from identification schemes into signature schemes.


This paper provides a framework to treat the problem of building signature schemes from identification schemes in a unified and systematic way. The outcomes are (1) Three alternatives to the Fiat-Shamir transform yielding signature schemes whose proofs give tight reductions to standard assumptions (2) An understanding and characterization of existing transforms in the literature. Reduction tightness is important because it allows the implemented scheme to use small parameters (thereby being as efficient as possible) while retaining provable security.

Keywords: identification, signatures, reduction tightness


Mihir Bellare, Bertram Poettering, Douglas Stebila. From identification to signatures, tightly: A framework and generic transforms. In Jung Hee Cheon, Tsuyoshi Takagi, editors, Advances in Cryptology — Proc. ASIACRYPT 2016, LNCS, vol. 10032, pp. 435-464. Springer, December 2016. © IACR.




This research was supported by:
  • Australian Research Council (ARC) Discovery Project grant DP130104304
  • Natural Sciences and Engineering Research Council (NSERC) of Canada Discovery grant RGPIN-2016-05146
  • NSF grants CNS-1228890 and CNS-1526801
  • A gift from Microsoft Corporation
  • ERC Project ERCC (FP7/615074)