International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On the Security Loss of Unique Signatures

Andrew Morgan
Rafael Pass
DOI: 10.1007/978-3-030-03807-6_19
Search ePrint
Search Google
Conference: TCC 2018
Abstract: 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.
  title={On the Security Loss of Unique Signatures},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  author={Andrew Morgan and Rafael Pass},