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

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) \mapsto (y + F(x), x) is extended via a multiplication, i.e., (x, y) \mapsto (y \times 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.

Keywords: Hash Functions – Griffin – Zero-Knowledge – Horst – Fluid-SPN

1. Introduction

Concepts like multi-party computation (MPC), homomorphic encryption (HE), post-quantum signature schemes, and zero-knowledge (ZK) proof systems have recently grown in popularity. Some of these applications favor cryptographic schemes with specific properties, such as a small number of multiplications. Considering \mathbb{F}_p^t for a prime p \geq 3 and t \geq 1, examples include Feistel-MiMC, GMiMC, Poseidon, Rescue, Grendel, Reinforced Concrete, Neptune, and Anemoi, among others.

The performance metrics vary between the different use cases. While the cost in e.g. MPC is well-studied, ZK protocols often have more sophisticated optimization targets. The two major classes of ZK proof systems are zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) and zero-knowledge scalable transparent arguments of knowledge (zk-STARKs), which are also the ones the authors focus on.

Recent hash functions proposed for these protocols differ substantially from each other, however their internal permutations are usually SPN constructions. While this approach may have advantages for arguing security, it can also have various limitations affecting the performance in ZK protocols.

1.1 Hash and Compression Functions in ZK Settings

Cost Metrics in ZK Protocols. In many ZK applications, the prover uses ZK proofs to convince a verifier that they know a preimage x of a given hash or compression output y = \mathcal{H}(x) without revealing anything about x. The efficiency of these protocols depends on the details of \mathcal{H}. In zk-SNARKs, the cost of the proof is proportional to the number of nonlinear operations one has to perform. In zk-STARKs, the cost is related to the degree and the depth of the circuit that must be verified. In both cases, it is not required to recompute \mathcal{H} in order to determine if y = \mathcal{H}(x). Indeed, one can verify any equivalent cheaper representation \mathcal{F}(x,y) = 0 which is satisfied if and only if y = \mathcal{H}(x).

Most previous designs focused only on a subset of cost metrics. For example, MiMC, HadesMiMC, and Poseidon aimed to minimize the number of multiplications, leading to efficiency in SNARKs but disadvantages in other proof systems. In contrast, Rescue has an inner structure tailored for STARKs but suffers in other SNARKs and in plain performance.

SPN Schemes and Power Maps. Competitive hash functions for ZK protocols include Rescue and Poseidon. Both schemes are instantiated via an SPN permutation, whose round function \mathcal{R} : \mathbb{F}_p^t \to \mathbb{F}_p^t is defined as

where c is a round constant, M \in \mathbb{F}_p^{t \times t} is an MDS matrix, and S : \mathbb{F}_p^t \to \mathbb{F}_p^t is an S-box layer defined as

for invertible maps S_i : \mathbb{F}_p \to \mathbb{F}_p. Every round of Rescue consists of two steps, one in which all S_i correspond to x \mapsto x^{1/d} and one in which all S_i correspond to x \mapsto x^d. Poseidon uses two different rounds, one in which S_i(x) = x^d and one in which S_0(x) = x^d and S_{i \neq 0}(x) = x (identity).

1.2 Our Contribution

SPN Schemes in ZK. An SPN scheme usually allows for simple and strong security arguments regarding statistical attacks. However, SPN schemes over \mathbb{F}_p^t have a crucial limitation in the ZK setting. A common way to instantiate the nonlinear layer is to use invertible power maps x \mapsto x^d (hence, \gcd(d, p-1) = 1). Since the square function is not a permutation over \mathbb{F}_p, one must use a function of degree d \geq 3, which affects the performance. The number of multiplications is at least 2t for a t-element state, and 3t for the particular ZK settings considered.

Horst Schemes. Together with an SPN, another popular cryptographic construction is the Feistel one. Given a function F over a generic field \mathbb{F}, a Feistel scheme is defined as the map (x,y) \mapsto (y + F(x), x) over \mathbb{F}_p^2. The authors propose a modified Feistel scheme, called Horst, in which the linear relation between y and F(x) is combined with a nonlinear one: (y, x) \mapsto (x, y \times G(x) + F(x)). To guarantee invertibility, we require that G(x) \neq 0 for each input x.

