Anemoi is a family of ZK-friendly permutations, that can be used to construct efficient hash functions and compression functions. Anemoi relies on two new components: a new S-box called Flystel, exploiting a previously unknown relationship with CCZ-equivalence, and a new mode of operation called Jive.

The Flystel is a pair of functions (the open and closed Flystel) relying on two quadratic functions Qγ, Qδ and a permutation E. While the open Flystel is a high degree permutation of (F_q)^2 the closed Flystel is a low degree function of (F_q)^2. The two variants are CCZ-equivalent, meaning that it is possible to encode the verification of the evaluation of the open Flystel H using the polynomial representation of the closed Flystel V.

Jive is a dedicated mode for compression functions in a Merkle tree. Given a permutation P of (F_q^m)^b, we can construct a b-to-1 compression function.

The internal state of Anemoi is represented as a matrix with l columns and 2 rows. A round function is then a permutation of (F_q)^{2l}, where q is either a prime number or a power of 2. The function applied at each round has a classical Substitution-Permutation Network (SPN) structure: first the constant addition, then the linear layer, and finally the S-box layer (i.e. the Flystel).

The number of rounds is determined by the complexity of algebraic attacks.

Cryptanalysis

The FreeLunch attack and 6 worlds of GB are two recent algebraic cryptanalysis on Anemoi. Both papers slightly reduce the security margin of Anemoi for the instance with l=1.

• Authors: Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum
  Title: The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives, CRYPTO 2024
• Authors: Katharina Koschatko, Reinhard Lüftenegger, Christian Rechberger
  Title: Exploring the Six Worlds of Gröbner Basis Cryptanalysis: Application to Anemoi, 2024

Implementation

The authors propose comparison with various instances of Rescue–Prime, Poseidon, Griffin with respect to SNARK metrics: R1CS and Plonk, and STARK: AIR.

The block cipher Arion and the hash function ArionHash are constructed over F_p for odd and particularly large primes, targeting low multiplicative complexity in a prover circuit. Both are based on the Generalized Triangular Dynamical System (GTDS), which uses a polynomial dynamical system to construct cryptographic permutations over finite fields.

ArionHash aims for efficient implementation in zkSNARK protocols and Zero-Knowledge proof systems, targeting BLS12 and BN254 curves. Its core primitive, the permutation Arion-π, uses in each round a polynomial of very high degree in one branch and low degree polynomials in the remaining branches to decrease the number of necessary rounds to achieve the desired security.

Arion and ArionHash also have aggressive versions, α-Arion and α-ArionHash, which avoid a proposed probabilistic Gröbner basis attack.

Cryptanalysis

• Authors: Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum
  Title: The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives, CRYPTO 2024
  Recovery of a CICO solution for 4 rounds of Arion (resp. of α-Arion) with attack complexities as low as 2^98 (resp. 2^83) for its weakest variants

Implementation

The designers have implemented ArionHash and α-ArionHash, and compared their Plonk and R1CS constraints to Poseidon, Griffin and Anemoi.

Chaghri takes Vision as a starting point but while the two steps of a Marvellous round employ different S-boxes, every round of Chaghri is composed of two similar steps. Chaghri is a 8-round SPN construction defined over F_{2^63}. The non-linear layer is composed of G, a power function using the Gold exponent 2^32 + 1, and B, an affine polynomial. In a first version of the design, the authors used B = c1 + c2 x^8, and following the work by Liu et al. they moved to another affine layer B = c1 + c2 x + c3 x^4 + c^4 x^256.

Cryptanalysis

• Authors: Fukang Liu, Ravi Anand, Libo Wang, Willi Meier, Takanori Isobe
  Title: Coefficient Grouping: Breaking Chaghri and More, EUROCRYPT 2023
  Liu et al. have shown that the first choice of affine layer implies a linear increase of the algebraic degree leading to a practical higher-order differential attack.
• Authors: Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
  Title: Coefficient Grouping for Complex Affine Layers, CRYPTO 2023
  This more recent analysis of complex affine layers shows that the new parameters are not part of good affine layers (that should lead to an exponential growth of the degree).

Implementation

The authors have implemented Chaghri using HElib, a library implementing the BGV variant, and compared the results with AES.

Unlike other primitives Ciminion does not use a power map as S-box. The non-linearity instead comes from the use of Toffoli gates.

Cryptanalysis

• Authors: Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin
  Title: Algebraic Attacks against Some Arithmetization-Oriented Primitives, ToSC 2022
  The authors propose an alternative way to set up a system of equations for algebraic attacks on Ciminion, this leads to much faster attacks than expected by the designers.
• Author: Augustin Bariant
  Title: Algebraic Cryptanalysis of Full Ciminion, SAC 2024
  The paper presents a new univariate modeling of Ciminion
• Authors: Lulu Zhang, Meicheng Liu, Shuaishuai Li, Dongdai Lin
  Title: Cryptanalysis of Ciminion, INSCRYPT 2022
  The authors propose higher order differential cryptanalysis and integral cryptanalysis.

Implementation

It is a low-depth, MPC friendly weak PRF which uses a combination of linear operations in two different fields, and can be implemented in depth-2 ACC^0 circuit.The key space is K_λ = Z_p^{m×n}​, the domain X_λ = Z_p^n​ and the range Y_λ = Z_q​ where $p$ and q are primes.
Define a nonlinear mapping map_{p,q} from {0,1,…p−1}^m to Z_q

