Reinforced Concrete: A Fast Hash Function for Verifiable Computation

Abstract

We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.

The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

Keywords: Hash functions, verifiable computation, zksnarks, finite fields

1. Introduction

The recent years have been marked as a thrive of distributed verifiable computation, where the outcome of some algorithm \mathcal{A} is accompanied with a succinct proof of correctness, widely known as a SNARK. Performance of those protocols, however, remains a major bottleneck for applications. The reasons are manyfold, but one crucial point is that SNARKs are constructed for statements formulated over prime fields whereas regular computer programs are written for and executed over bitstrings. The necessary translation of code into finite field arithmetic carries a significant overhead.

In this paper we remove one of such bottlenecks by offering a hash function that is fast both for SNARKs and native computation. There already exist functions that excel in either of those areas, but not in both. The motivation for such a swiss-army tool is the following. To scale, parallelize, and aggregate proofs we employ what is called a recursive proof protocol, where a party can prove their share of computation together with a verification of proof coming from the predecessor. This also enables wrapping multiple proofs into a single succinct check.

Summary of use cases. The new hash function addresses, among others, the following use cases:

• Fast and efficient set membership proofs based on Merkle tree accumulators. Immensely popular in cryptocurrency protocols, this case requires a hash function for the tree. Its ZK circuit should minimize the proof creation time.
• Verifiable computation based on recursive proofs. Here the entire computation is a chain of functions F_1, F_2, \dots, F_k applied consecutively to some state. Here we minimize both native computation time and the prover time.

Summary of requirements. (1) Minimal prover time — for many ZK proof systems it is a (super)linear function of the gate count, where each gate is usually a basic field arithmetic operation. (2) Native performance — a hash function should run as fast as possible on typical hardware. (3) Security — it is desirable to base security on a more traditional rather than algebraic security analysis.

Our design: Reinforced Concrete. We present a new sponge hash function Reinforced Concrete (RC) over \mathbb{F}_p exploiting all the advantages of lookup-equipped proof systems and suitable for both membership proofs and verifiable computation use cases. The permutation that instantiates RC is composed of two types of components: (1) outer ones for preventing statistical attacks; (2) an inner one for preventing algebraic attacks. The inner part strengthens the whole construction like steel bars strengthen concrete, hence the name.

For the inner component, instead of using simple power maps as in Poseidon and Rescue, we use a single building block with a complex algebraic structure, which we call Bars. A Bars layer can be seen as a non-linear layer composed of independent high-degree and dense S-boxes. The Bars function combines a layer of S-boxes (such as in AES) with a field element decomposition in just a handful of small operations.

Even if it prevents algebraic attacks, it can be broken by more traditional statistical attacks such as rebound attacks. The external rounds are instantiated with other layers which are known to protect against statistical attacks, including affine layers called Concrete that provides full diffusion and a low-degree non-linear layer called Bricks.

Comparison to other designs. When compared to hash functions tailored to the same use cases, RC is on par in the gate metric and much faster in native performance. Over generic prime fields (such as the scalar fields of BLS12-381 or BN254) RC is faster by a factor of 5 compared to Poseidon and by a factor of 140 compared to Rescue. Using specially crafted fields increases these factors to 16 and 357 respectively. RC is only 5x slower than Blake2, the fastest traditional hash algorithm benchmarked, but requires 7 times fewer gates when encoded into a circuit.

Supported proof systems. A number of ZK proof system protocols support lookup tables, including Arya, Plookup, Halo2, and Cairo. As lookup gates also speed up traditional hash functions like SHA-2, the authors expect such protocols to become widespread.

Restrictions and future work. A proof system should support lookup gates, as otherwise the RC circuit would be quite large (around 5000 constraints). Also the Bars component is specific for each field, implying some work when carrying it to a new curve. Devising a more generic Bars is the subject of future work.

2. RC in a Nutshell

The RC hash function operates in the sponge framework. The sponge converts a fixed length bijective function (called RC permutation) to a variable-length hash function, which is collision- and preimage-resistant as long as the underlying permutation does not exhibit any “non-random” properties up to the bound defined by the security level 2^\lambda (in our case \lambda is universally set to 128).

