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.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Algebraic CryptanalysisGröbner BasisArithmetization Oriented Cipher
Contact author(s)
ferdinand @ asdm gmbh
alan @ asdm gmbh
History
Short URL
https://ia.cr/2021/870

CC BY

BibTeX

@misc{cryptoeprint:2021/870,
author = {Jan Ferdinand Sauer and Alan Szepieniec},
title = {SoK: Gröbner Basis Algorithms for Arithmetization Oriented Ciphers},
howpublished = {Cryptology ePrint Archive, Paper 2021/870},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/870}},
url = {https://eprint.iacr.org/2021/870}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.