map_{p,q}​ (y) = ∑_{i=1}^n y_i mod q

Then the mod−p/mod−q weak PRF is defined as

F_A(x) = map(Ax)

for an input x in Z_p^n​ and a key A in Z_p^{m×n}​.

Here, y = Ax will be a vector in Z_p^m​ which is viewed as a vector in {0,1,…p−1}^m with integer entries; to which we apply the mapping map_{p,q}​ to get an output in Z_q.
For efficiency, authors suggest using a circulant matrix as a key. Moreover, the linear mapping map_{p,q}​ can be replaced by multiplication by a public matrix G in Z_q^{l×n}​ to get a longer output. The main focus is on the case of mod−2/mod−3 weak PRF for which the authors provide a distributed evaluation protocol. The authors also propose an ‘alternative’ binary weak PRF F from Z_2^n × Z_2^ n to Z_2^n which can be described as

F(k,x) = (⟨k,x⟩ mod 2+⟨k,x⟩ mod 3) mod 2

where both key $k$ and input $x$ are binary vectors of length n.

Cryptanalysis

• Authors: Jung Hee Cheon, Wonhee Cho, Jeong Han Kim, Jiseung Kim
  Title: Adventures in Crypto Dark Matter: Attacks and Fixes for Weak Pseudorandom Functions, PKC 2021
  Authors propose an attack where the advantage of an alternative Mod-2/Mod-3 weak PRF is 2^{−0.105n} with the size of input space n. Similarly, they provide a heuristic attack for circulant mod−2/mod−3 weak PRF with an advantage 2^{−0.21n}. The attack is based on the conditional probability of certain input vectors given that the outputs are ‘zero’, which deviates from 1/2. They suggest using a circulant key generated by two vectors to prevent this attack.
• Authors: Thomas Johansson, Willi Meier, Vu Nguyen
  Title: Differential cryptanalysis of Mod-2/Mod-3 constructions of binary weak PRFs, IEEE 2023
  Authors propose an improved attack for the alternative weak PRF candidate. Their attack outperforms the attack by Cheon et. al. by achieving complexity of O(2^{0.166n})

Elisabeth is a family of stream ciphers designed for Torus Fully Homomorphic Encryption (TFHE) applications published at Asiacrypt 2022. Its structure is heavily inspired by FliP: a subkey with a size much bigger than the security level is generated, and then stored. Then, to generate each block of keystream, a complex non-linear function is applied on a deterministically chosen subset of the subkey bits. Operating in this way means that the subkey is not updated, and thus that noise does not get an opportunity to grow. This is summarized in the first figure to the right.

The filter function has a complex design: it essentially consists in several iterations of an SPN-like structure, whereby S-boxes are applied in parallel to the filter’s internal state, followed by partial-rank diffusion layer that uses only additions, and the mixing
of some key words (see Figure to the right). Several such functions are evaluated in parallel on different parts of the subkey, and then the sum of their outputs is returned as a keystream word.

The cipher operates on Z/16Z. As 16 is even, the S-boxes have to have a specific property, nega-cyclicity, meaning that S(x)=16-x for all x.

Following the cryptanalysis by Gilbert et al, the designers published a follow-up paper describing potential strategies to fix the stream cipher. They in particular
proposed new variants: Elisabeth-b, Gabriel, and Margrethe.
– Elisabeth-b is built on the same principle but uses a filter with a larger internal state.
– Gabriel complexifies the design of the filter function by giving it another component intended to ensure a dense enough polynomial representation, thus blocking the attacks of Gilbert et al.
– Margrethe mixes arithmetic over Z/16Z and F_2^18.

Cryptanalysis

• Authors: Henri Gilbert, Rachelle Heim Boissier, Jérémy Jean, Jean-René Reinhard
  Title: Cryptanalysis of Elisabeth-4, ASIACRYPT 2023
  This paper proposes different variants of key recovery attacks on the full version of Elisabeth-4 cipher. The main flaw they identified is an improper estimation of the number of monomials present in the polynomial representation of the filter function, which allowed the attackers to present an efficient linearization of the primitive.

Inspired by the Filter Permutator (FP) paradigm proposed for FLIP, the authors proposed a modified version, the Improved Filter Permutator (IFP) paradigm, considering two sizes of registers.
The stream cipher family FiLIP is then an instantiation of the IFP paradigm where the PRNG is a variant of AES in counter mode, and the wire-cross permutations are generated by the Knuth shuffle.

FiLIP_{DSM} and FiLIP_{XMAJ} are specific ciphers instantiated respectively by Direct Sums of Monomials (DSM) functions, which are generalization of FLIP functions, and XOR-MAJ functions.

Implementation

Authors proposed comparison with FLIP and other FHE-friendly primitives.

FLIP is a family of stream ciphers designed to address some of the limitations of previous schemes, by allowing constant and reducing noise. This is possible thanks to a novel construction resembling a filter generator with a constant register that is permuted before entering the filtering function, thereby limiting the circuit’s multiplicative depth.

The original construction has been revised after Duval et al. showed several vulnerabilities.

Cryptanalysis

• Attack by: Sébastien Duval, Virginie Lallemand, and Yann Rotella
  Title: Cryptanalysis of the FLIP Family of Stream Ciphers, CRYPTO 2016
  The authors present an attack on the original version of FLIP, exploiting the structure of the filter function and the constant internal state of the cipher.

Implementation

The authors investigated the performances of different instances of FLIP for FHE schemes using HElib and compared them with Trivium, Kreyvium and LowMC.

