An estimator for the hardness of the MQ problem

DOI10.1007/978-3-031-17433-9_14zbMath1515.94053OpenAlexW4312767547MaRDI QIDQ6103087

Emanuele Bellini, Carlo Sanna, Rusydi H. Makarim, Javier A. Verbel

Publication date: 2 June 2023

Published in: Progress in Cryptology - AFRICACRYPT 2022 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-17433-9_14

zbMATH Keywords

estimatormultivariate cryptographyMQ problempolynomial solving

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the concrete hardness of learning with errors
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Asymptotically faster quantum algorithms to solve multivariate quadratic equations
• A survey on signature-based algorithms for computing Gröbner bases
• SOFIA: \(\mathcal{MQ}\)-based signatures in the QROM
• Solving polynomial equations. Foundations, algorithms, and applications
• On the complexity of solving quadratic Boolean systems
• Solving binary \(\mathcal {MQ}\) with Grover's algorithm
• Sigma protocols for MQ, PKP and SIS, and fishy signature schemes
• Improved cryptanalysis of UOV and Rainbow
• 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
• Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Gaussian elimination is not optimal
• A crossbred algorithm for solving Boolean polynomial systems
• Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited
• Fast Exhaustive Search for Quadratic Systems in $$\mathbb {F}_{2}$$ on FPGAs
• Post-Quantum Cryptography
• Fast Exhaustive Search for Polynomial Systems in ${\mathbb{F}_2}$
• Rainbow, a New Multivariable Polynomial Signature Scheme
• How To Prove Yourself: Practical Solutions to Identification and Signature Problems
• Unbalanced Oil and Vinegar Signature Schemes
• Beating Brute Force for Systems of Polynomial Equations over Finite Fields
• Solving Quadratic Equations with XL on Parallel Architectures
• Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations
• Syndrome Decoding Estimator
• M4GB
• Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials
• Information Security and Privacy
• Phase Transition of Multivariate Polynomial Systems
• Comparison Between XL and Gröbner Basis Algorithms

This page was built for publication: An estimator for the hardness of the MQ problem