CryptoDB

Paper: On the Security Loss of Unique Signatures

Authors: Andrew Morgan Rafael Pass DOI: 10.1007/978-3-030-03807-6_19 Search ePrint Search Google TCC 2018 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.
BibTeX
@inproceedings{tcc-2018-28996,
title={On the Security Loss of Unique Signatures},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={507-536},
doi={10.1007/978-3-030-03807-6_19},
author={Andrew Morgan and Rafael Pass},
year=2018
}