Paper 2021/870 Original: eprint.iacr.org/2021/870 ↗
SoK: Gröbner Basis Algorithms for Arithmetization Oriented Ciphers
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.
- History
- 2021-06-24: last updated
- 2021-06-24: published
- Short URL
- https://ia.cr/2021/870
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}