Arithmetization-Oriented Hash Functions

This is a research wiki on the security of arithmetization-oriented (AO) cryptographic primitives: hash functions, permutations, ciphers, and signature schemes designed for efficient evaluation inside arithmetic circuits, zero-knowledge proof systems, MPC protocols, and other algebraic settings.

Context and motivation

This wiki is part of BaDaaS's research effort into the cryptanalysis of AO constructions. It is related to the Poseidon initiative by the Ethereum Foundation, which coordinates security analysis of Poseidon and related primitives used across the Ethereum ecosystem.

At BaDaaS, we are interested in the cryptanalysis of AO constructions across the board. As a starting point for our research, we are building this live wiki with:

• Documentation of all known AO primitive designs, their security claims, and the attacks published against them.
• Sage code providing reference implementations, attack reproductions, and algebraic experiments.
• Industrial usage mapping showing which primitives are deployed in which proof systems and protocols.
• Resource gathering from research papers, but also from textbooks on computational algebra, Groebner bases, and solving multivariate polynomial systems over finite fields, to identify whether unexplored mathematical landscapes could yield new cryptanalytic techniques.

Scope

Traditional hash functions (SHA-256, BLAKE3, Keccak) are designed for efficient evaluation on CPUs. They rely on bitwise operations (XOR, AND, bit rotation) that are cheap in hardware but expensive inside arithmetic circuits over large prime fields $\mathbb{F}_p$.

AO primitives replace bitwise operations with field arithmetic: multiplications, exponentiations, and linear maps over $\mathbb{F}_p$. This makes them orders of magnitude more efficient inside SNARKs, STARKs, and other proof systems, but it also changes the threat model. The security analysis of these primitives requires algebraic cryptanalysis, a different toolset from the classical differential/linear methods used for AES or SHA.

Primitives covered

Primitive	S-box	Structure	Year
Poseidon	$x^{\alpha}$	SPN (full + partial rounds)	2019
Poseidon2	$x^{\alpha}$	SPN (external + internal rounds)	2023
Neptune	$x^{\alpha}$	SPN (Poseidon variant)	2021
Anemoi	Flystel	SPN (open Flystel)	2022
Griffin	$x^{\alpha}$ / $x^{1/\alpha}$	Horst	2022
Rescue / Rescue-Prime	$x^{\alpha}$ / $x^{1/\alpha}$	SPN	2020
Reinforced Concrete	Bars + Bricks + Concrete	SPN (lookup-friendly)	2022
Tip5	Lookup + $x^{\alpha}$	SPN (Tip4Prime successor)	2023

Analysis dimensions

Each primitive is studied along three axes:

Arithmetization efficiency

The arithmetization section covers the constraint cost of evaluating each primitive inside the three main proof system families:

• R1CS (Groth16, Spartan, Marlin)
• AIR (STARKs)
• PlonK-ish (PLONK, Halo 2, HyperPlonk)

CPU efficiency

The CPU efficiency section analyses the native performance of each primitive outside of circuits: field arithmetic costs, the expense of inverse S-boxes, and the impact of field choice on throughput.

Cryptanalysis

The attacks section covers the cryptanalytic techniques used to evaluate these primitives:

• Algebraic attacks (interpolation, invariant subspace)
• Groebner basis attacks
• Differential cryptanalysis
• Higher-order differentials and algebraic degree
• Statistical attacks (linear, integral)

Sage code

All Sage scripts live in the sage/ directory at the repository root. They are referenced from the documentation pages and can be executed independently:

cd sage/poseidon
sage permutation.sage

References

Papers are tracked using papyrus. Each primitive page includes a chronological list of relevant publications with links to the original papers and to cryptography.academy where available.