Paper 2014/004
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 q1$ 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.4760) 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 3MaxMinMax problem, a novel problem for hypergraphs.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 complexity theoryequation solvingcryptanalysis
 Contact author(s)
 igor @ ii uib no
 History
 20140103: received
 Short URL
 https://ia.cr/2014/004
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/004, author = {Igor Semaev}, title = {MaxMinMax problem and sparse equations over finite fields}, howpublished = {Cryptology ePrint Archive, Paper 2014/004}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/004}}, url = {https://eprint.iacr.org/2014/004} }