Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications

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

Paper 2022/403

Horst Meets Fluid-SPN: Griffin for Zero-Knowledge Applications

Lorenzo Grassi, Ruhr University Bochum, Bochum (Germany)

Yonglin Hao, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878 (China)

Christian Rechberger, Graz University of Technology (Austria)

Markus Schofnegger, Horizen Labs (United States)

Roman Walch, Graz University of Technology (Austria), Know-Center GmbH (Austria), TACEO GmbH (Austria)

Qingju Wang, Telecom Paris, Institut Polytechnique de Paris (France)

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 over prime fields rather than binary ones. 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 crucial limitations in the design, which may affect the performance in the target applications. In this paper, we propose the Horst construction, in which the addition in a Feistel scheme (x, y) -> (y + F(x), x) is extended via a multiplication, i.e., (x, y) -> (y * G(x) + F(x), x). By carefully analyzing the performance metrics in SNARK and STARK protocols, we show how to combine an expanding Horst scheme with a Rescue-like SPN scheme 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.

Note: Fixed a typo in the security section for the Gröbner basis approach using intermediate variables.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in CRYPTO 2023
Keywords: Hash Functions Griffin Zero Knowledge Horst Fluid-SPN
Contact author(s): lorenzo grassi @ ruhr-uni-bochum de
haoyonglin @ yeah net
christian rechberger @ tugraz at
markus schofnegger @ gmail com
roman walch @ iaik tugraz at
qingju wang @ telecom-paris fr
History: 2023-12-01: last of 5 revisions; 2022-03-31: received; See all versions
Short URL: https://ia.cr/2022/403
License: 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 = {Horst Meets Fluid-{SPN}: Griffin for Zero-Knowledge Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/403},
      year = {2022},
      url = {https://eprint.iacr.org/2022/403}
}