Practical complexities of probabilistic algorithms for solving Boolean polynomial systems

DOI10.1016/j.dam.2021.11.014OpenAlexW3216715219MaRDI QIDQ2065761

Carlo Sanna, Stefano Barbero, Emanuele Bellini, Javier A. Verbel

Publication date: 13 January 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.11.014

zbMATH Keywords

probabilistic algorithmimplementationpolynomial methodpractical complexityBoolean quadratic polynomial systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Boolean functions (94D10)

Related Items (1)

An estimator for the hardness of the MQ problem

Uses Software

• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On miniaturized problems in parameterized complexity theory
• Matrix multiplication via arithmetic progressions
• NP is as easy as detecting unique solutions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Complexity of problems in games, graphs and algebraic equations
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
• Solving polynomial equations. Foundations, algorithms, and applications
• On the complexity of solving quadratic Boolean systems
• Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
• Gaussian elimination is not optimal
• A crossbred algorithm for solving Boolean polynomial systems
• Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Hybrid approach for solving multivariate systems over finite fields
• Fast Exhaustive Search for Polynomial Systems in ${\mathbb{F}_2}$
• Unbalanced Oil and Vinegar Signature Schemes
• Beating Brute Force for Systems of Polynomial Equations over Finite Fields
• Membership in polynomial ideals over Q is exponential space complete
• Information Security and Privacy
• On the complexity of \(k\)-SAT

This page was built for publication: Practical complexities of probabilistic algorithms for solving Boolean polynomial systems