Generalized Feistel MiMC (GMiMC) refers to a family of block ciphers and hash functions based on the MiMC permutation. It can be seen as a further generalization of the (balanced) Feistel-MiMC.

The GMiMC family is comprised of four variants:
– an unbalanced Feistel network (UFN) with contracting round functions (CRF) (Figure 1);
– a UFN with expanding round functions (ERF) (Figure 2);
– a Nyberg generalized Feistel network (Figure 3);
– and a multi-rotating Feistel network (Figure 4).

All of the above Feistel networks can be used to create block ciphers. Hash function variants are, in turn, constructed by setting the keys to 0 and applying the resulting permutation in a sponge framework.

In the initial security analysis, the authors of GMiMC consider two settings:
– Over a finite field GF(p), where p is a prime of at least 128 bits.
– Over a finite field GF(2^n), but the attacker is only restricted to a small number of plaintext-ciphertext pairs (this is intended for use in post-quantum signature schemes).

The block cipher variants can be further divided into two cases. For t the number of branches, and n the number of bits of the finite field these cases are
i) the “univariate case”, where the key size is n bits;
ii) the “multivariate case” where the key size is t*n.

Cryptanalysis

The GMiMC family has been the target of several cryptanalysis papers. Bonnetain showed a weakness among the univariate cases of GMiMC, and Beyne-Liu have described attacks in some cases for the CRF variant. The remaining analysis has largely focused on attacks in round-reduced settings, as well as distinguishers (both reduced and full-round).

• Authors: Xavier Bonnetain
  Title: Collisions on Feistel-MiMC and univariate GMiMC, 2019
  This paper describes a collision attack that applies to most variants of block cipher GMiMC in the univariate case.
• Authors: Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer.
  Title: Out of Oddity – New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems, CRYPTO 2020.
  This paper describes zero-sum distinguishers of low complexity of full-round variants of GMiMC permutations. Practical collision attacks on round-reduced variants are also presented.
  
• Authors: Arnab Roy, Elena Andreeva and Jan Ferdinand Sauer.
  Title: Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions, SAC 2020.
  The article explores several aspects of algebraic attacks on the UFN variants of GMiMC with expanding and contracting round functions. In particular, techniques for low-memory interpolation on GMiMC are presented.
  
• Authors: Tim Beyne and Yunwen Liu.
  Title: Truncated Differential Attacks on Contracting Feistel Ciphers, ToSC 2022.
  Full-round distinguishers and key-recovery attacks are presented in this work for some cases of the GMiMC CRF variant.
• Authors: Jiamin Cui, Kai Hu, Meiqin Wang and Puwen Wei.
  Title: On the Field-Based Division Property: Applications to MiMC, Feistel MiMC and GMiMC, ASIACRYPT 2022.
  This paper improves the distinguishers for GMiMC with ERF.
• Authors: Shiyao Chen, Chun Guo, Jian Guo, Li Liu, Meiqin Wang, Puwen Wei and Zeyu Xu.
  Title: Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives, ToSC 2023.
  This paper further improves the distinguishers on the different GMiMC variants.
  

Implementation

This PRF expands a short input using a secret key into a larger output which could be thought of as a keystream, or if it is truncated as a PRF. It works using a simple Boolean function which is applied on an input-dependent selection of key bits. In a way, it does the opposite of FLIP.

Grendel is a cipher designed for zero-knowledge and efficiently-verifiable proof systems. It utilizes Legendre symbols as component gates, which correspond to high-degree maps but can be evaluated much faster, enabling Grendel to offer the same security as high-degree maps without the associated slow evaluation time.

More specifically, Grendel is an SPN construction over F_p^m where the S-box uses the Legendre symbol; the non-linear layer is a low-degree power-map x -> x^d, with a possible sign flip given by the Legendre symbol. Grendel then employs this enhanced S-box in conjunction with the SHARK strategy.

Grendel defines a permutation that serves as a sponge function, which is used internally by the Grendel hash function.

Cryptanalysis

• Authors: Lorenzo Grassi, Dmitry Khovratovich, Sondre Rønjom, Markus Schofnegger
  Title: The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over (F_p)^n, ToSC 2022
  Preimage attacks on a sponge hash function instantiated with the full Grendel permutation with practical verification
• Authors: Jianqiang Ni, Jianhui Zhang, Gaoli Wang, Rui Li, Yanzhao Shen
  Title: Algebraic Attacks against Grendel: An Arithmetization-Oriented Primitive with the Legendre Symbol, Symmetry 2023
  Preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods

Griffin is a family of sponge hash and compression functions designed for Zero-Knowledge applications, using the internal permutation Griffin-π, which is defined over the finite field F_t where t = 3 or t is a multiple of four.

Griffin is claimed to offer efficient verifiability, high degrees of security in both forward and backward directions, minimal multiplicative complexity, and robust security against algebraic attacks on top of simple arguments against statistical attacks.

Each round function of Griffin-π consists of a nonlinear layer, the addition of a round constant, and a linear layer defined by multiplication by an MDS matrix ensuring full diffusion. The nonlinear layer of Griffin-π consists of two nonlinear sublayers defined by three different nonlinear functions. Two of these functions are invertible power maps, x ↦x^d and x ↦x^(1/d). The third function is based on the proposed Horst strategy, which uses the map (x,y) ↦(x, y⋅G(x)) for a quadratic function G such that G(z)≠0 for each z.

Cryptanalysis

