Paper 2022/992 Original: eprint.iacr.org/2022/992 ↗
An $\mathcal{O}(n)$ Algorithm for Coefficient Grouping
Abstract
In this note, we study a specific optimization problem arising in the recently proposed coefficient grouping technique, which is used for the algebraic degree evaluation. Specifically, we show that there exists an efficient algorithm running in time $\mathcal{O}(n)$ to solve this basic optimization problem relevant to upper bound the algebraic degree. Moreover, the main technique in this efficient algorithm can also be used to further improve the performance of the off-the-shelf solvers to solve other optimization problems in the coefficient grouping technique. We expect that some results in this note can inspire more studies on the coefficient grouping technique.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2022-10-03: last updated
- 2022-08-03: published
- Short URL
- https://ia.cr/2022/992
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2022/992,
author = {Fukang Liu},
title = {An $\mathcal{O}(n)$ Algorithm for Coefficient Grouping},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/992},
year = {2022},
url = {https://eprint.iacr.org/2022/992}
}