Cryptology ePrint Archive: Report 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}

Category / Keywords: Square, HFE, degree of regularity

Date: received 28 May 2011, last revised 30 Sep 2011

Contact author: jintai ding at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20110930:233530 (All versions of this report)

Short URL: ia.cr/2011/275