License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2023.9
URN: urn:nbn:de:0030-drops-183378
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18337/
Bouaziz-Ermann, Samuel ;
Grilo, Alex B. ;
Vergnaud, Damien
Quantum Security of Subset Cover Problems
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 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.
BibTeX - Entry
@InProceedings{bouazizermann_et_al:LIPIcs.ITC.2023.9,
author = {Bouaziz-Ermann, Samuel and Grilo, Alex B. and Vergnaud, Damien},
title = {{Quantum Security of Subset Cover Problems}},
booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-271-6},
ISSN = {1868-8969},
year = {2023},
volume = {267},
editor = {Chung, Kai-Min},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18337},
URN = {urn:nbn:de:0030-drops-183378},
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 Information-Theoretic Cryptography (ITC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.07.2023 |
