Paper 2018/905

On the Security Loss of Unique Signatures

Andrew Morgan and Rafael Pass

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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2018
Keywords
unique signaturessecurity lossblack-box impossibilitylinear-preserving reductionmeta-reduction
Contact author(s)
asmorgan @ cs cornell edu
History
2018-09-25: received
Short URL
https://ia.cr/2018/905
License
Creative Commons Attribution
CC BY

BibTeX

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