• Authors: Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum
  Title: The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives, CRYPTO 2024
  Recovery of a CICO solution for 7 out of 10 rounds of Griffin in less than four hours with attack complexities as low as 2^64 for its weakest variants

Implementation

Hera is a cipher featuring a simple randomized key schedule and sparse linear layers in order to be efficiently evaluated with batching technique.

The PRF Hydra is a specific instantiation of the Megafono construction, which builds on the Hades strategy and extended versions of the Lai–Massey scheme.

Implementation

Kreyvium is designed for efficient compression of homomorphic ciphertexts and is composed of five registers. The main difference from Trivium lies in the 128-bit top and bottom registers, while the three middle registers, with lengths of 93, 84, and 111 bits, are identical to those in Trivium. Kreyvium is designed to provide 128-bit security and supports a 128-bit key and a 128-bit IV. The initial loading process differs from Trivium in that the IV and the key are loaded into the top and bottom registers, respectively. Apart from this, the initialization process is similar to Trivium, involving 1152 rounds. During each step, both the key and IV are involved linearly in the state update, and the key also contributes linearly to the keystream generation.

The authors proposed a PRF based on the Legendre symbol.

Cryptanalysis

• Authors: Ward Beullens, Tim Beyne, Aleksei Udovenko and Giuseppe Vitto
  Title: Cryptanalysis of the Legendre PRF and Generalizations, ToSC 2020
  The paper improves previous attacks on the Legendre PRF. In particular the authors broke three concrete instances of the PRF proposed by the Ethereum foundation.

LowMC is a family of flexible block ciphers based on an SPN structure defined over F_2. It is designed to be used in the context of an MPC protocol, ZK or HE scheme.

To reduce its multiplicative complexity, LowMC leaves part of the substitution layer as the identity mapping; reducing the number of Sboxes applied in parallel. It then introduces a high degree of diffusion by using pseudorandomly generated binary matrices in the linear layer in order to reach the claimed security.

The authors propose a wide range of different instantiations corresponding to 80, 128, and 256-bit security.

Cryptanalysis

• Authors: Fukang Liu, Santanu Sarkar, Gaoli Wang, Willi Meier, Takanori Isobe
  Title: Algebraic Meet-in-the-Middle Attack on LowMC, ASIACRYPT 2022
  This paper proposes an algebraic meet-in-the-middle attack on LowMC, reducing the memory and time complexities over previous attacks that retrieve the full key from a differential trail. As a consequence, some LowMC instances could be broken for the first time.

Implementation

The authors report on experiments when evaluating LowMC with MPC protocols and with FHE.

In the case of MPC, they provide GMW benchmarking results in the semi-honest setting for a single block and for multiple blocks in parallel to encrypt 12.8 Mbit of data. The security parameters are set to 80-bit for lightweight security and to 128-bit for long-term security. The experiments are run on two desktop PCs, each equipped with an Intel Haswell i7-4770K CPU with 3.5 GHz and 16GB of RAM, that are connected by Gigabit LAN.

For FHE, they implement LowMC using the holomorphic encryption library HELib.

Friday is a hash function based on the Merkle-Damgård construction and instantiated with Jarvis as its compression function. It is designed to be a STARK-friendly hash function.

Together with Jarvis, it served as a basis for the Rescue and Vision families of ZK-friendly primitives.

Cryptanalysis

• Authors: Martin R. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger
  Title: Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC, ASIACRYPT 2019
  It is shown that Friday is particularly vulnerable to Gröbner basis attacks.

Jarvis is a block cipher defined over the large finite field F_(2^n), over only one branch. Its purpose is to be very STARK-friendly. Its design is directly inspired from the AES. Specifically, it uses the x^(-1) Sbox, which translates directly to low-degree equations for the STARK proof system (x^2 S(x) = x).

Another noteworthy idea is that its affine layer is defined as the composition of B^(-1) and C, where B and C are both low-degree polynomials. That way, C o B^(-1) has a large algebraic degree, but B^(-1) and C separately account for low-degree equations in the STARK model.

Together with Friday, Jarvis served as a basis for the Rescue and Vision families of ZK-friendly primitives.

Cryptanalysis

• Authors: Martin R. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger
  Title: Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC, ASIACRYPT 2019
  It is shown that Jarvis is particularly vulnerable to Gröbner basis attacks.

Instances

Four instances are defined in the paper, and their numbers of rounds are equal to those of the AES for the same key size (although in the case of Jarvis, it is also the message block size). The instances are:

• Jarvis-128, with 10 rounds.
• Jarvis-160, with 11 rounds.
• Jarvis-192, with 12 rounds.
• Jarvis-256, with 14 rounds

Marvellous designs originally refer to Rescue and Vision. The design strategy relies on an SPN construction defined over F_q^m , where q is either a prime number or a power of 2. The construction is decomposed by steps such that one round is given by two steps. Then each step is composed of the addition of a key and round constant, the multiplication by an MDS matrix, and one S-box that is different depending on the step: a first S-box is applied on even steps and a second one is applied on odd steps.

Rescue is a ZK-friendly block cipher that has the particularity of using both a low degree S-box and its inverse. Indeed, each round of Rescue, consists of two steps: while the first one involves an S-box, the second one uses its inverse. The idea is that two consecutive steps together form a high-degree, algebraically complex operation in both ways – “forward” and “backward” – but can be modeled in a SNARK proof system such as R1CS with a few low-degree constraints.

