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

Edward Eaton; Fang Song

Paper 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.

Note: To appear in Proceedings of TQC2015

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: quantum cryptography
Contact author(s): ted @ eeaton ca
History: 2015-09-13: received
Short URL: https://ia.cr/2015/878
License: CC BY

BibTeX

@misc{cryptoeprint:2015/878,
      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},
      url = {https://eprint.iacr.org/2015/878}
}