### 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.

Available format(s)
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
Short URL
https://ia.cr/2018/905

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},
note = {\url{https://eprint.iacr.org/2018/905}},
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.