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
-
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}
}
