Abstract
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 hashfunction based signature scheme HORS. The security of many hashbased 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 rchosen 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.
BibTeX  Entry
@InProceedings{bouazizermann_et_al:LIPIcs.ITC.2023.9,
author = {BouazizErmann, Samuel and Grilo, Alex B. and Vergnaud, Damien},
title = {{Quantum Security of Subset Cover Problems}},
booktitle = {4th Conference on InformationTheoretic Cryptography (ITC 2023)},
pages = {9:19:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772716},
ISSN = {18688969},
year = {2023},
volume = {267},
editor = {Chung, KaiMin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18337},
URN = {urn:nbn:de:0030drops183378},
doi = {10.4230/LIPIcs.ITC.2023.9},
annote = {Keywords: Cryptography, Random oracle model, Quantum information}
}
Keywords: 

Cryptography, Random oracle model, Quantum information 
Collection: 

4th Conference on InformationTheoretic Cryptography (ITC 2023) 
Issue Date: 

2023 
Date of publication: 

21.07.2023 