Together with Vision, it is a successor of Jarvis and Friday, and thus is a member of the “Marvellous family”.

More up-to-date versions of Rescue exist: the one defined in Rescue-Prime, and Rescue-Prime Optimized.

Cryptanalysis

• Authors: Aurélien Boeuf, Anne Canteaut, Léo Perrin
  Title: Propagation of Subspaces in Primitives with Monomial Sboxes: Applications to Rescue and Variants of the AES, ToSC 2023
  They show the existence of weak round constants although it is unclear how this affects the security of real instances.

Implementation

Code to implement Rescue and Vision is given in https://github.com/KULeuven-COSIC/Marvellous.

Rescue–Prime is a family of ZK-friendly sponge hash functions based on the Rescue family of block ciphers. It uses a slightly different family of permutations – called Rescue-XLIX, pronounced Rescue-fourty-nine  – from those defined in the original Marvellous paper. Specifically, the round constants are derived differently, the security margin is lowered, and the order of Sboxes is flipped.

Cryptanalysis

• Authors: Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin
  Title: Algebraic Attacks against Some Arithmetization-Oriented Primitives, ToSC 2022
  The authors show that it is possible to bypass one round (two steps) when building a system to solve the CICO problem.

Rescue-Prime Optimized denotes two hash functions based on Rescue-Prime and optimized for native hashing in a STARK virtual machine such as Miden.

These two instances (achieving respectively 128 and 160 bits of security) are specifically defined over the finite field F_p is the Goldilocks prime number 2^64 – 2^32 + 1, the same field as the virtual machine.

Notable differences are that the order of layers is changed – now, the permutation starts with the affine layer – and that the number of rounds is further reduced: 7 rounds for both instances.

Implementation

A reference implementation is given at https://github.com/ASDiscreteMathematics/rpo/tree/master.

Vision is a family of STARK-friendly block ciphers, defined over F_(2^n), much like its direct predecessor, Jarvis. Unlike Jarvis, however, it is is defined for more than one branch. Thus, the full state can be seen as an element in (F_(2^n))^m.

Much like Jarvis, it uses both affine functions of low algebraic degree and affine functions whose inverse has a low algebraic degree – namely, B and B^(-1), where B has a low algebraic degree. Then, much like Rescue, the composition of two steps is algebraically complex, but can be modeled with a few low-degree equations in a STARK setting.

Implementation

Code to implement Vision is given in https://github.com/KULeuven-COSIC/Marvellous. Two instances are proposed by the authors: Vision Mark 1 (n = 8, m = 16) and Vision Mark II (n = 128, m = 4).

Vision Mark-32 is a sponge hash function using an instance of the Vision family of block ciphers, specifically designed to be used in Binius, a hardware-optimized SNARK defined over binary fields. In particular, compared to Vision, the number of rounds is reduced (8 rounds, each one with 2 steps) and the authors define a specific, efficient MDS matrix.

The underlying permutation used in Vision Mark-32 is defined over F_(2^32), with m=24 state elements and a capacity c=8.

Cryptanalysis

• Author: Léo Perrin
  Title: Security Analysis of XHASH8/12, 2024
  The author proposes a generalization of the FreeLunch approach and argue that both XHash8 and XHash12 are safe against such attacks under some reasonable conjecture.
• Authors: Vincent Rijmen
  Title: Cryptanalytic Audit of the XHash Sponge Function and its Components, 2024
  The author revisits the security analysis of the designers, elaborates on some details, and extends the analysis in various directions. The extended analysis mostly confirms the designers’ statements and does not lead to any new attacks.

MiMC (Minimal Multiplicative Complexity) refers to a family of ciphers and hash functions over large finite fields. Its simple – yet elegant – design has served as the inspiration of several other designs such as GMiMC and the Poseidon-family.

We give the following descriptions for a finite field GF(2^n). Note that GF(p) for an odd prime p is also allowed, and is similarly defined. Let d and n be integers such that the power function X –> X^d is a permutation over GF(2^n) (d = 3 is typically used). Let furthermore K denote a secret key and C a round constant, both elements in GF(2^n). Then the i-th round function F_{K,i}: GF(2^n) –> GF(2^n) at the core of MiMC is given by F_{K,i}(X) = (X + K + C_i)^d. The encryption function MiMC-n/n is realized by iterating this round function r times, as shown below. The number of rounds are chosen as r = Ceiling(n/log_2(d)), to avoid attacks exploiting a low algebraic degree.

A second encryption variant, Feistel-MiMC or MiMC-2n/n, uses the above function as part of a Feistel network, and the number of rounds are suggested to be r = 2*Ceiling(n/log_2(d)).

Either of the encryption variants (i.e., Feistel or non-Feistel) can be turned into a permutation by setting the secret key to 0. This permutation is then used in the sponge-framework to construct variants of the hash functions MiMChash.

Cryptanalysis

The MiMC family has been the target of significant cryptanalytic efforts since its inception. A successful attack against the Feistel-MiMC cipher was discovered by Bonnetain, who exploited a weakness in the application of a weak key-schedule used in the Feistel framework. This attack does not extend to the MiMC-n/n cipher, nor does it seem to affect the hash functions instanciated by Feistel-MiMC.

Beyond that, the initial security analysis concluded that a relatively large number of rounds was needed to provide security against attacks exploiting a low algebraic degree, such as interpolation and higher-order differential attacks. Many of the ensuing works of cryptanalysis have further explored the algebraic behaviour of MiMC-variants, particularly the MiMC-n/n cipher over binary fields. While this has led to further refinement of algebraic attacks against MiMC – even some successful “academic attacks” – their data complexities remain too large to be considered a realistic threat. We provide a non-exhaustive list of analytical works in the following.