The RC permutation can be considered as a modified 7-round SP network, where input, output and intermediate state elements are from \mathbb{F}_p^3 for a prime number p. More formally,

In the following, we refer to Concrete ∘ Bricks as “round”.

We define RC for different p, with two (-BN and -BLS) being scalar fields of the curves BN254 and BLS12-381, and another one (-ST) crafted for a specially chosen field in order to deliver the highest performance.

Design. The RC design is a modification of a traditional word-oriented SP-network (SPN) for constructing cryptographic permutations. It differs from a traditional SPN in two aspects: (1) the middle layer of the SP network is replaced by a special component called Bars, which does not admit a low-degree polynomial description but can be implemented as a circuit with reasonable costs in ZK; (2) instead of applying independent non-linear transformations on single words, RC uses low-degree non-linear layers called Bricks that additionally mix different words. The third component, Concrete, is an analog of the traditional affine layer over \mathbb{F}.

3. Security Requirements and Claims

The high-level security claims, which determine the parameter selection for RC, are the following:

• For the sponge hash function with RC, collision and preimage resistance up to 2^{128} field operations for 256-bit fields. Ability to instantiate a random oracle in protocols up to 2^{128} calls.
• For authenticated encryption using RC, confidentiality and integrity up to 2^{128} encrypted messages for 256-bit fields.
• When using RC in other future schemes, a 1-element CICO security up to 2^{128} field operations. More concretely, it should be infeasible to find such x_1, x_2, y_1, y_2 such that

4. Specification and Rationale

The story behind the design of RC, which has determined its inner components, is as follows: (1) We wanted to design a hash function which has a high degree as a polynomial and would not allow a treatment with algebraic methods such as Gröbner basis. (2) We sought to have table lookup functionality applied to finite field elements rather than bitstrings. For this we had to design an efficient way to decompose a field element into smaller chunks, apply some nonlinear transformation, and then wrap it back (composition). This was to become Bars. (3) In order to protect against non-algebraic attacks, we had to wrap Bars with additional confusion and diffusion layers.

4.1 The Bricks Function

The invertibility of Bricks relies on the fact that z^2 + \alpha z + \beta \neq 0 for each z \in \mathbb{F}_p. See Appendix A.1 for a proof.

4.2 The Concrete Function

Note that M is invertible and MDS for each p \ge 3. The elements c_1^{(j)}, c_2^{(j)}, c_3^{(j)} are certain pseudo-random constants, generated using e.g. Shake-128 with rejection sampling.

4.3 The Bars Function

4.3.1 Decomposition and Composition. We choose the standard representation \mathbb{F}_p = \{0, 1, \dots, p-1\}, thus identifying an element x \in \mathbb{F}_p with an integer 0 \le x \le p-1. The decomposition maps \mathbb{F}_p \to \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_n} as

with 0 \le x_i < s_i and where the s_i are chosen such that \prod_{i=1}^{n} s_i > p. The digits x_i \in \mathbb{Z}_{s_i} are determined similarly to ordinary base-b expansion:

For convenience we define b_i := \prod_{j > i} s_j = s_{i+1} s_{i+2} \dots s_n, with b_n := 1. The composition \mathsf{Comp} : \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_n} \to \mathbb{F}_p is

4.3.2 SBox. Let (v_1, v_2, \ldots, v_n) = \mathsf{Decomp}(p-1) and let p' \le \min_{1 \le i \le n} v_i. Then x_i is converted as follows:

where f denotes a permutation of \mathbb{Z}_{p'}. The f function is derived from the MiMC cipher (which implicitly requires p' being prime).

4.4 Sponge Framework Parameters

The bijective transformation RC is used in the sponge framework similarly to Poseidon and Rescue. The parameters are:

• Rate is two \mathbb{F}_p elements, capacity is one \mathbb{F}_p element.
• Claimed preimage and collision security level of 128 bits.
• The padding rule is simply to add the 0 element to any input of odd length. The very first capacity value is initialized by the length-depending constant.

5. Security Analysis

This section summarizes the authors’ own analysis of RC security. They customarily reduce the security of the RC hash to its resistance against known cryptanalytic attacks, focusing on two classes:

