Paper 2022/1474

Quantum security of subset cover problems

Abstract

The subset cover problem for $k\ge 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 $$ queries to the underlying hash functions with codomain size $$ 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 $$-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a $$-chosen message attack (for $$). We prove that a generic quantum algorithm needs to make $$ queries to the underlying hash functions to find a $$-subset cover. We also propose a quantum algorithm that finds a $$-subset cover making $$ queries to the $$ hash functions.