Paper 2015/878

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

Edward Eaton and Fang Song


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.

Note: To appear in Proceedings of TQC2015

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
quantum cryptography
Contact author(s)
ted @ eeaton ca
2015-09-13: received
Short URL
Creative Commons Attribution


      author = {Edward Eaton and Fang Song},
      title = {Making Existential-Unforgeable Signatures Strongly Unforgeable in the Quantum Random-Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2015/878},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.