• Statistical attacks (including differential, linear, rebound, truncated, impossible, MiTM, boomerang) cannot be mounted on RC even with the middle component replaced with a single Bricks layer up to 2^{128} field operations.
• The middle component Bricks-Concrete-Bars-Concrete-Bricks resists invariant subspace and algebraic (e.g., Gröbner basis) attacks up to 2^{128} field operations.

The short summary: differential and linear attacks do not work as long as the Bricks layer is involved; rebound attacks cannot be mounted for 5 or more rounds (at least 2 rounds of security margin); no invariant subspace attacks have been found; Gröbner basis cryptanalysis fails at greatly weakened versions (10-bit fields) already. Detailed analysis is presented in Appendix B.

6. Lookup Tables and System of Constraints for Bar

This section creates tables and a set of constraints such that for x, y \in \mathbb{F}_p it holds y = \mathsf{Bar}(x) if and only if this set of constraints is satisfied. Two challenges are faced:

• The S-box S_i acts on a domain of size s_i, making each S-box potentially unique.
• Since \prod_i s_i > p, there exist distinct elements in \mathbb{Z}_{s_1} \times \ldots \times \mathbb{Z}_{s_n} that produce the same x \in \mathbb{F}_p. The constraint system must prevent this collision.

These challenges are addressed with two additional sets of variables (z_1, \ldots, z_n) and (c_1, \ldots, c_n). The variable z_i encodes if x_i < p' (S_i is non-linear) or x_i \ge p' (S_i is identity):

The variables (c_1, \ldots, c_n) indicate if a tuple overflows p. Only sequences output by a finite-state automaton \mathcal{A} are allowed; they characterize all tuples (x_1, \ldots, x_n) \in \mathbb{N}^n with \sum_{i=1}^{n} x_i b_i < p.

Three 4-ary tables are created: T_2 contains all binary sequences of length 4; T_3 contains all outputs of length 4 of the automaton \mathcal{A}; T_1 encodes the output of the S-boxes S_1, \ldots, S_n.

The claim is that y = \mathsf{Bar}(x) holds if and only if for x, y \in \mathbb{F}_p and (x_1, \dots, x_n), (y_1, \dots, y_n) \in \mathbb{N}^n the following constraints are satisfied:

The total number of lookup constraints is n + \lceil (n-1)/3 \rceil + \lceil n/4 \rceil \approx 1.59n.

6.1 Soundness and Completeness

Proof sketch. The proof proceeds in four steps: (1) construct x_i, y_i from Decomp and SBox and verify constraints (12) and (13); (2) define z_i satisfying Table T_2 constraints; (3) define c_i satisfying Table T_3 constraints, showing that the finite-state automaton \mathcal{A} captures all valid sequences by ruling out forbidden subsequences (2, \ldots), (\ldots, 0, 2, \ldots), (\ldots, 1, 0, \ldots), and (\ldots, 2, 0, \ldots); (4) verify that (x_i, i \cdot z_i, y_i, c_i) satisfies Table T_1 constraints by case analysis on each possible range of x_i.

Proof sketch. For \mathcal{R}_{< p} := \{(z_1, \dots, z_n) \in \mathcal{R} : \sum_{i=1}^{n} z_i b_i < p\}, the proof shows: (1) (x_1, \ldots, x_n) = \mathsf{Decomp}(x) by showing the case \hat{x} \ge p leads to a contradiction via Table T_3 constraints; (2) for each i, y_i = S(x_i) follows from Table T_1 and the binary encoding of z_i; (3) combining \mathsf{Bar} = \mathsf{Comp} \circ \mathsf{SBox} \circ \mathsf{Decomp} with constraint (13) yields y = \mathsf{Bar}(x).

7. Concrete Instances

The values of \alpha_1, \alpha_2, \beta_1, \beta_2 are: for p = p_{\text{BLS381}}: (1, 3, 2, 4); for p = p_{\text{BN254}}: (1, 3, 2, 4); for p = p_{\text{ST}}: (1, 2, 3, 4).

For the Bar function, a decomposition into n = 27 small S-boxes is chosen for p being the order of BLS12-381 or BN254 curves.

