Paper 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.
Metadata
- Available format(s)
-
PDF
- 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
- 2021-06-24: received
- Short URL
- https://ia.cr/2021/870
- License
-
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},
url = {https://eprint.iacr.org/2021/870}
}