• Author: Xavier Bonnetain
  Title: Collisions on Feistel-MiMC and univariate GMiMC, 2019
  This note shows a collision property in Feistel-MiMC that reduces key-recovery to a collision attack that can be performed in 2^{n/2} operations.
• Authors: Chaoyun Li and Bart Preneel
  Title: Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree, SAC 2019
  The authors of this work develop interpolation attacks on MiMC-n/n with low memory requirements. While this does not break the full round parameters recommended for MiMC, it disproves an interesting claim on whether the number of rounds can be reduced under realistic assumptions on available memory to an attacker.
• Authors: Maria Eichlseder, Lorenzo Grassi, Reinhard Lüftenegger, Morten Øygarden, Christian Rechberger, Markus Schofnegger, and Qingju Wang
  Title: An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC, ASIACRYPT 2020
  The paper explores distinguishers based on higher-order differentials on MiMC-n/n over binary fields. A key-recovery attack faster than brute-force is also presented, though the requirement of 2^{n-1}
  chosen ciphertext decryptions are too large for the attack to be a threat in practice. None of the results affect MiMC over prime fields.
• Authors: Clémence Bouvier, Anne Canteaut and Léo Perrin.
  Title: On the Algebraic Degree of Iterated Power Functions, Designs, Codes and Cryptography 2022.
  This article provides an extensive study of the algebraic degree growth of MiMC-n/n over binary fields. The authors derive both upper and lower bounds on this degree, providing further confidence in the security of MiMC against algebraic attacks. These results also improve upon the attacks of Eichlseder et al., particularly reducing the data complexity of the aforementioned key-recovery attack to 2^{n-4} in some cases.
• Authors: Jiamin Cui, Kai Hu, Meiqin Wang and Puwen Wei.
  Title: On the Field-Based Division Property: Applications to MiMC, Feistel MiMC and GMiMC, ASIACRYPT 2022.
  This work continues the exploration of degree growth of different MiMC variants. The paper particularly expands our understanding of Feistel-MiMC, as well as MiMC-n/n with more general exponent d, and provides improved zero-sum distinguishers for several cases in these directions.

Monolith is a family of permutations that can be used as sponge or compression functions and that are defined for prime fields Fp where p = 2^{64} – 2^{32} + 1 or p = 2^{31} – 1.

The authors propose in particular Kintsugi, a design strategy to construct nonlinear layers of high algebraic degree that allow both a fast native implementations and an efficient circuit description for ZK applications.

The names of the components of a Monolith round are inspired by those of Reinforced Concrete: Bricks (Feistel Type-3 construction with square mappings), Concrete (multiplication by a circulant MDS matrix) and Bars (layer of look-up based on the Kintsugi design strategy).

Implementation

The authors compare the performance of Monolith with other primitives for plain and in circuit implementations.

The Hades design strategy refers to an SPN construction utilizing two different round functions. It starts and ends with full rounds, R_F, which applies S-boxes along every branch as usual. The middle part consists of partial rounds, R_P, which applies S-boxes to only a limited number of branches.

HadesMiMC specifically refers to a family of keyed permutations which can be used to construct block ciphers and hash functions. It utilizes the MiMC S-box along with the Hades design strategy. The motivation of this choice is that the partial rounds allows for decreasing the number of multiplications per encrypted bit, without compromising on the algebraic degree of the primitive.

Variants of the HadesMiMC hash function, most notably Poseidon/Poseidon2, have proved particularly popular due to its efficiency in ZK settings.

Cryptanalysis

HadesMiMC and its variants – particularly the Poseidon hash functions – have received significant cryptanalytic attention. Some weak instances that were pointed out by Beyne et al., and Keller-Rosemarin have been addressed in an updated version of the HadesMiMC article on ePrint.

• Authors: Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer.
  Title: Out of Oddity – New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems, CRYPTO 2020.
  This paper describes zero-sum distinguishers of low complexity of full-round variants of the HadesMiMC permutations. Preimage attacks against some variants of Poseidon are also presented.
• Authors: Nathan Keller and Asaf Rosemarin.
  Title: Mind the Middle Layer: The HADES Design Strategy Revisited, EUROCRYPT 2021.
  This work explores the linear layers used in HadesMiMC and points to severe weaknesses if these are not chosen properly.
• Authors: Carlos Cid, Lorenzo Grassi, Aldo Gunsing, Reinhard Lüftenegger, Christian Rechberger and Markus Schofnegger.
  Title: Influence of the Linear Layer on the Algebraic Degree in SP-Networks, ToSC 2022
  This article derives improved bounds on the algebraic degree of HadesMiMC constructions, and explore the impact of the linear layer on this degree.
• Authors: Augustin Bariant, Clémence Bouvier, Gaëtan Leurent and Léo Perrin
  Title: Algebraic Attacks against Some Arithmetization-Oriented Primitives, ToSC 2022.
  This paper shows a method for bypassing two rounds in an algebraic attack on Poseidon. While this does not directly contradict the original security claim of HadesMiMC, it breaks some security claims used in the 2021-2022 ZK Hash Bounties offered by the Ethereum Foundation.
