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
[ Cryptology ePrint archive ]