Polynomial-solving Attacks against Arithmetization-Oriented Primitives

Recent advanced protocols for zero-knowledge, multi-party computation or fast homomorphic encryption have been the subject of active research in the last decade. Many such protocols rely on symmetric cryptography primitives which are evaluated inside the protocol. The cost of these primitives depends on the operations allowed in the protocol, and these operations are often large finite field operations (+, x) . Traditional symmetric primitives such as the AES are very costly when converted into these operations, therefore dedicated primitives have been proposed; they are called Arithmetization-Oriented (AO) primitives. AO primitives tend to minimize the number of multiplication in such protocols to lower their cost, and their security is mainly evaluated with algebraic cryptanalysis. In this talk, I give an introduction to polynomial-solving attacks, a special type of algebraic attack against AO primitives. I first recall the algebraic concepts involved in the attacks, and then show the principle of polynomial-solving attacks based on Groebner bases, with application to existing AO primitives. Finally, I will go over two recent threatening polynomial-solving attacks that do not follow the usual steps of Groebner basis attacks: the FreeLunch attack (CRYPTO 2024) and the resultant attack (ASIACRYPT 2024).