Inverting the Square systems is exponential

Jintai Ding

Paper 2011/275

Inverting the Square systems is exponential

Jintai Ding

Abstract

In this paper, we prove that the degree of regularity of the family of Square systems, an HFE type of systems, over a prime finite field of odd characteristics $q$ is exactly $q$, and therefore prove that \vskip .1in \begin{itemize} \item inverting Square systems algebraically is exponential, when $q=O(n)$, where $n$ is the number of variables of the system. \end{itemize}

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Square HFE degree of regularity
Contact author(s): jintai ding @ gmail com
History: 2011-09-30: revised; 2011-05-28: received; See all versions
Short URL: https://ia.cr/2011/275
License: CC BY

BibTeX

@misc{cryptoeprint:2011/275,
      author = {Jintai Ding},
      title = {Inverting the Square systems is exponential},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/275},
      year = {2011},
      url = {https://eprint.iacr.org/2011/275}
}