Paper 2018/905

On the Security Loss of Unique Signatures

Andrew Morgan and Rafael Pass


We consider the question of whether the security of unique digital signature schemes can be based on game-based cryptographic assumptions using linear-preserving black-box security reductions—that is, black-box reductions for which the security loss (i.e., the ratio between "work" of the adversary and the "work" of the reduction) is some a priori bounded polynomial. A seminal result by Coron (Eurocrypt'02) shows limitations of such reductions; however, his impossibility result and its subsequent extensions all suffer from two notable restrictions: (1) they only rule out so-called "simple" reductions, where the reduction is restricted to only sequentially invoke "straight-line" instances of the adversary; and (2) they only rule out reductions to non-interactive (two-round) assumptions. In this work, we present the first full impossibility result: our main result shows that the existence of any linear-preserving black-box reduction for basing the security of unique signatures on some bounded-round assumption implies that the assumption can be broken in polynomial time.

Note: Full version of a paper (by the same title) to appear in TCC 2018.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2018
unique signaturessecurity lossblack-box impossibilitylinear-preserving reductionmeta-reduction
Contact author(s)
asmorgan @ cs cornell edu
2018-09-25: received
Short URL
Creative Commons Attribution


      author = {Andrew Morgan and Rafael Pass},
      title = {On the Security Loss of Unique Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/905},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.