Griffin. Griffin is a new family of sponge hash and compression functions using the internal permutation Griffin-\pi. The permutation cannot be rewritten as a standard SPN since its nonlinear layer is not divided into independent nonlinear S-boxes. Instead, it is composed of two nonlinear sublayers defined via three different nonlinear functions. Two of them are defined via the invertible power maps x \mapsto x^d and x \mapsto x^{1/d} (inspired by Rescue), and the final one is defined by the proposed Horst strategy, using the map (x,y) \mapsto (x, y \cdot G(x)) for a quadratic function G such that G(z) \neq 0 for each z.

Modes of Operation. The proposed permutation Griffin-\pi can be used both in a sponge mode and in a compression mode. The former is more versatile while the latter can be more efficient in specific settings.

Security Analysis. A security analysis is given in Section 6. From the algebraic perspective, Grobner basis attacks at the round level are the most efficient ones. From the statistical perspective, the authors apply bounds against classical differential and linear attacks. For rebound attacks, an analysis using dedicated MILP tools provides bounds on the minimal number of rounds needed.

Efficiency. Griffin aims to find a beneficial tradeoff between all cost metrics. In R1CS-based SNARKs, Griffin is better suited than any previously proposed design. In zk-STARKs and Plonk, Griffin provides similar performance as the currently best hash functions for STARKs, and the best performance for many configurations in Plonk.

2. Cost Metrics for Zero-Knowledge Proof Systems

This section analyzes the cost metrics for R1CS-based SNARKs and Plonk. The authors start by providing a brief introduction to arithmetization techniques used in various ZK proof systems, focusing on iterative functions.

2.1 Zero-Knowledge Proofs

A ZK proof system is a two-player protocol between a prover and a verifier, allowing the prover to convince the verifier that they know a witness w to a statement x without revealing anything about the witness beyond what can be implied by x. The proof system needs to be complete and sound with a negligible soundness error \epsilon, and it must fulfill the zero-knowledge property.

The two major classes of ZK proof systems are zk-SNARKs and zk-STARKs, where zk-SNARKs require a trusted setup and are not post-quantum secure. Two main use cases relying on hash functions are set membership proofs based on Merkle tree accumulators and verifiable computation based on recursive proofs.

2.2 Arithmetization

To prove a solution of a computational problem, one has to translate the problem into an algebraic representation. This step is known as arithmetization and differs between the various proof systems. Many representations have been proposed, with rank-1 constraint satisfaction systems (R1CS) and Plonk gates being the most widely used in zk-SNARKs, and the algebraic intermediate representation (AIR) being used in zk-STARKs.

This strategy is based on the notion of non-procedural computation, which describes the idea of not only evaluating schemes in the plain direction, but using intermediate relations instead. A scheme is fluid if it admits an equivalent representation which can be proven and/or verified more efficiently.

2.3 Rank-1 Constraint Satisfaction Systems (R1CS)

Many proof systems (e.g., Groth16, Ligero, Aurora, Bulletproofs) require translating the circuit into an R1CS, with Groth16 being the fastest proof system with the smallest proofs to date. An R1CS is a set of \eta equations (constraints) on the variables a_0, \ldots, a_m \in \mathbb{F}_q (with a_0 = 1) such that

In R1CS constraints, every statement needs to be translated into multiplications of linear combinations of the witness variables. Linear operations can be embedded into subsequent constraints and do not require additional constraints.

Cost Metric. The number of R1CS constraints, i.e., the minimum number of nonlinear operations of linear combinations of witness variables required to fully represent any equivalent relation between the input and its output.

2.4 Plonk Arithmetization

Plonk is a zk-SNARK which does not use R1CS constraints. Its arithmetization is based on Plonk gates with constraints of the form

Using this equation, one can either describe a 2-fan-in addition (setting q_{M,i} = 0) or a 2-fan-in multiplication (setting q_{L,i} = q_{R,i} = 0). Contrary to R1CS constraints, additions cannot be embedded into subsequent multiplication constraints anymore and require separate Plonk gates.

Cost Metric. The number of Plonk gates, i.e., the minimum number of 2-fan-in additions and multiplications of witness variables required to fully represent any equivalent relation between the input and its output.

3. The Road to Griffin

