2026-07-25T08:26:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5554 2024-03-06T10:36:40Z ddc:004 open_access

Making Existential-unforgeable Signatures Strongly Unforgeable in the Quantum Random-oracle Model Eaton, Edward Song, Fang digital signatures strongly unforgeable quantum random-oracle lattices 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edward Eaton and Fang Song 2015 Is Part Of LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2015.147 urn:nbn:de:0030-drops-55540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.147 eng https://creativecommons.org/licenses/by/3.0/legalcode