Cryptology ePrint Archive: Report 2015/878

Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model

Edward Eaton and Fang Song

Abstract: Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions.

This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.

Category / Keywords: public-key cryptography / quantum cryptography

Date: received 9 Sep 2015

Contact author: ted at eeaton ca

Available format(s): PDF | BibTeX Citation

Note: To appear in Proceedings of TQC2015

Version: 20150913:191907 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]