3.1 Related Work: SPN Schemes for ZK Applications

Poseidon and Rescue. Two well-known examples of SPN schemes for ZK settings. Their round function is defined via an MDS matrix and S-box layer where all S-boxes operate over \mathbb{F}_p independently. An important advantage is that techniques such as the wide trail design strategy have been developed to study their security. At the same time, a strong limitation on the choice of the S-box arises: the designer is restricted to S-box functions of degree d \geq 3. Quadratic nonlinear components cannot be used, leading to performance limitations.

Neptune and Anemoi. One way to gain more flexibility regarding the degree is by considering S-boxes over \mathbb{F}_p^n for n \geq 2. Neptune is inspired by Poseidon but replaces the power maps in external rounds with quadratic Lai-Massey functions. Anemoi uses S-boxes based on a particular Feistel scheme called Flystel.

3.2 Non-SPN Schemes: From Feistel to Horst

Given functions \tilde{F}_0, \tilde{F}_1, \ldots, \tilde{F}_{t-2} over \mathbb{F}_p, the authors consider generalized Feistel schemes: Type-I, Type-II, and Type-III. An example of a ZK-friendly generalized Feistel scheme is GMiMC (broken in [BCD+20]). Practical tests suggest these schemes may not provide the expected security level against some algebraic attacks. To solve this, the authors propose the following.

Initial Security Considerations. It is always possible to set up a distinguisher for one (trivial) and two rounds of the Horst scheme. The problems of setting up distinguishers for more than 2 rounds of Horst and for more than 6 rounds of Feistel or \text{Horst}^\times are open for future research.

3.3 Constructing Nonzero Functions G

Let d \geq 3 be the smallest integer such that x \mapsto x^d is invertible over \mathbb{F}_q. Let \alpha \in \mathbb{F}_q \setminus \{0\}. A concrete example of G over \mathbb{F}_q is

Result for Prime Fields. In the case of a prime field \mathbb{F}_p for p \geq 3, one can exploit the fact that the quadratic map x \mapsto x^2 is not invertible over \mathbb{F}_p. Let \alpha, \beta \in \mathbb{F}_p such that \alpha^2 - 4\beta is a quadratic nonresidue modulo p. Then G(x) = x^2 + \alpha x + \beta satisfies the required property.

3.4 Combining Horst with a Rescue-like SPN: The Birth of Griffin

Nonlinear Layer. By combining a Fluid-SPN scheme and Horst in a single nonlinear layer, the authors obtain S : \mathbb{F}_p^t \to \mathbb{F}_p^t defined as S(\cdot) = S'' \circ S'(\cdot), where

where \alpha_i^2 - 4\beta_i is a quadratic nonresidue and z_i is a linear combination of the inputs and outputs.

Number of Multiplications. The number of multiplications per round for the verification process is

Hence, for large t, the cost of this design is almost independent of the value of d.

Linear Layer. For t \in \{3, 4\}, MDS matrices are used. For t > 4, a more efficient linear layer is proposed, inspired by the linear layer of AES. The matrix can be decomposed as the multiplication of two matrices that both provide full diffusion, achieving this property in each state word after a single round. The linear layer only requires around 5t \in \mathcal{O}(t) operations.

4. Modes of Operation

The authors build a hash function with the sponge construction and a compression function with the feed-forward operation and truncation. Both use the Griffin-\pi permutation.

4.1 Sponge Hash Functions

The sponge construction builds upon an internal permutation and can be used to achieve various goals such as encryption, authentication, and hashing. The state size is split into t = r + c, where r and c denote the number of elements in the rate and capacity part, respectively.

Security. If the inner permutation resembles a random one, the sponge construction is indifferentiable from a random oracle up to around p^{c/2} queries. To provide \kappa bits of security, c \geq \lceil 2\kappa \cdot \log_p(2) \rceil.

4.2 Compression Functions

Let p \geq 2 be a prime and let 1 \leq n < t. A cryptographic compression function \mathcal{C} : \mathbb{F}_p^t \to \mathbb{F}_p^n takes t-element inputs and compresses them to n-element outputs. One way to set up a compression function via a permutation is to combine the truncation function with the feed-forward operation:

where \mathcal{P} is a permutation over \mathbb{F}_p^t and \text{Tr}_n yields the first n elements.

