International Association
for Cryptologic Research

The sponge is a popular construction for hashing and keyed hashing, and the duplex for authenticated encryption. They are proven to achieve approximately 2c/2 security, where c is the so-called capacity. This approach generalizes to arithmetizationoriented constructions, that operate on elements from a finite field of size p: in this case, security is guaranteed up to pc/2. However, to hash securely, the sponge needs to injectively pad the message, and likewise, authenticated encryption schemes often flip bits in the inner part to ensure domain separation. While these bit manipulations have little (but non-zero) influence on the efficiency and security in case of a field of size 2, they become more profound for larger fields. For example, Reinforced Concrete operates on a field with p ≈ 2256, absorbs 2 elements per permutation evaluation, and has a capacity c = 1. Consequently, injective padding results in superfluous permutation evaluations half of the time, and domain separation in the inner part would reduce the capacity to 0 and thus void security. In this work, we investigate an alternative approach to padding and domain separation for the sponge through the use of non-cryptographic permutations (NCPs) to transform the inner state. The idea dates back to the Merkle-Damgård with permutation construction (ASIACRYPT 2007) but we use it in a much more generalized form in the sponge and in the duplex. We demonstrate that this approach allows for NCP-based padding and NCP-based domain separation at a constant loss, regardless of the size of the field. We apply our findings to arithmetization-oriented element-wise sponging (akin to the recently introduced SAFE) and authenticated encryption.

We provide security foundations for SAFE, a recently introduced API framework for sponge-based hash functions tailored to prime-field-based protocols. SAFE aims to provide a robust and foolproof interface, has been implemented in the Neptune hash framework and some zero-knowledge proof projects, but despite its usability and applicability it currently lacks any security proof. Such a proof would not be straightforward as SAFE abuses the inner part of the sponge and fills it with protocol-specific data. In this work we identify the SAFECore as versatile variant sponge construction underlying SAFE, we prove indifferentiability of SAFECore for all (binary and prime) fields up to around $|\mathbb{F}_p|^{c/2}$ queries, where $\mathbb{F}_p$ is the underlying field and $c$ the capacity, and we apply this security result to various use cases. We show that the SAFE-based protocols of plain hashing, authenticated encryption, verifiable computation, non-interactive proofs, and commitment schemes are secure against a wide class of adversaries, including those dealing with multiple invocations of a sponge in a single application. Our results pave the way of using SAFE with the full taxonomy of hash functions, including SNARK-, lattice-, and x86-friendly hashes.