Optimal Security Reductions for Unique Signatures: Bypassing Impossibilities with A Counterexample.
Fuchun Guo, Rongmao Chen, Willy Susilo, Jianchang Lai, Guomin Yang, Yi Mu · Research Online (University of Wollongong) · 2017
Optimal security reductions for unique signatures (Coron, Eurocrypt 2002) and their generalization, i.e., efficiently re-randomizable signatures (Hofheinz et al. PKC 2012 & Bader et al. Eurocrypt 2016) have been well studied in the literature. Particularly, it has been shown that under a non-interactive hard assumption, any security reduction (with or without random oracles) for a unique signature scheme or an efficiently re-randomizable signature scheme must loose a factor of at least \(q_s\) in the security model of existential unforgeability against chosen-message attacks (EU-CMA), where \(q_s\) denotes the number of signature queries. Note that the number \(q_s\) can be as large as \(2^{30}\) in practice. All unique signature schemes and efficiently re-randomizable signature schemes are concluded to be accompanied with loose reductions from these impossibility results.