  The subset cover problem for $k \geq 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+, $\dots$).
  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 $\Omega\left((k+1)^{-\frac{2^{k}}{2^{k+1}-1}}\cdot
N^{\frac{2^{k}-1}{2^{k+1}-1}}\right)$ 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 \geq 1$). We prove that a generic quantum
algorithm needs to make $\Omega\left(N^{k/5}\right)$ 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\left(N^{k/(2+2r)}\right)$ queries to the $k$ hash functions.
