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

Fukang Liu

Paper 2022/992

An $O (n)$ Algorithm for Coefficient Grouping

Fukang Liu, Libo Wang

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 $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},
      url = {https://eprint.iacr.org/2022/992}
}

Paper 2022/992

An O(n) Algorithm for Coefficient Grouping

Abstract

Metadata

An $O (n)$ Algorithm for Coefficient Grouping