A crossbred algorithm for solving Boolean polynomial systems

DOI10.1007/978-3-319-76620-1_1MaRDI QIDQ2636455zbMATH OpenOpenAlexFDO

Authors Vanessa Vitse, Antoine Joux

Publication date 5 June 2018

Full work available at URL https://doi.org/10.1007/978-3-319-76620-1_1

zbMATH Keywords

algebraic cryptanalysismultivariate cryptographymultivariate polynomial systemsXLGröbner basis

Mathematics Subject Classification ID

Cryptography (94A60) Fuzzy sets and logic (in connection with information, communication, or circuits theory) (94D05) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Recommendations

• On the complexity of solving quadratic Boolean systems
• Boolean ring cryptographic equation solving
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
• On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables

Cited in

(28)

• On the complexity of solving quadratic Boolean systems
• Admissible parameters for the crossbred algorithm and semi-regular sequences over finite fields
• SoK: how (not) to design and implement post-quantum cryptography
• Preimage attacks on 4-round Keccak by solving multivariate quadratic systems
• Boolean ring cryptographic equation solving
• A multivariate cryptosystem inspired by random linear codes
• A rank attack against extension field cancellation
• On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables
• Rare structures in tensor graphs. Bermuda triangles for cryptosystems based on the tensor isomorphism problem
• The use of associative information processing for constructing algorithms for solving systems of Boolean equations
• Integrating algebraic and SAT solvers
• Logical cryptanalysis with WDSat
• Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem
• Sigma protocols for MQ, PKP and SIS, and fishy signature schemes
• A new method for solving polynomial systems with noise over \(\mathbb{F}_2\) and its applications in cold boot key recovery
• On the efficiency of solving Boolean polynomial systems with the characteristic set method
• Polynomial XL: a variant of the XL algorithm using Macaulay matrices over polynomial rings
• Algorithm 1052: evaluating a Boolean polynomial on all possible inputs
• A hybrid algorithm for the regular syndrome decoding problem
• Fast exhaustive search for quadratic systems in \(\mathbb {F}_2\) on FPGAs
• Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
• Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
• A SAT-Based Approach for Index Calculus on Binary Elliptic Curves
• Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields
• An estimator for the hardness of the MQ problem
• Internal differential structure: preimage attacks on up to 5-round Keccak
• Solving non-linear Boolean equation systems by variable elimination
• The number of steps for construction of a Boolean solution to polynomial congruences and systems of polynomial congruences

This page was built for publication: A crossbred algorithm for solving Boolean polynomial systems

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