• Authors: Tomer Ashur, Thomas Buschman and Mohammad Mahzoun
  Title: Algebraic Cryptanalysis of the HADES Design Strategy: Application to Poseidon and Poseidon2, ACISP 2024.
  This paper explores Gröbner basis attacks against hash function variants of HadesMiMC (Poseidon and Poseidon2). It challenges aspects of the security arguments of HadesMiMC against these algebraic attacks, particularly in extremely high security settings (>= 384-bit security).

Implementation

Neptune is a variant of the sponge hash function Poseidon with a different non-linear layer. The main difference relies on the fact that the power map x ↦x^d is replaced by a concatenation of independent S-Boxes defined over F_p^2 via the Lai-Massey construction. For internal rounds, the non-linear layer of the remains unchanged (the power map x ↦x^d) and the matrix that instantiates the linear layer is different from the one proposed for external rounds.

Implementation

The authors observe that the multiplicative complexity of Neptune is always smaller than the one of Poseidon.

Poseidon is a family of hash functions based on the HADES design strategy over prime fields. The primitive is composed of two different types of rounds: full rounds have m S-box per round while partial rounds have only one S-box and m – 1 identity functions. The S-box is a power function x^d, where d is small.

Cryptanalysis

We refer to the cryptanalysis section on HadesMiMC which also extends to Poseidon. Note that the updated version of the Poseidon article on ePrint takes into consideration the cryptanalysis of Beyne et al., Keller-Rosemarin and Ashur-Buschman-Mahzoun.

Implementation

Poseidon2 is a more efficient version of Poseidon that has been recently proposed. While Poseidon is a sponge hash function, Poseidon2 can be either a sponge or a compression function depending on the use case.

Cryptanalysis

We refer to the cryptanalysis section on HadesMiMC which extends to Poseidon2. Note that the authors of Poseidon2 have taken these issues into consideration.

Implementation

RAIN (Random Affine Inverse Nyberg-inspired) is an MPC-friendly cipher that shows several similarities to MiMC, Jarvis and Vision. However note that RAIN is not a classical block cipher, and is only intended to be used for a MPC-in-the-Head proof system.

A way of seeing Rain is as an iteration of a larger variant of the AES S-box using a more unstructured affine mapping.

Cryptanalysis

• Authors: Fukang Liu, Mohammad Mahzoun, Morten Øygarden, Willi Meier
  Title: Algebraic Attacks on RAIN and AIM Using Equivalent Representations, ToSC 2023
  By finding an equivalent representation of 2 rounds of RAIN the authors can break 2 rounds with the 128/192/256-bit key in only 2¹¹¹/2¹⁷⁰/2²²⁵ bit operations.

Dasta is a variant of Rasta where the unique linear layers are not generated from a PRNG but rather follow a fixed schedule. This is accomplished by doing cyclic rotations on various parts of the cipher state before multiplying with a fixed matrix. The cyclic rotations depend both on block counter and round number, ensuring linear transformations do not repeat.

Cryptanalysis

• Authors: Fukang Liu, Santanu Sarkar, Willi Meier, and Takanori Isobe
  Title: Algebraic Attacks on Rasta and Dasta Using Low-Degree Equations, ASIACRYPT 2021
  Lowers security margin to one round for Rasta and Dasta, reveal that Dasta is more vulnerable to attack than Rasta.
• Authors: Lorenzo Grassi, Fukang Liu, Christian Rechberger, Fabian Schmid, Roman Walch, Qingju Wang
  Title: Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?, SAC 2024
  Studies to which extent linear transformations in Rasta-like designs need to be random before security is affected.

Implementation

The designers have implemented Dasta and compared execution time and throughput against Rasta.

Fasta is another variant of Rasta, designed to be used together with the BGV homomorphic encryption scheme. The block size is larger than in Rasta, and the block is split into five words, each corresponding to a BGV ciphertext. The unique affine transformations are designed to use only xors and cyclic rotations, which are fast operations in BGV.

Implementation

The designers have implemented Fasta, and compared the time to generate key stream under FHE encryption to Rasta.

Masta is a variant of Rasta where the plaintext and key stream elements are in a finite field F_t instead of single bits. This fits well with FHE instances where the plaintext space is larger than F_2. The block size of Masta consists of n elements of F_t, and the linear transformations are designed to be multiplications over F_{t^n}, realized as multiplication with an nxn matrix over F_t.

Cryptanalysis

• Authors: Weizhe Wang, Deng Tang
  Title: Differential Fault Attack on HE-Friendly Stream Ciphers: Masta, Pasta and Elisabeth
  Differential fault injection attack that recovers the secret key in Masta using one word of key stream and a single fault injection.
  
• Authors: Aikata Aikata, Ahaan Dabholkar, Dhiman Saha, Sujoy Sinha Roy
  Title: SASTA: Ambushing Hybrid Homomorphic Encryption with a Single Fault
  Differential fault injection attack that recovers the secret key in Masta using a single fault injection.

Implementation

The designers have implemented Masta and compared its throughput to Rasta under various parameter choices.

Pasta is a Rasta variant designed with basic plaintext elements in a finite field F_p, similar to Masta. The cipher block consists of several F_p-elements that are split into two tracks, where only the output of one track is used as key stream. Pasta uses two different non-linear operations, none of them being the Chi-transformation found in the other variants.

Cryptanalysis

• Authors: Weizhe Wang, Deng Tang
  Title: Differential Fault Attack on HE-Friendly Stream Ciphers: Masta, Pasta and Elisabeth, 2024
  Differential fault injection attack that breaks Pasta with three word-based faults injected into the encryption. The time complexity is 2^{85} or higher.
