Paper 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 degree evaluation. Specifically, we show that there exists an efficient algorithm running in time $\mathcal{O}(n)$ to solve a basic optimization problem relevant to upper bound the algebraic degree. We expect that some results in this note can inspire more studies on other optimization problems in the coefficient grouping technique.
Note: Significantly simply the proof of Theorem 1.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- coefficient grouping optimization problem
- Contact author(s)
- liufukangs @ gmail com
- History
- 2022-08-03: last of 2 revisions
- 2022-08-03: received
- See all versions
- Short URL
- https://ia.cr/2022/992
- License
-
CC BY
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},
note = {\url{https://eprint.iacr.org/2022/992}},
url = {https://eprint.iacr.org/2022/992}
}
