Sponge-based constructions have successfully been receiving widespread adoption, as represented by the standardization of SHA-3 and Ascon by NIST. Yet, their provable security against quantum adversaries has not been investigated much. This paper studies the post-quantum security of some keyed sponge-based constructions in the quantum ideal permutation model, focusing on the Ascon AEAD mode and KMAC as concrete instances. For the Ascon AEAD mode, we prove the post-quantum security in the single-user setting up to about \(\min (2^{c/3},2^{\kappa /3})\) queries, where c is the capacity and \(\kappa \) is the key length. Unlike the recent work by Lang et al. (ePrint 2025/411), we do not need non-standard restrictions on nonce sets or the number of forgery attempts. In addition, our result guarantees even non-conventional security notions such as the nonce-misuse resilience confidentiality and authenticity under release of unverified plaintext. For KMAC, we show the security up to about \(\min (2^{c/3}, 2^{r/2},2^{(\kappa -r)/2})\) queries, where r is the rate, ignoring some small factors. In fact, we prove the security not only for KMAC but also for general modes such as the inner-, outer-, and full-keyed sponge functions. We take a modular proof approach, adapting the ideas by several works in the classical ideal permutation model into the quantum setting: For the Ascon AEAD mode, we observe it can be regarded as an iterative application of a Tweakable Even-Mansour \((\textsf{TEM})\) cipher with a single low-entropy key, and gives the security bound as the sum of the post-quantum TPRP advantage of \(\textsf{TEM}\) and the classical security advantage of Ascon when \(\textsf{TEM}\) is replaced with a secret random object. The proof for keyed sponges is obtained analogously by regarding them as built on an Even-Mansour ( \(\textsf{EM}\) ) cipher with a single low-entropy key. The post-quantum security of ( \(\textsf{T}\) ) \(\textsf{EM}\) has been proven by Alagic et al. (Eurocrypt 2022 and Eurocrypt 2024). However, they show the security only when the keys are uniformly random. In addition, the proof techniques, so-called the resampling lemmas, are inapplicable to our case with a low-entropy key. Thus, we introduce and prove a modified resampling lemma, thereby showing the security of ( \(\textsf{T}\) ) \(\textsf{EM}\) with a low-entropy key.

Post-Quantum Security of Keyed Sponge-Based Constructions Through a Modular Approach

会议论文
发表日期：

2026年

查看全文

Akinori Hosoyamada

摘要

Sponge-based constructions have successfully been receiving widespread adoption, as represented by the standardization of SHA-3 and Ascon by NIST. Yet, their provable security against quantum adversaries has not been investigated much. This paper studies the post-quantum security of some keyed sponge-based constructions in the quantum ideal permutation model, focusing on the Ascon AEAD mode and KMAC as concrete instances. For the Ascon AEAD mode, we prove the post-quantum security in the single-user setting up to about \(\min (2^{c/3},2^{\kappa /3})\) queries, where c is the capacity and \(\kappa \) is the key length. Unlike the recent work by Lang et al. (ePrint 2025/411), we do not need non-standard restrictions on nonce sets or the number of forgery attempts. In addition, our result guarantees even non-conventional security notions such as the nonce-misuse resilience confidentiality and authenticity under release of unverified plaintext. For KMAC, we show the security up to about \(\min (2^{c/3}, 2^{r/2},2^{(\kappa -r)/2})\) queries, where r is the rate, ignoring some small factors. In fact, we prove the security not only for KMAC but also for general modes such as the inner-, outer-, and full-keyed sponge functions. We take a modular proof approach, adapting the ideas by several works in the classical ideal permutation model into the quantum setting: For the Ascon AEAD mode, we observe it can be regarded as an iterative application of a Tweakable Even-Mansour \((\textsf{TEM})\) cipher with a single low-entropy key, and gives the security bound as the sum of the post-quantum TPRP advantage of \(\textsf{TEM}\) and the classical security advantage of Ascon when \(\textsf{TEM}\) is replaced with a secret random object. The proof for keyed sponges is obtained analogously by regarding them as built on an Even-Mansour ( \(\textsf{EM}\) ) cipher with a single low-entropy key. The post-quantum security of ( \(\textsf{T}\) ) \(\textsf{EM}\) has been proven by Alagic et al. (Eurocrypt 2022 and Eurocrypt 2024). However, they show the security only when the keys are uniformly random. In addition, the proof techniques, so-called the resampling lemmas, are inapplicable to our case with a low-entropy key. Thus, we introduce and prove a modified resampling lemma, thereby showing the security of ( \(\textsf{T}\) ) \(\textsf{EM}\) with a low-entropy key.