To Pad or Not to Pad? Padding-Free Arithmetization-Oriented Sponges

Abstract

The sponge is a popular construction for hashing and keyed hashing, and the duplex for authenticated encryption. They are proven to achieve approximately 2^c/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 p^c/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 ≈ 2²⁵⁶, 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.