5. Griffin and Griffin-\pi

Griffin-Sponge and Griffin-Compression are respectively a sponge hash function and a compression function over \mathbb{F}_p^t instantiated with the permutation Griffin-\pi, where p > 2^{63} for a prime p and t \in \{3, 4t'\} for a positive integer t' \in \{1, 2, \ldots, 6\}, i.e., t is either 3 or a multiple of 4. The security level is \kappa bits, where 80 \leq \kappa \leq \min\{256, \lfloor \log_2(p) \cdot t/3 \rfloor\}. It is assumed that there exists d \in \{3, 5, 7, 11\} such that \gcd(d, p - 1) = 1.

5.1 Specification of Griffin-\pi

The Griffin-\pi permutation \mathcal{G}^\pi : \mathbb{F}_p^t \to \mathbb{F}_p^t is defined by

where M \in \mathbb{F}_p^{t \times t} is an invertible matrix and \mathcal{F}_i(\cdot) = c^{(i)} + M \times S(\cdot) for a round constant c^{(i)} \in \mathbb{F}_p^t and nonlinear layer S.

The Nonlinear Layer S. Let d \in \{3, 5, 7, 11\} be the smallest integer such that \gcd(d, p-1) = 1. Let (\alpha_i, \beta_i) \in \mathbb{F}_p^2 \setminus \{(0,0)\} be pairwise distinct such that \alpha_i^2 - 4\beta_i is a quadratic nonresidue modulo p for 2 \leq i \leq t-1. The nonlinear layer S(x_0, \ldots, x_{t-1}) = y_0 \| \cdots \| y_{t-1} is then defined by

where y_0 = x_0^d, y_1 = x_1^{1/d}, and L_i(z_0, z_1, z_2) = \gamma_i \cdot z_0 + z_1 + z_2 for arbitrary pairwise distinct \gamma_i \in \mathbb{F}_p \setminus \{0\}.

The Linear Layer M. For t \in \{3, 4\}, the matrices must be MDS:

For t = 4t' \geq 8, M is defined as

where M' = \text{diag}(M_4, M_4, \dots, M_4) and M'' = \text{circ}(2 \cdot I, I, \dots, I).

Choosing the Constants. A pseudo-random number generator based on SHAKE is used to choose the round constants and the constants (\alpha_2, \beta_2) that define the nonlinear layer. The other constants are defined as \alpha_i = (i-1) \cdot \alpha_2 and \beta_i = (i-1)^2 \cdot \beta_2.

5.2 Number of Rounds of Griffin-\pi

For \kappa-bit security, the round number R including a margin of 20% must satisfy

6. Security of Griffin and Griffin-\pi

The authors aim for Griffin-\pi instances that prevent attacks on the hash and compression function. Distinguishers on Griffin-\pi that cannot be exploited for an attack on the entire construction (e.g., zero sum partitions) are not taken into account.

6.1 Statistical Attacks on Griffin-\pi

The best statistical attacks against Griffin-\pi include the differential and the rebound attack. The security analysis is supported by dedicated automatic MILP tools.

Differential Cryptanalysis. Given pairs of inputs with fixed input differences, differential cryptanalysis considers the probability distribution of the corresponding output differences. The differential probability for \Delta_O given \Delta_I is

The number of rounds sufficient to achieve a probability smaller than 2^{-2.5\kappa} over the entire permutation is

Rebound Attacks. The goal is to find two (input, output) pairs such that the two inputs and corresponding outputs satisfy certain truncated differences. The authors claim that 6 rounds are sufficient against this attack, supported by a dedicated MILP tool that shows no feasible rebound attack can be mounted for 3 or more Griffin-\pi rounds.

6.2 Algebraic Attacks

Algebraic attacks exploit weak algebraic properties of the design. The authors analyze interpolation attacks and Grobner basis attacks as the most efficient ones against Griffin.

Interpolation Attacks. The cost of the attack grows with the number of different monomials in the interpolation polynomial. In this case, 3 rounds are sufficient to reach the maximum degree, and 2 \cdot 3 = 6 rounds are conjectured sufficient to prevent interpolation attacks and their variants.

Grobner Basis Attacks. Two strategies are considered. The first introduces intermediate variables for all state words per round, yielding a complexity requiring

The second strategy introduces only a single intermediate variable per round, yielding

6.3 Feistel versus Horst: Security of Griffin Instantiated with Feistel

The authors consider the security of Griffin instantiated with a classical Feistel scheme. In the first Grobner basis strategy with intermediate variables for the whole state, the practical degree of regularity was constant regardless of the number of rounds for R \geq 2. The designers were able to compute Grobner bases in practice for the round numbers proposed for Griffin (with Horst).

For the second strategy, the maximum degree in each round is reduced due to the missing multiplication, and faster Grobner basis computations were observed for the Feistel version (about a factor of 8 between the two versions). This suggests that using the multiplication instead of the addition is better when aiming for security and efficiency.

7. Performance Evaluation

The authors evaluate the performance of Griffin and compare it to Poseidon, Rescue-Prime, \text{GMiMC}_{\text{erf}}, Grendel, Neptune, and Anemoi. All hash functions are instantiated to provide 128 bits of security. Benchmarks were obtained on Linux using an Intel Xeon E5-2699 v4 CPU (2.2 GHz) using stable Rust version 1.59.

7.1 Plain Performance

The plain performance is compared using the scalar fields of the commonly used BLS12 and BN254 elliptic curves (both using d = 5). For t \leq 16, the fastest permutation is \text{GMiMC}_{\text{erf}}. However, as shown later, it has the worst performance in SNARKs and STARKs. Rescue-Prime and Grendel have the worst plain performance due to having t high-degree x^{1/d} or Legendre symbol evaluations per round.

Griffin also uses x^{1/d}, but only once per round, so it scales significantly better with larger t. For small t, Griffin is slower than Poseidon and Neptune, but the differences get smaller for larger t, until Griffin is faster if t \geq 16.

7.2 R1CS-Based SNARKs with Griffin

Describing Griffin as an R1CS system is straightforward. The total number of R1CS constraints for the whole Griffin-\pi permutation is

i.e., 2 \cdot R \cdot t R1CS constraints if d = 3 and R \cdot (2t + 2) if d = 5.

Griffin requires the smallest number of R1CS constraints to prove the knowledge of a preimage of a hash for several state sizes. Even for arities where Griffin requires a larger state size (since it is defined for t \in \{3, 4t'\}), the approach results in significantly fewer R1CS constraints and smaller proving times compared to other hash functions. Concretely, using Griffin results in nearly half of the required constraints compared to Poseidon and Rescue, and two thirds compared to Neptune.

7.3 Plonk Performance of Griffin

Describing Griffin with Plonk gates: each affine layer usually requires t \cdot (t-1) addition gates, but due to the specific structure of the linear layers, the number is reduced significantly. Griffin requires

Plonk gates, i.e., (R+1) \cdot \#\text{mat} + R \cdot (4t - 5) gates if d = 3 and (R+1) \cdot \#\text{mat} + R \cdot (4t - 3) gates if d = 5.

Compared to Poseidon and Rescue, Griffin always requires the smallest number of Plonk gates due to having a small number of multiplications and rounds. Only Anemoi requires a smaller number of gates for d = 3 and small state sizes, but Griffin's linear layer becomes more efficient with larger state sizes (around t \geq 12).

Acknowledgments

The authors thank all reviewers for their suggestions. Lorenzo Grassi is supported by the German Research Foundation (DFG) within the framework of the Excellence Strategy of the Federal Government and the States – EXC 2092 CaSa – 39078197. Roman Walch is supported by the "DDAI" COMET Module. Yonglin Hao is supported by National Natural Science Foundation of China (Grant No. 62002024). Qingju Wang was funded, in part, by Huawei Technologies Co., Ltd.

Appendix A. STARKs with Griffin

A.1 Algebraic Intermediate Representation (AIR). zk-STARKs require translating the computational problem into an algebraic intermediate representation (AIR). The AIR consists of a sequence of machine states (the algebraic execution trace (AET)) and multivariate polynomials describing the transition between states. The efficiency depends on w (register width), T (sequence length), and d_{\max} (maximum polynomial degree).

Cost Metric. Approximated as \mathcal{O}(d_{\max} \cdot T), i.e., the number of rounds times the degree of the round function representation.

A.2 Relations Between SNARK and STARK Cost Metrics. While for HE it is important to minimize the multiplicative depth, for MPC it is crucial to minimize the total number of multiplications. In ZK proof systems, one must find an efficient equivalent representation minimizing the degree and/or the number of multiplications.

A.3 STARK Performance of Griffin. For the AIR representation, the machine size w equals the state size t, and the maximum degree d_{\max} equals d. The AIR of Griffin is a straightforward translation and is easier to use in practice compared to Poseidon (which requires heavy precomputations) or Rescue (which needs a meet-in-the-middle approach).

Appendix B. Security of Horst Schemes

The authors propose distinguishers for 3, 4, and 5 rounds of \text{Horst}^\times, adapting analogous attacks on Feistel schemes by Patarin. Each round is defined as

3 Rounds. Consider inputs of the form (\hat{y}, x_i) and corresponding outputs (z_i, w_i). The probability to have a collision of the form (z_i - \beta_1) \cdot x_j = (z_j - \beta_1) \cdot x_i is around 2/q for \text{Horst}^\times versus 1/q for a PRP.

4 Rounds. The 3-round distinguisher is easily extended to 4 rounds by starting with inputs of the form (y_i, \hat{y}) and reusing the previous distinguisher.

Appendix C. Proofs – Differential Cryptanalysis

C.1 Maximum Differential Probability of S. The proofs of Lemmas 2 and 3 are provided. For x \mapsto x^d, the maximal number of solutions of (x + \delta_I)^d - x^d = \delta_O is d - 1, yielding \text{DP}_{\max} = (d-1)/p.

C.2 Branch Number of M.

Appendix D. Dedicated MILP Tool for Rebound Attacks on Griffin-\pi

A dedicated mixed integer linear programming (MILP) tool is constructed to verify the results of rebound attacks. The core of the tool captures the truncated differential propagation of Griffin-\pi.

MILP Models for Linear Combinations. For a linear step z = x + y, the truncated differential propagation rule is captured by MILP constraints.

Word Conditions. In rebound attacks, complexities are decided by the number of word conditions imposed by both nonlinear and linear operations. Word conditions in the inbound phase can be satisfied for free via message modification, while those in the outbound phase have probability p^{-1}.

The results show that it is not possible to mount a rebound attack on more than 3 rounds of Griffin-\pi. Equivalently, 4 rounds are sufficient for providing security against this attack.

Appendix E. Algebraic Attacks – Details

E.1 Density of Griffin-\pi. Since the only high-degree nonlinear function is x \mapsto x^{1/d}, the density is analyzed. In practice, x \mapsto x^{1/d} provides almost full density over \mathbb{F}_p. The polynomial representation of the construction is claimed to be dense after 3 rounds.

E.2 Practical Results for Grobner Bases. Concrete data points for practical computations with intermediate variables show observed degrees of regularity \geq D_{\text{est}}^{(1)} = dR. For partial intermediate variables, the degree of regularity is estimated as D_{\text{est}}^{(2)} = d^R.

E.3 Additional Strategies. Two further strategies are described: the full-round equation system (requiring \lceil \kappa / \log_2(p) \rceil + 1 rounds) and adding an intermediate variable for the degree-2 function L. Both are less efficient than the main strategies.

Appendix F. Security Analysis – Other Attacks

F.1 Other Statistical Attacks.

Linear Attack: Due to the same analysis proposed for differential attacks, linear attacks pose no threat to Griffin.

Impossible Differential and Zero-correlation Attacks: The difference of one word can affect the whole state by one round function call, so these attacks can hardly be mounted on 3 or more rounds.

Boomerang Attack: Differential trails with high probability are unlikely for more than 6 rounds, so the differential/rebound round numbers are sufficient.

Integral/Square, Multiple-of-n, and Mixture Differential Cryptanalysis: These become quickly infeasible since the nonlinear layer S is not aligned and the matrix M provides full diffusion after a single round.

F.2 Higher-Order Differentials and Zero-Sum Partitions.

The authors explicitly state that they do not make claims about the security of Griffin against zero-sum partitions, motivated by the gap present in the literature between the number of rounds covered by zero-sum partitions and the number of rounds that can be broken via preimage or collision attacks.

References

1. M. R. Albrecht, C. Cid, L. Grassi, D. Khovratovich, R. Luftenegger, C. Rechberger, and M. Schofnegger. "Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC". ASIACRYPT 2019.
2. M. R. Albrecht, L. Grassi, L. Perrin, S. Ramacher, C. Rechberger, D. Rotaru, A. Roy, and M. Schofnegger. "Feistel Structures for MPC, and More". ESORICS 2019. [page on this site]
3. M. R. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen. "MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity". ASIACRYPT 2016.
4. A. Aly, T. Ashur, E. Ben-Sasson, S. Dhooghe, and A. Szepieniec. "Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols". IACR Trans. Symmetric Cryptol. 2020.3.
5. S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam. "Ligero: Lightweight Sublinear Arguments Without a Trusted Setup". CCS 2017.
6. M. Bardet, J.-C. Faugere, B. Salvy, and B.-Y. Yang. "Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems". Proc. of MEGA 2005.
7. E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. "Scalable, transparent, and post-quantum secure computational integrity". ePrint 2018/46.
8. E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward. "Aurora: Transparent Succinct Arguments for R1CS". EUROCRYPT 2019.
9. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. "Sponge functions". Ecrypt Hash Workshop 2007.
10. G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. "On the Indifferentiability of the Sponge Construction". EUROCRYPT 2008.
11. T. Beyne, A. Canteaut, I. Dinur, et al. "Out of Oddity - New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems". CRYPTO 2020. [page on this site]
12. E. Biham and A. Shamir. "Differential Cryptanalysis of DES-like Cryptosystems". CRYPTO 1990.
13. A. Biryukov, L. Perrin, and A. Udovenko. "Reverse- Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1". EUROCRYPT 2016.
14. J. Black, P. Rogaway, and T. Shrimpton. "Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV". CRYPTO 2002.
15. C. Boura, A. Canteaut, and C. D. Canniere. "Higher-Order Differential Properties of Keccak and Luffa". FSE 2011.
16. C. Bouvier, P. Briaud, P. Chaidos, L. Perrin, R. Salen, V. Velichkov, and D. Willems. "Anemoi Permutations and Jive Compression Mode". ePrint 2022/840. [page on this site]
17. B. Buchberger. "Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal". PhD thesis, Univ. Innsbruck, 1965.
18. B. Bunz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. "Bulletproofs: Short Proofs for Confidential Transactions and More". IEEE S&P 2018.
19. J.-S. Coron, J. Patarin, and Y. Seurin. "The Random Oracle Model and the Ideal Cipher Model Are Equivalent". CRYPTO 2008.
20. D. A. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Springer, 1997.
21. R. A. de la Cruz Jimenez. "On some methods for constructing almost optimal S-Boxes and their resilience against side-channel attacks". ePrint 2018/618.
22. J. Daemen and V. Rijmen. "The Wide Trail Design Strategy". Cryptography and Coding 2001.
23. Y. Dai and J. P. Steinberger. "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016.
24. C. Dobraunig, L. Grassi, A. Guinet, and D. Kuijsters. "Ciminion: Symmetric Encryption Based on Toffoli-Gates over Large Finite Fields". EUROCRYPT 2021.
25. V. Dolmatov and A. Degtyarev. "GOST R 34.11-2012: Hash Function". RFC 6986, 2013.
26. S. Duval and G. Leurent. "MDS Matrices with Lightweight Circuits". IACR Trans. Symmetric Cryptol. 2018.2.
27. Federal Agency on Technical Regulation and Metrology. GOST R 34.12-2015: Block Cipher. 2015.
28. A. Gabizon and Z. J. Williamson. "plookup: A simplified polynomial protocol for lookup tables". ePrint 2020/315. [page on this site]
29. A. Gabizon, Z. J. Williamson, and O. Ciobotaru. "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge". ePrint 2019/953. [page on this site]
30. L. Grassi. "On Generalizations of the Lai-Massey Scheme". ePrint 2022/1245.
31. L. Grassi, D. Khovratovich, R. Luftenegger, C. Rechberger, M. Schofnegger, and R. Walch. "Reinforced Concrete: Fast Hash Function for Zero Knowledge Proofs". ePrint 2021/1038. [page on this site]
32. L. Grassi, D. Khovratovich, C. Rechberger, A. Roy, and M. Schofnegger. "Poseidon: A New Hash Function for Zero-Knowledge Proof Systems". USENIX Security 2021. [page on this site]
33. L. Grassi, D. Khovratovich, S. Ronjom, and M. Schofnegger. "The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes". IACR Trans. Symmetric Cryptol. 2022.1.
34. L. Grassi, R. Luftenegger, C. Rechberger, D. Rotaru, and M. Schofnegger. "On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy". EUROCRYPT 2020. [page on this site]
35. L. Grassi, S. Onofri, M. Pedicini, and L. Sozzi. "Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes". IACR Trans. Symmetric Cryptol. 2022.3.
36. L. Grassi, C. Rechberger, D. Rotaru, P. Scholl, and N. P. Smart. "MPC-Friendly Symmetric Key Primitives". CCS 2016.
37. J. Groth. "On the Size of Pairing-Based Non-interactive Arguments". EUROCRYPT 2016.
38. V. T. Hoang and P. Rogaway. "On Generalized Feistel Networks". CRYPTO 2010.
39. H. B. Hougaard. "3-round Feistel is Not Superpseudorandom Over Any Group". ePrint 2021/675.
40. T. Jakobsen and L. R. Knudsen. "The Interpolation Attack on Block Ciphers". FSE 1997.
41. A. Klimov and A. Shamir. "Cryptographic Applications of T-Functions". SAC 2003.
42. S. Kolbl, M. M. Lauridsen, F. Mendel, and C. Rechberger. "Haraka v2". IACR Trans. Symmetric Cryptol. 2016.2.
43. X. Lai and J. L. Massey. "A Proposal for a New Block Encryption Standard". EUROCRYPT 1990.
44. M. Lamberger, F. Mendel, C. Rechberger, V. Rijmen, and M. Schlaffer. "Rebound Distinguishers: Results on the Full Whirlpool Compression Function". ASIACRYPT 2009.
45. M. Luby and C. Rackoff. "How to Construct Pseudorandom Permutations from Pseudorandom Functions". SIAM J. Comput. 17.2 (1988).
46. M. Matsui. "Linear Cryptanalysis Method for DES Cipher". EUROCRYPT 1993.
47. K. Matusiewicz, M. Naya-Plasencia, I. Nikolic, Y. Sasaki, and M. Schlaffer. "Rebound Attack on the Full Lane Compression Function". ASIACRYPT 2009.
48. U. M. Maurer and K. Pietrzak. "The Security of Many-Round Luby-Rackoff Pseudo-Random Permutations". EUROCRYPT 2003.
49. F. Mendel, C. Rechberger, M. Schlaffer, and S. S. Thomsen. "The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl". FSE 2009.
50. R. Mollin and S. C. "On Permutation Polynomials Over Finite Fields". Int. J. Math. Math. Sci. 10 (1987).
51. NIST. "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions". FIPS 202, 2015.
52. K. Nyberg. "Generalized Feistel Networks". ASIACRYPT 1996.
53. J. Patarin. "About Feistel Schemes with Six (or More) Rounds". FSE 1998.
54. J. Patarin. "Generic Attacks on Feistel Schemes". ASIACRYPT 2001.
55. S. Patel, Z. Ramzan, and G. S. Sundaram. "Luby-Rackoff Ciphers: Why XOR Is Not So Exclusive". SAC 2002.
56. Polygon. "Introducing Plonky2". 2022.
57. B. Preneel, R. Govaerts, and J. Vandewalle. "Hash Functions Based on Block Ciphers: A Synthetic Approach". CRYPTO 1993.
58. A. Szepieniec. "On the Use of the Legendre Symbol in Symmetric Cipher Design". ePrint 2021/984.
59. A. Szepieniec, T. Ashur, and S. Dhooghe. "Rescue-Prime: a Standard Specification (SoK)". ePrint 2020/1143. [page on this site]
60. S. Vaudenay. "Decorrelation: A Theory for Block Cipher Security". J. Cryptol. 16.4 (2003).
61. Zcash. "ZCash protocol specification". 2021.
62. Y. Zheng, T. Matsumoto, and H. Imai. "On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses". CRYPTO 1989.