MaxMinMax problem and sparse equations over finite fields

DOI10.1007/S10623-015-0058-6MaRDI QIDQ285259zbMATH OpenOpenAlexFDO

Authors Igor Semaev

Publication date 19 May 2016

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10623-015-0058-6

zbMATH Keywords

3-setsfinite fieldsmaxminmax problemsparse equations

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

Let \(\mathbb F_q\) be the finite field with \(q\) elements and \(\mathcal X=\{ x_1, \ldots ,x_n\}\) be a set of variables. Consider a 3-sparse system of equations \[ f_1(X_1)=0, \ldots , f_m(X_m)=0, \] where each \(X_i\subset\mathcal X\), \(|X_i|\leq 3\) and the \(f_i\) are polynomials over \(\mathbb F_q\). The main result is that if \(m=n\) and the polynomials are taken independently and uniformly at random from the set of polynomials of degree \(\leq q-1\) in each variable then the average time complexity of finding all solutions in \(\mathbb F_q\) to the system has the upper bound \[ \frac{n}{q^{5.7883}}+\mathcal O(\log n). \] The underlying algorithm is the Gluing Algorithm introduced by the author in a previous paper [Des. Codes Cryptogr. 49, 47--60 (2008; Zbl 1196.11171); Math. Comput. Sci. 7, No. 3, 321--339 (2013; Zbl 1343.94080)]. This leads to needing an estimate on \[ \max_{\mathcal X}\min_{\pi}\max_{k} |\cup_{j=1}^k X_{\pi (j)}|-k, \] for permutations \(\pi\), an example of the \(\ell\)-MaxMinMax problem. The bulk of the paper consists of getting such an estimate.

Recommendations

• Sparse algebraic equations over finite fields
• Beating brute force for systems of polynomial equations over finite fields
• On solving sparse algebraic equations over finite fields
• Improved agreeing-gluing algorithm
• A combinatorial problem related to sparse systems of equations

Cites work

• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A new efficient algorithm for computing Gröbner bases (F₄)
• Algebraic Cryptanalysis of the Data Encryption Standard
• Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• scientific article; zbMATH DE number 3131972 (Why is no real title available?)
• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• Improved agreeing-gluing algorithm
• Improved randomized algorithms for 3-SAT
• Information and Communications Security
• On solving sparse algebraic equations over finite fields
• Solving multiple right hand sides linear equations
• Sparse algebraic equations over finite fields
• Speeding up deciphering by hypergraph ordering

Cited in

(6)

• On solving sparse algebraic equations over finite fields
• Speeding up deciphering by hypergraph ordering
• A combinatorial problem related to sparse systems of equations
• The minimum rank problem over finite fields
• An application of combinatorics in cryptography
• Efficient implementations of Gaussian elimination in finite fields on ASICs for MQ cryptographic systems

This page was built for publication: MaxMinMax problem and sparse equations over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285259)