<p>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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation>, a generalized form of the Sponge construction offering enhanced flexibility in input chaining, field sizes, and padding types. <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation> not only captures all existing sponge variants but also unveils new, efficient ones. The generic structure of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\({\textsf{c}}/2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">c</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation> called <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\textsf{Sponge2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">Sponge</mi> <mn mathvariant="sans-serif">2</mn> </mrow> </math></EquationSource> </InlineEquation> capturing these micro-optimizations and provide a formal indifferentiability proof to establish both <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\textsf{Sponge2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">Sponge</mi> <mn mathvariant="sans-serif">2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation>’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 <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\textsf{GSponge}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">GSponge</mi> </math></EquationSource> </InlineEquation> can be safely instantiated with permutations defined over large prime fields, a result not previously formally proven.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Generalized indifferentiable sponge and its application to Polygon Miden VM

  • Tomer Ashur,
  • Amit Singh Bhati

摘要

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 \(\textsf{GSponge}\) GSponge , a generalized form of the Sponge construction offering enhanced flexibility in input chaining, field sizes, and padding types. \(\textsf{GSponge}\) GSponge not only captures all existing sponge variants but also unveils new, efficient ones. The generic structure of \(\textsf{GSponge}\) 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 \({\textsf{c}}/2\) 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 \(\textsf{GSponge}\) GSponge called \(\textsf{Sponge2}\) Sponge 2 capturing these micro-optimizations and provide a formal indifferentiability proof to establish both \(\textsf{Sponge2}\) Sponge 2 and \(\textsf{GSponge}\) 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 \(\textsf{GSponge}\) GSponge can be safely instantiated with permutations defined over large prime fields, a result not previously formally proven.