**MaxMinMax problem and sparse equations over finite fields**

*Igor Semaev*

**Abstract: **Asymptotical complexity of sparse equation systems over finite field $F_q$ is studied.
Let the variable sets belong to a fixed family $\mathcal{X}=\{X_1,\ldots,X_m\}$ while
the polynomials $f_i(X_i)$ are taken independently and uniformly at random from the set of all polynomials
of degree $\leq q-1$ in each of the
variables in $X_i$. In particular, for $|X_i|\le3$, $m=n$, we prove
the average complexity of finding all solutions to $f_i(X_i)=0, i=1,\ldots,m$ by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47--60) is at most $
q^{\frac{n}{5.7883}+O(\log n)}$ for arbitrary $\mathcal{X}$ and $q$. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.

**Category / Keywords: **complexity theory, equation solving, cryptanalysis

**Date: **received 2 Jan 2014

**Contact author: **igor at ii uib no

**Available format(s): **PDF | BibTeX Citation

**Version: **20140103:085826 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]