Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / unique signatures, security loss, black-box impossibility, linear-preserving reduction, meta-reduction

Original Publication (with major differences): IACR-TCC-2018

Date: received 24 Sep 2018, last revised 24 Sep 2018

Contact author: asmorgan at cs cornell edu

Available format(s): PDF | BibTeX Citation

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

Version: 20180925:031951 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]