BLS12-381. p_{\text{BLS381}} = \mathtt{0x73eda753\ldots00000001}. The largest prime p' smaller than or equal to v = \min_{1 \le i \le 27} v_i is p' = 659.

BN254. p_{\text{BN254}} = \mathtt{0x30644e72\ldots f0000001}. The largest prime p' smaller than or equal to v is p' = 641.

Special prime. A 250-bit prime p_{\text{ST}} has been crafted for proof systems that are not elliptic curve based, admitting the representation:

i.e., s_2 = s_3 = \dots = s_{24} = 1024, s_{25} = 1023, v_1 = v_2 = \dots = v_{25} = 1018. This makes the decomposition and modular reduction extremely fast.

8. Performance

8.1 Proof System Performance

8.1.1 Circuit metrics. Two metrics are used. The first counts regular gates (arithmetic + lookup), as defined in the Plonk and Plookup papers. The second, the area-degree product, applies to custom gates and estimates prover cost as (number of gates) × (max degree of a gate constraint) × (gate arity).

8.1.2 Measuring hash functions. RC (BLS/BN primes): Bricks: 8 gates per round; Concrete: 6 gates per round; Bars: 282 gates per round (decomposition 26, composition 26, table 42 per element). Total: 8 \cdot 6 + 6 \cdot 8 + 282 = 378 regular gates. Area-degree product: 378 \cdot 15 = 5670.

Poseidon-128 with 2 inputs needs 633 gates. Rescue with 2 inputs requires 480 regular gates (Rescue-Prime: 420). Sinsemilla for k = 10, t = 51 yields about 510 regular gates, with an optimized area-degree product of 1530.

8.2 Plain Implementation Performance

RC was implemented in pure Rust using the ff_ce library for field operations. All benchmarks were obtained on a Linux Desktop PC with an Intel i7-4790 CPU (3.6 GHz) and 16 GB RAM. Key results: RC is faster than Poseidon by a factor of 5 for p_{\text{BN254}} and p_{\text{BLS381}}, and by a factor of 16 for p_{\text{ST}}. Compared to fast binary hash functions, RC is only about 5x slower than Blake2, while requiring 7 times fewer Plookup gates.

For computing a Merkle tree with 2^{20} elements: RC requires 3.91s (BN) / 3.97s (BLS) / 1.36s (ST), compared to Poseidon at 22.6s (BN) and SHA-256 at 0.624s.

Appendix A. Bijectivity of RC Components

A.1 Bijectivity of Bricks

Given \alpha_1, \alpha_2, \beta_1, \beta_2 \in \mathbb{F}_p such that \alpha_i^2 - 4 \cdot \beta_i is a non-quadratic residue mod p, the Bricks function is invertible. Given \mathsf{Bricks}(x_1, x_2, x_3) = (y_1, y_2, y_3),

since (1) x \mapsto x^d is invertible due to \gcd(d, p-1) = 1; (2) z^2 + \alpha_i z + \beta_i \neq 0 for each z \in \mathbb{F}_p because \alpha_i^2 - 4\beta_i is not a square.

A.2 Bijectivity of Bar

Proof sketch. For \mathcal{R}_{< p} := \{(z_1, \dots, z_n) \in \mathcal{R} : \sum_{i=1}^{n} z_i b_i < p\}, the proof shows: (1) Decomp is injective and \mathsf{Decomp}(\mathbb{F}_p) \subseteq \mathcal{R}_{< p}; (2) \mathsf{SBox}(\mathcal{R}_{< p}) \subseteq \mathcal{R}_{< p}, so SBox permutes \mathcal{R}_{< p}; (3) Comp is injective on \mathcal{R}_{< p}. It follows that \mathsf{Bar} = \mathsf{Comp} \circ \mathsf{SBox} \circ \mathsf{Decomp} is injective and hence surjective.

The key step in (2) uses the property that for every 1 \le k \le n:

Informally, the sum of the maximal values of the first l = n - k least significant positions equals the value of the next greater significant position minus 1.

A.3 The SBox Function

The non-identity part f : \mathbb{F}_{p'} \to \mathbb{F}_{p'} of each S-box must be a permutation of \mathbb{F}_{p'} with high degree and a dense polynomial description. The technique: (1) choose the smallest prime d = 2^n - 1 with \gcd(d, p' - 1) = 1; (2) compute the r-fold composition