• Authors: Lorenzo Grassi, Fukang Liu, Christian Rechberger, Fabian Schmid, Roman Walch, Qingju Wang
  Title: Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?, SAC 2024
  Proposes a version of Pasta (Pasta_v2), where only the first linear transformation in the encryption algorithm is random, and all others are fixed.
• Authors: Aikata Aikata, Ahaan Dabholkar, Dhiman Saha, Sujoy Sinha Roy
  Title: SASTA: Ambushing Hybrid Homomorphic Encryption with a Single Fault, 2024
  Differential fault injection attack that recovers the secret key in Pasta by injecting a fault in one word.

Implementation

The designers have implemented Pasta in the FHE library SEAL and compared its runtime to HERA and Masta.

Rasta is a stream cipher designed to be used in the context of FHE and MPC. It is designed to have a low multiplicative depth for computing the key stream. The non-linear layer uses the Chi-transformation with multiplicative depth 1, while every linear layer is generated from a counter and only used once during key stream generation.

Cryptanalysis

• Authors: Fukang Liu, Santanu Sarkar, Willi Meier, and Takanori Isobe
  Title: Algebraic Attacks on Rasta and Dasta Using Low-Degree Equations, ASIACRYPT 2021
  Breaks 2 out of 3 versions of Agrasta, lowers security margin to one round for Rasta.
• Authors: Fukang Liu, Santanu Sarkar, Willi Meier, and Takanori Isobe
  Title: The Inverse of Chi and Its Applications to Rasta-like Ciphers, Journal of Cryptology 2022
  Gives formula for the inverse of Chi used in Rasta, leading to more exploitable equations for attacking Rasta.
• Authors: R Radheshwar, Meenakshi Kansal, Pierrick Méaux, Dibyendu Roy
  Title: Differential Fault Attack on Rasta and FiLIP_DSM, IEEE 2023
  Gives fault injection attack on Rasta, by only injecting one bit fault in the initial state.
• Authors: Lorenzo Grassi, Fukang Liu, Christian Rechberger, Fabian Schmid, Roman Walch, Qingju Wang
  Title: Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?, SAC 2024
  Studies to which extent linear transformations in Rasta-like designs need to be random before security is affected.

Implementation

The designers have implemented the homomorphic circuit of Rasta using the BGV scheme in HElib, and compared the time used to some other FHE-friendly ciphers.

Reinforced Concrete is the first design proposed for ZKP based on look-up tables. This primitive operates on three prime field elements. The authors provide in particular concrete instances for large prime fields Fp where p is the order of the curves BLS381 and BN254 (around 256 bits).

Reinforced Concrete uses three different layers: Concrete, Bricks, and Bar. The Concrete layer corresponds to the multiplication by the circulant matrix (2,1,1) and addition of constants. Then, the Bricks layer is a non-linear permutation inspired by the one used in Griffin. This layer provides security against statistical attacks. Finally, lookup tables are used for the Bar layer that is applied only once in the middle on the Reinforced Concrete permutation. This layer provides resistance of the scheme to algebraic attacks.

Implementation

The authors propose a comparison of Reinforced Concrete with other ZK-friendly primitives and with traditional ones.

Rubato is a family of noisy ciphers designed for a transciphering framework for approximate FHE. It introduces Gaussian noise to a symmetric cipher of low algebraic degree, significantly reducing the multiplicative complexity compared to existing HE-friendly ciphers, and allowing very few rounds to achieve security. As such, Rubato offers a cost-effective trade-off between Learning With Errors (LWE) encryption and conventional symmetric encryption.

Its design is similar to HERA, but differs in that while HERA operates over a field F_p for prime p, Rubato relaxes this condition to a ring Z_q for any 25- or 26-bit integer q.

Cryptanalysis

• Authors: Lorenzo Grassi, Irati Manterola Ayala, Martha Norberg Hovd, Morten Øygarden, Håvard Raddum, Qingju Wang
  Title: Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato, CRYPTO 2023
  Key recovery attack on full Rubato for at least 25% of the possible choices for q with additional experimental data. In its weakest instance, the secret key can be successfully recovered with time complexity 2^57 using less than 250.000 known key stream elements and less than 25 GB of memory

Implementation

This tweakable block cipher is intended to be easy to mask using arithmetic masking rather than Boolean masking, meaning that it is MPC-friendly.

It is a generalized Feistel network operating on four branches, each consisting of four sub-branches. Each sub-branch is then an integer modulo 127. The Feistel function is depicted in the following figure. The key material is injected into the state every four Feistel rounds, four rounds thus forming a step. Somewhat counter-intuitively, the master key is simply added into the state at the start of each step, and it is the tweak that undergoes non-trivial non-linear operations.

While Tip5 is targeting a security level of 160 bits the two variants, called Tip4 and Tip4’, achieve 128 bits of security.

Implementation

Tip5 is a hash function specifically designed to be efficient over the Goldilocks field Fp with p = 2^64 – 2^32 + 1.
The non-linear layer is composed of two types of S-boxes: S, is taken from a lookup table, and T is the classical power function x^d (here d = 7). Among the 16 branches, 4 are of the first type S, and 12 of the second type T.
The overall construction is a 5-round SPN with a circulant MDS matrix as linear layer. Note that the linear layer and the round constants are derived from the ASCII string “Tip5”.

Implementation

The authors propose a comparison with Rescue-Prime and Poseidon.