License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2015.147
URN: urn:nbn:de:0030-drops-55540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5554/
Go to the corresponding LIPIcs Volume Portal

Eaton, Edward ; Song, Fang

Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model

pdf-format:
10.pdf (0.6 MB)

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. [Teranishi/Oyama/Ogata, Cryptology-Indocrypt 2006] 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. [Cash/Hofheinz/Kiltz/Peikert, J. of Cryptology 2012], 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.

BibTeX - Entry

@InProceedings{eaton_et_al:LIPIcs:2015:5554,
  author =	{Edward Eaton and Fang Song},
  title =	{{Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{147--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Salman Beigi and Robert Koenig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5554},
  URN =		{urn:nbn:de:0030-drops-55540},
  doi =		{10.4230/LIPIcs.TQC.2015.147},
  annote =	{Keywords: digital signatures, strongly unforgeable, quantum random-oracle, lattices}
}

Keywords: digital signatures, strongly unforgeable, quantum random-oracle, lattices
Collection: 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Issue Date: 2015
Date of publication: 04.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI