Cryptology ePrint Archive: Report 2021/870

SoK: Gröbner Basis Algorithms for Arithmetization Oriented Ciphers

Jan Ferdinand Sauer and Alan Szepieniec

Abstract: Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.

Category / Keywords: secret-key cryptography / Algebraic Cryptanalysis, Gröbner Basis, Arithmetization Oriented Cipher

Date: received 24 Jun 2021

Contact author: ferdinand at asdm gmbh, alan at asdm gmbh

Available format(s): PDF | BibTeX Citation

Version: 20210624:150955 (All versions of this report)

Short URL: ia.cr/2021/870


[ Cryptology ePrint archive ]