Paper 2026/707

Alternating Sponge: A Low-Memory Hash Function with Beyond-Birthday-Bound Security

Yaobin Shen, School of Informatics, Xiamen University, Xiamen

Hailun Yan, School of Cryptology, University of Chinese Academy of Sciences, Beijing

Lei Wang, Shanghai Jiao Tong University, Shanghai

Dawu Gu, Shanghai Jiao Tong University, Shanghai

Abstract

We propose the \emph{Alternating Sponge} (ASP), a permutation-based hashing mode that explores how to obtain beyond-birthday-bound security without duplicating the full capacity state. The main design idea is to replace spatial state duplication by temporal alternation: ASP keeps two \(r\)-bit rate branches but lets them share a single \(c\)-bit capacity chain, and updates the two branches through alternating calls to two independent \((r+c)\)-bit permutations. This yields a state size of \(2r+c\) bits and outputs \(2r\) bits per mode-level squeezing round. We prove that ASP is indifferentiable from a random oracle in the ideal permutation model. For the base primitive-call budget \(q=q_P+\lambda\), the bound gives a capacity-driven term of order \(O(q^3/2^{2c})\), together with a primitive-space term of order \(O(q^2/2^{r+c})\). This yields the asymptotic security level \(\min\{\frac{2c}{3},\frac{r+c}{2}\}\). In particular, for \(r\ge \frac{c}{3}\), ASP reaches the \(\frac{2c}{3}\) capacity-driven exponent while saving one \(c\)-bit capacity component compared with a fully duplicated two-branch design. We also discuss generic distinguishing attacks, including a construction-level state-merging birthday attack and a simulator-specific attack, which clarify the current proof--attack gap.

@misc{cryptoeprint:2026/707,
      author = {Ziyang Luo and Yaobin Shen and Hailun Yan and Lei Wang and Dawu Gu},
      title = {Alternating Sponge: A Low-Memory Hash Function with Beyond-Birthday-Bound Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/707},
      year = {2026},
      url = {https://eprint.iacr.org/2026/707}
}