2026-07-22T04:53:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18337 2024-03-06T11:01:42Z ddc:004 open_access

Quantum Security of Subset Cover Problems Bouaziz-Ermann, Samuel Grilo, Alex B. Vergnaud, Damien Cryptography Random oracle model Quantum information The subset cover problem for k ≥ 1 hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, ...). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make Ω((k+1)^{-(2^k)/(2^{k+1}-1})⋅ N^{(2^{k}-1})/(2^{k+1}-1)}) queries to the underlying hash functions with codomain size N to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general (r,k)-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a r-chosen message attack (for r ≥ 1). We prove that a generic quantum algorithm needs to make Ω(N^{k/5}) queries to the underlying hash functions to find a (1,k)-subset cover. We also propose a quantum algorithm that finds a (r,k)-subset cover making O (N^{k/(2+2r)}) queries to the k hash functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samuel Bouaziz-Ermann and Alex B. Grilo and Damien Vergnaud 2023 Is Part Of LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2023.9 urn:nbn:de:0030-drops-183378 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode