Considering security against quantum adversaries, while it is important to consider the traditional existential unforgeability (EUF-CMA security), it is desirable to consider security against adversaries making quantum queries to the signing oracle: Plus-one security ( \({ \textsc {PO}}\) security) and blind unforgeability ( \({ \textsc {BU}}\) security) proposed by Boneh and Zhandry (Crypto 2013) and Alagic et al. (EUROCRYPT 2020), respectively. Hash-and-sign is one of the most common paradigms for constructing \({ \textsc {EUF-CMA}}\) -secure signature schemes in the quantum random oracle model, employing a trapdoor function and a hash function. It is known that its derandomized version is \({ \textsc {PO}}\) - and \({ \textsc {BU}}\) -secure. A variant of hash-and-sign, known as hash-and-sign with retry ( \(\text {HSwR}\) ), formulated by Kosuge and Xagawa (PKC 2024), is widespread since it allows for weakening the security assumptions of a trapdoor function. Unfortunately, it has not been known whether \(\text {HSwR}\) can achieve \({ \textsc {PO}}\) - and \({ \textsc {BU}}\) -secure even with derandomization. In this paper, we apply a derandomization with bounded loops to \(\text {HSwR}\) . We demonstrate that \(\text {HSwR}\) can achieve \({ \textsc {PO}}\) and \({ \textsc {BU}}\) security through this approach. Since derandomization with bounded loops offers advantages in some implementations, our results support its wider adoption, including in NIST PQC candidates.

The Security of Hash-and-Sign with Retry Against Superposition Attacks

会议论文
发表日期：

2025年

查看全文

Haruhisa Kosuge,
Keita Xagawa

摘要

Considering security against quantum adversaries, while it is important to consider the traditional existential unforgeability (EUF-CMA security), it is desirable to consider security against adversaries making quantum queries to the signing oracle: Plus-one security ( \({ \textsc {PO}}\) security) and blind unforgeability ( \({ \textsc {BU}}\) security) proposed by Boneh and Zhandry (Crypto 2013) and Alagic et al. (EUROCRYPT 2020), respectively. Hash-and-sign is one of the most common paradigms for constructing \({ \textsc {EUF-CMA}}\) -secure signature schemes in the quantum random oracle model, employing a trapdoor function and a hash function. It is known that its derandomized version is \({ \textsc {PO}}\) - and \({ \textsc {BU}}\) -secure. A variant of hash-and-sign, known as hash-and-sign with retry ( \(\text {HSwR}\) ), formulated by Kosuge and Xagawa (PKC 2024), is widespread since it allows for weakening the security assumptions of a trapdoor function. Unfortunately, it has not been known whether \(\text {HSwR}\) can achieve \({ \textsc {PO}}\) - and \({ \textsc {BU}}\) -secure even with derandomization. In this paper, we apply a derandomization with bounded loops to \(\text {HSwR}\) . We demonstrate that \(\text {HSwR}\) can achieve \({ \textsc {PO}}\) and \({ \textsc {BU}}\) security through this approach. Since derandomization with bounded loops offers advantages in some implementations, our results support its wider adoption, including in NIST PQC candidates.