with r = 2 \lceil \log_d(p') \rceil, aiming for degree p' - 2 and p' - 1 non-zero coefficients.

Appendix B. Security Analysis

B.1 Statistical Attacks

The security analysis considers a variant RC′ in which the middle component Bricks-Concrete-Bars-Concrete-Bricks is replaced with a single Bricks. If RC′ is secure against statistical attacks, then so is the full RC.

B.1.1 Differential Cryptanalysis. The differential probability is defined as

For the power map: \mathrm{DP}_{\max}(x \mapsto x^d) = (d-1)/p. The best differential characteristic over two rounds has probability at most 4(d-1)^2 / p^4 \ll p^{-3}, due to at least four active words each contributing a factor proportional to p^{-1}. Two consecutive rounds suffice for security against differential attacks.

B.1.2 Truncated and Impossible Differentials. Truncated differentials with probability 1 exist over a single round but cannot be extended further. An impossible differential exists over two rounds. Three rounds suffice for security.

B.1.3 Meet-in-the-Middle and Boomerang. These rely on chaining two good differential/linear trails. The six-round RC′ is secure.

B.1.4 Rebound Attacks. The inbound phase can cover two rounds; the outbound phase can extend one round in each direction. RC′ with six rounds is secure since no attack on five or more rounds was found (at least 2 rounds of security margin).

B.1.5 Linear and Zero-Correlation. Linear attacks pose no threat with the same number of rounds as for differential cryptanalysis. Finding zero-correlation linear hulls is infeasible for the four Bricks layers.

B.1.6 Square/Integral & Mixture Differential. Only one round can be covered with an integral attack. Both Bricks and Concrete mix the state components, preventing extension.

B.2 Invariant Subspace Attack and Fixed Points

B.2.1 Invariant Subspaces. For the Bars layer, subspaces where only a single word is active, and subspaces of the form \langle (1,1,0) \rangle, \langle (1,0,1) \rangle, \langle (0,1,1) \rangle, or \langle (1,1,1) \rangle are invariant. However, there is no invariant subspace for Bricks, ensuring security against this attack.

B.2.2 Fixed Points. The only fixed points for Bricks are (0,0,0), (\pm 1, 0, 0), and (\pm \sqrt{-1}, 0, 0). For Bar, the number of fixed points is \bigl(\prod_{i=1}^{n} (s_i - p')\bigr)^3. For p_{\text{BLS381}} \approx 2^{256}, the probability for a random point to be a fixed point is approximately 2^{-364.4}.

B.3 Gröbner Basis Cryptanalysis

Under the assumption of a semi-regular input system, the degree of regularity d_{\text{reg}} provides an upper bound for the highest degree element in a Gröbner basis. The complexity bound is:

where \omega is the linear algebra constant. For the algebraic model of Bar, the expected degree of regularity is d_{\text{reg}}^{\text{Bar}} = 1 - n + 2 \sum_{i=1}^{n} (s_i - 1) \approx 2n \sqrt[n]{p}.

Practical experiments on small-scale instances of Concrete ∘ Bars ∘ Concrete in the CICO-setting show the ratio d_{\text{reg}} / d_{\text{mag}} \approx 3 and practical runtimes approximately the square root of the complexity estimates. For the full-scale instance with n = 27:

far exceeding the security level of 2^{128}.

B.4 Other Algebraic Attacks

B.4.1 Interpolation Analysis. The total degree of one word of the permutation RC over \mathbb{F}_p is d_B \cdot d_S^6. It suffices that d_B > 2^{127}. Since Bars is defined non-linearly on at least p'^{27} \ge 2^{251} points, the degree far exceeds this requirement. For small-scale instances the degree was always maximal (p - 2).

B.4.2 Higher-Order Differential and Zero-Sum. Security against interpolation implies security against higher-order differential attacks. The authors do not claim security against zero-sum partitions, as there is a gap in the literature between the number of rounds coverable by a zero-sum partition and the rounds breakable in a sponge hash function.

B.5 Side-channel Attacks

For the RC design, its native execution can be run without table lookups as the table is computed as a polynomial. If prime field operations were implemented in constant-time, the function would be leakage-free.

B.6 Every Building Block is Necessary

B.6.1 Necessity of Bars. Without Bars, a much higher number of rounds is needed. Using Gröbner basis approaches in the CICO setting, the authors show that r \ge 54 rounds are needed for the full-round equation approach, and r \ge 33 for the intermediate variables approach (both for p \approx 2^{256}).

B.6.2 Necessity of Concrete. Without Concrete, the subspaces \langle (0,1,0), (0,0,1) \rangle and \langle (0,0,1) \rangle would be invariant through the whole permutation.

B.6.3 Necessity of Bricks. Without Bricks, an attacker could work with a system of equations over the smaller fields of the Bars layer. Also, both outbound phases of a rebound attack would be linear.

Acknowledgements

Special thanks to Ferdinand Sauer for valuable discussion on Gröbner basis computations and for assistance in conducting the practical experiments. Thanks to Alex Vlasov (Matter Labs) for modular math optimizations and comments.

Lorenzo Grassi is supported by the European Research Council (ERC) under grant ERC-2017-ADG Nr. 788980 ESCADA. Roman Walch is supported by the “DDAI” COMET Module within the COMET Programme, funded by the Austrian Federal Ministry for Transport, Innovation and Technology (bmvit), the Austrian Federal Ministry for Digital and Economic Affairs (bmdw), the Austrian Research Promotion Agency (FFG), the province of Styria (SFG) and partners from industry and academia.

References

1. [IAIK21] Hash functions for zero-knowledge applications zoo. IAIK, Graz University of Technology (2021).
2. [Tor21] Tornado cash privacy solution version 1.4 (2021).
3. [ZCa22] ZCash protocol specification (2022).
4. [Alb+19a] Albrecht, M.R. et al. “Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC”. In: ASIACRYPT 2019. LNCS, vol. 11923, pp. 371–397.
5. [Alb+19b] Albrecht, M.R. et al. “Feistel Structures for MPC, and More”. In: ESORICS 2019. LNCS, vol. 11736, pp. 151–171.
6. [Alb+16] Albrecht, M.R. et al. “MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity”. In: ASIACRYPT 2016. LNCS, vol. 10031, pp. 191–219.
7. [Aly+20] Aly, A. et al. “Design of symmetric-key primitives for advanced cryptographic protocols”. IACR Trans. Symmetric Cryptol. 2020(3), 1–45.
8. [AshDho18] Ashur, T., Dhooghe, S. “MARVELlous: a STARK-Friendly Family of Cryptographic Primitives”. ePrint 2018/1098.
9. [BaiSteVau07] Baignères, T., Stern, J., Vaudenay, S. “Linear Cryptanalysis of Non Binary Ciphers”. In: SAC 2007. LNCS, vol. 4876, pp. 184–211.
10. [Bar+05] Bardet, M. et al. “Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems”. In: MEGA 2005.
11. [Bar+22] Bariant, A. et al. “Practical algebraic attacks against some arithmetization-oriented hash functions” (2022).
12. [Ben+18] Ben-Sasson, E. et al. “Fast Reed-Solomon interactive oracle proofs of proximity”. In: ICALP 2018. LIPIcs, vol. 107.
13. [Ben+19] Ben-Sasson, E. et al. “Aurora: Transparent succinct arguments for R1CS”. In: EUROCRYPT 2019. LNCS, vol. 11476, pp. 103–128.
14. [Ber+08] Bertoni, G. et al. “On the Indifferentiability of the Sponge Construction”. In: EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197.
15. [Ber+11] Bertoni, G. et al. “On alignment in Keccak”.
16. [Bey+20] Beyne, T. et al. “Out of Oddity – New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems”. In: CRYPTO 2020. LNCS, vol. 12172, pp. 299–328.
17. [BihBirSha99] Biham, E., Biryukov, A., Shamir, A. “Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials”. In: EUROCRYPT 1999. LNCS, vol. 1592.
18. [BihSha90] Biham, E., Shamir, A. “Differential Cryptanalysis of DES-like Cryptosystems”. In: CRYPTO 1990. LNCS, vol. 537, pp. 2–21.
19. [BihSha93] Biham, E., Shamir, A. Differential Cryptanalysis of the Data Encryption Standard. Springer (1993).
20. [BogWan12] Bogdanov, A., Wang, M. “Zero Correlation Linear Cryptanalysis with Reduced Data Complexity”. In: FSE 2012. LNCS, vol. 7549, pp. 29–48.
21. [Bon+21] Boneh, D. et al. “Halo infinite: Proof-carrying data from additive polynomial commitments”. In: CRYPTO 2021. LNCS, vol. 12825, pp. 649–680.
22. [Boo+18] Bootle, J. et al. “Arya: Nearly linear-time zero-knowledge proofs for correct program execution”. In: ASIACRYPT 2018. LNCS, vol. 11272, pp. 595–626.
23. [Bou+11] Boura, C. et al. “Higher-Order Differential Properties of Keccak and Luffa”. In: FSE 2011. LNCS, vol. 6733, pp. 252–269.
24. [BowHop21] Bowe, S., Hopwood, D. “Zcash Orchard: Sinsemilla Gadget” (2021).
25. [Bun+21] Bünz, B. et al. “Proof-carrying data without succinct arguments”. In: CRYPTO 2021. LNCS, vol. 12825, pp. 681–710.
26. [Bun+20] Bünz, B. et al. “Recursive proof composition from accumulation schemes”. In: TCC 2020. LNCS, vol. 12551, pp. 1–18.
27. [ChiOjhSpo20] Chiesa, A., Ojha, D., Spooner, N. “Fractal: Post-quantum and transparent recursive proofs from holography”. In: EUROCRYPT 2020. LNCS, vol. 12105, pp. 769–793.
28. [CidLeu05] Cid, C., Leurent, G. “An Analysis of the XSL Algorithm”. In: ASIACRYPT 2005. LNCS, vol. 3788, pp. 333–352.
29. [CouPie02] Courtois, N.T., Pieprzyk, J. “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations”. In: ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287.
30. [Cox+97] Cox, D.A. et al. Ideals, varieties, and algorithms – an introduction to computational algebraic geometry and commutative algebra. 2nd ed. Springer (1997).
31. [DaeKnuRij97] Daemen, J., Knudsen, L.R., Rijmen, V. “The Block Cipher Square”. In: FSE 1997. LNCS, vol. 1267, pp. 149–165.
32. [DaeRij02] Daemen, J., Rijmen, V. The Design of Rijndael: AES. Springer (2002).
33. [Eic+20] Eichlseder, M. et al. “An algebraic attack on ciphers with low-degree round functions: Application to full MiMC”. In: ASIACRYPT 2020. LNCS, vol. 12491, pp. 477–506.
34. [GabWil20] Gabizon, A., Williamson, Z.J. “plookup: A simplified polynomial protocol for lookup tables”. ePrint 2020/315. [page on this site]
35. [GabWilCio19] Gabizon, A., Williamson, Z.J., Ciobotaru, O. “Plonk: Permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge”. ePrint 2019/953. [page on this site]
36. [Gen07] Genovese, G. “Improving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields”. J. Symb. Comput. 42(1-2), 159–177 (2007).
37. [Gol+21] Goldberg, L. et al. “Cairo – a Turing-complete STARK-friendly CPU architecture”. ePrint (2021).
38. [Gra18] Grassi, L. “Mixture Differential Cryptanalysis: a New Approach to Distinguishers and Attacks on round-reduced AES”. IACR Trans. Symmetric Cryptol. 2018(2), 133–160.
39. [Gra+22] Grassi, L. et al. “A New Feistel Approach Meets Fluid-SPN: Griffin for Zero-Knowledge Applications”. ePrint 2022/403. [page on this site]
40. [Gra+21a] Grassi, L. et al. “The Legendre symbol and the modulo-2 operator in symmetric schemes over \mathbb{F}_p^n”. ePrint (2021).
41. [Gra+21b] Grassi, L. et al. “Poseidon: A new hash function for zero-knowledge proof systems”. USENIX Security 2021. [page on this site]
42. [Gra+20] Grassi, L. et al. “On a generalization of substitution-permutation networks: The HADES design strategy”. In: EUROCRYPT 2020. LNCS, vol. 12106, pp. 674–704. [page on this site]
43. [Gra+21c] Grassi, L. et al. “Invertible Quadratic Non-Linear Layers for MPC-/FHE-/ZK-Friendly Schemes over \mathbb{F}_p^n”. ePrint 2021/1695.
44. [Gra+16] Grassi, L. et al. “Subspace Trail Cryptanalysis and its Applications to AES”. IACR Trans. Symmetric Cryptol. 2016(2), 192–225.
45. [Gra+17] Grassi, L. et al. “A New Structural-Differential Property of 5-Round AES”. In: EUROCRYPT 2017. LNCS, vol. 10211, pp. 289–317.
46. [Gra+21d] Grassi, L. et al. “Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer”. IACR Trans. Symmetric Cryptol. 2021(2).
47. [Gro16] Groth, J. “On the size of pairing-based non-interactive arguments”. In: EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326.
48. [Gui+11] Guido, B. et al. “Cryptographic sponge functions” (2011).
49. [Hop19] Hopwood, D. “Zcon0 conference notes” (2019).
50. [JakKnu97] Jakobsen, T., Knudsen, L.R. “The Interpolation Attack on Block Ciphers”. In: FSE 1997. LNCS, vol. 1267, pp. 28–40.
51. [KelRos21] Keller, N., Rosemarin, A. “Mind the Middle Layer: The HADES Design Strategy Revisited”. In: EUROCRYPT 2021. LNCS, vol. 12697, pp. 35–63. [page on this site]
52. [Knu94] Knudsen, L.R. “Truncated and Higher Order Differentials”. In: FSE 1994. LNCS, vol. 1008, pp. 196–211.
53. [Knu98] Knudsen, L.R. “DEAL – A 128-bit Block Cipher” (1998).
54. [Lai94] Lai, X. “Higher order derivatives and differential cryptanalysis”. In: Communications and Cryptography. pp. 227–233. Springer US (1994).
55. [Lam+09] Lamberger, M. et al. “Rebound Distinguishers: Results on the Full Whirlpool Compression Function”. In: ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143.
56. [Lea+11] Leander, G. et al. “A Cryptanalysis of PRINTcipher: The Invariant Subspace Attack”. In: CRYPTO 2011. LNCS, vol. 6841, pp. 206–221.
57. [Lea+15] Leander, G. et al. “A Generic Approach to Invariant Subspace Attacks”. In: EUROCRYPT 2015. LNCS, vol. 9056, pp. 254–283.
58. [Mal+19] Maller, M. et al. “Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings”. In: CCS 2019. pp. 2111–2128.
59. [Mat93] Matsui, M. “Linear Cryptanalysis Method for DES Cipher”. In: EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397.
60. [Men+09] Mendel, F. et al. “The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl”. In: FSE 2009. LNCS, vol. 5665, pp. 260–276.
61. [Ozd+20] Ozdemir, A. et al. “Scaling verifiable computation using efficient set accumulators”. In: USENIX Security 2020. pp. 2075–2092.
62. [Par+13] Parno, B. et al. “Pinocchio: Nearly practical verifiable computation”. In: IEEE S&P 2013. pp. 238–252.
63. [Pea+22] Pearson, L. et al. “Plonkup: Reconciling Plonk with Plookup”. ePrint (2022).
64. [SauSze21] Sauer, J.F., Szepieniec, A. “SoK: Gröbner basis algorithms for arithmetization oriented ciphers”. ePrint (2021).
65. [Sze21] Szepieniec, A. “On the use of the Legendre symbol in symmetric cipher design”. ePrint (2021).
66. [Tra+20] Tramèr, F. et al. “Remote side-channel attacks on anonymous transactions”. In: USENIX Security 2020. pp. 2739–2756.
67. [Wag99] Wagner, D.A. “The Boomerang Attack”. In: FSE 1999. LNCS, vol. 1636, pp. 156–170.
68. [Wil20] Williamson, Z. “zkSummit: Plookup” (2020).
69. [Woo+14] Wood, G. et al. “Ethereum: A secure decentralised generalised transaction ledger” (2014).