The algebraic FreeLunch: efficient Gröbner basis attacks against arithmetization-oriented primitives

DOI10.1007/978-3-031-68385-5_5MaRDI QIDQ6652914zbMATH OpenFDO

Authors Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum

Publication date 13 December 2024

Full work available at URL https://doi.org/10.1007/978-3-031-68385-5_5

zbMATH Keywords

\texttt{Anemoi}\texttt{Arion}\texttt{Griffin}algebraic attacksFreeLunchGröbner basissymmetric cryptanalysis

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Cryptography (94A60)

Recommendations

• Topics in Cryptology – CT-RSA 2006
• Algebraic-differential attacks on a family of arithmetization-oriented symmetric ciphers
• Algebraic attacks from a Groebner basis perspective
• Algebraic precomputations in differential and integral cryptanalysis
• Advances in Cryptology - CRYPTO 2003

Cites work

• \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption
• \texttt{Horst} meets \textit{Fluid}-SPN: Griffin for zero-knowledge applications
• A new efficient algorithm for computing Gröbner bases (F₄)
• A Zero-Dimensional Gröbner Basis for AES-128
• Algebraic cryptanalysis of STARK-friendly designs: application to MARVELlous and MiMC
• Ciphers for MPC and FHE
• Computing syzygies in finite dimension using fast linear algebra
• Cryptanalysis of \texttt{Elisabeth-4}
• Cryptanalysis of the FLIP family of stream ciphers
• Effective and efficient masking with low noise using small-Mersenne-prime ciphers
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 2151192 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants
• MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity
• New design techniques for efficient arithmetization-oriented hash functions: \texttt{Anemoi} permutations and \texttt{Jive} compression mode
• On fast multiplication of polynomials over arbitrary algebras
• Rasta: a cipher with low ANDdepth and few ANDs per bit
• Sparse FGLM algorithms
• Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression
• Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression
• Sub-cubic change of ordering for Gröbner basis: a probabilistic approach
• Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations
• The Magma algebra system. I: The user language
• Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher
• Towards stream ciphers for efficient FHE with low-noise ciphertexts

Cited in

(6)

• Algebraic-differential attacks on a family of arithmetization-oriented symmetric ciphers
• Improved resultant attack against arithmetization-oriented primitives
• Gröbner basis cryptanalysis of Anemoi
• The XHash family for ZK-friendly hash functions
• Magic pot: cryptanalysis of full AIM2 in the standard and related-/reused-key settings using new elimination framework
• A semi-analytical method for solving inverse kinematics of 6R robotic arms with subparallel axes

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: The algebraic FreeLunch: efficient Gröbner basis attacks against arithmetization-oriented primitives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6652914)