CryptoDB
Hybrid-query bounds with partial input control -- framework and application to tight M-eTCR
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | In this paper, we revisit the security of randomized hash & sign. More precisely, we present an improved security analysis for the underlying hash function property multi-target extended target collision resistance (M-eTCR) in the quantum random oracle model (QROM). While prior work relied on reprogramming techniques to handle adversarial challenge queries, we leverage the hybrid compressed oracle framework of Hamoudi, Liu, and Sinha to formulate an adaptive search problem. To do so, we had to extend their framework to cover partially randomized classical adversary queries. We conjecture that this extension will also allow to analyze further hash function properties that allow adversaries to define challenges via a classical oracle. By applying the extended framework to M-eTCR, we give an improved upper bound on the adversary's success probability. Our results show that the required key size for M-eTCR can be reduced by more than half (from 192 to 72 bits), and we prove the tightness of our bound in the number of queries via matching attacks. To illustrate practical impact, we optimize parameters for Falcon in the hash & sign paradigm, enabling more efficient instantiations with reduced salt sizes resulting in smaller signature lengths. For the example of multiple signatures aggregation, we achieve a signature size improvement of 30 kB for typical parameters. |
BibTeX
@inproceedings{asiacrypt-2025-36051,
title={Hybrid-query bounds with partial input control -- framework and application to tight M-eTCR},
publisher={Springer-Verlag},
author={Mikhail Kudinov and Andreas Hülsing and Christian Majenz},
year=2025
}