Paper 2024/911

Generalized Indifferentiable Sponge and its Application to Polygon Miden VM

Tomer Ashur, 3MI Labs, Polygon Research
Amit Singh Bhati, COSIC, KU Leuven
Abstract

Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge construction is one of the prevalent hashing method used in various systems. The Sponge has been shown to be indifferentiable from a random oracle when initialized with a random permutation. In this work, we first introduce $\mathsf{GSponge}$, a generalized form of the Sponge construction offering enhanced flexibility in input chaining, field sizes, and padding types. $\mathsf{GSponge}$ not only captures all existing sponge variants but also unveils new, efficient ones. The generic structure of $\mathsf{GSponge}$ facilitates the discovery of two micro-optimizations for already deployed sponges. Firstly, it allows a new padding rule based on zero-padding and domain-separated inputs, saving one full permutation call in certain cases without increasing the generation time of zero-knowledge proofs. Secondly, it allows to absorb up to $\mathsf{c}/2$ more elements (that can save another permutation call for certain message lengths) without compromising the indifferentiability security. These optimizations enhance hashing time for practical use cases such as Merkle-tree hashing and short message processing. We then propose a new efficient instantiation of $\mathsf{GSponge}$ called $\mathsf{Sponge2}$ capturing these micro-optimizations and provide a formal indifferentiability proof to establish both $\mathsf{Sponge2}$ and $\mathsf{GSponge}$'s security. This proof, simpler than the original for Sponges, offers clarity and ease of understanding for real-world practitioners. Additionally, it is demonstrated that $\mathsf{GSponge}$ can be safely instantiated with permutations defined over large prime fields, a result not previously formally proven.

Note: Added an application section. Updated the related works.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
SpongeGSpongeSponge2Hashing ModeAlgebraicMiden VMIndifferentiabilityRandom OracleGeneric Attacks
Contact author(s)
tomer @ 3milabs tech
amitsingh bhati @ esat kuleuven be
History
2024-07-11: last of 2 revisions
2024-06-07: received
See all versions
Short URL
https://ia.cr/2024/911
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/911,
      author = {Tomer Ashur and Amit Singh Bhati},
      title = {Generalized Indifferentiable Sponge and its Application to Polygon Miden {VM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/911},
      year = {2024},
      url = {https://eprint.iacr.org/2024/911}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.