Paper 2022/992

An $\mathcal{O}(n)$ Algorithm for Coefficient Grouping

Fukang Liu
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.