An Algebraic Cryptanalysis of the Atrapos Permutations

Bachelor's thesis by Matthijs Poppe

Abstract

Atrapos is a novel (still in development) family of cryptographic round-based permutations for use in the sponge construction. The Atrapos permutations operate natively on elements of 𝔽ₚ (where p > 2 is a prime number). Atrapos is designed to provide an efficient alternative for SHA3 as used in the post-quantum asymmetric cryptographic algorithms Kyber and Dilithium on platforms where hardware acceleration for multiplication in 𝔽ₚ is available, where either p = 3329 (for Kyber) or p = 8380417 (for Dilithium).

This thesis investigates the security of Atrapos against algebraic attacks using Gröbner basis techniques. To this end, we model the Atrapos permutations using sparse systems of polynomials. The complexity of algebraic attacks is determined by a quantity called the "ideal degree" of the ideal generated by these polynomials. We find that the top homogeneous parts of the polynomials corresponding to a single round of Atrapos form a so-called "regular sequence" of quadratic polynomials. This property allows us to compute the ideal degree for any number of rounds. Ultimately, we estimate that algebraic attacks against Atrapos require 2^{ωℓR} field operations in 𝔽ₚ (additions and multiplications), where 2 ≤ ω ≤ 3 is the matrix multiplication exponent, ℓ ≥ 3 is a quantity that depends on p, and R is the number of rounds. Based on this estimate, we determine that at least R = 4 (for Kyber) or R = 10 (for Dilithium) rounds are needed to obtain 128 bits of security against algebraic attacks. Findings from small-scale experiments are consistent with this theorized complexity.

Cite This Work

@mastersthesis{poppe-2025-atrapos,
  type   = {Bachelor's Thesis},
  author = {Poppe, Matthijs},
  title  = {An Algebraic Cryptanalysis of the {\textsc{Atrapos}} Permutations},
  year   = {2025},
  school = {Radboud University Nijmegen},
  url    = {https://mdjp.eu/bsc-thesis-atrapos},
}