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 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.
Note: Generalize the results.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- coefficient grouping set equivalence optimization problem
- Contact author(s)
- liufukangs @ gmail com
- History
- 2022-10-03: last of 3 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}
}
