Paper 2022/403

A New Feistel Approach Meets Fluid-SPN: Griffin for Zero-Knowledge Applications

Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, and Qingju Wang

Abstract

Zero-knowledge (ZK) applications form a large group of use cases in modern cryptography, and recently gained in popularity due to novel proof systems. For many of these applications, cryptographic hash functions are used as the main building blocks, and they often dominate the overall performance and cost of these approaches. Therefore, in the last years several new hash functions were built in order to reduce the cost in these scenarios, including Poseidon and Rescue among others. These hash functions often look very different from more classical designs such as AES or SHA-2. For example, they work natively with integer objects rather than bits. At the same time, for example Poseidon and Rescue share some common features, such as being SPN schemes and instantiating the nonlinear layer with invertible power maps. While this allows the designers to provide simple and strong arguments for establishing their security, it also introduces some crucial limitations in the design, which affects the performance in the target applications. To overcome these limitations, we propose the Horst mode of operation, in which the addition in a Feistel scheme $(x,y) \mapsto (y+F(x), x)$ is replaced by a multiplication, i.e., $(x,y) \mapsto (y \times G(x), x)$. By carefully analyzing the relevant performance metrics in SNARK and STARK protocols, we show how to combine an expanding Horst scheme and the strong points of existing schemes in order to provide security and better efficiency in the target applications. We provide an extensive security analysis for our new design Griffin and a comparison with all current competitors.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Sponge Hash FunctionGriffinZero-Knowledge Proof SystemsHorstFluid-SPN
Contact author(s)
lgrassi @ science ru nl
haoyonglin @ yeah net
christian rechberger @ tugraz at
markus schofnegger @ tugraz at
roman walch @ iaik tugraz at
qingju wang @ uni lu
History
2022-03-31: received
Short URL
https://ia.cr/2022/403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/403,
      author = {Lorenzo Grassi and Yonglin Hao and Christian Rechberger and Markus Schofnegger and Roman Walch and Qingju Wang},
      title = {A New Feistel Approach Meets Fluid-SPN: Griffin for Zero-Knowledge Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/403},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/403}},
      url = {https://eprint.iacr.org/2022/403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.