Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem

DOI10.1007/978-3-030-81293-5_4MaRDI QIDQ2118526zbMATH OpenOpenAlexFDO

Authors Hiroki Furue, Shuhei Nakamura, Tsuyoshi Takagi

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-81293-5_4

zbMATH Keywords

\( \mathcal{MQ}\) problemhybrid approachmultivariate public key cryptographypost-quantum cryptographyunderdetermined system

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Symbolic computation and algebraic computation (68W30) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Cites work

• A crossbred algorithm for solving Boolean polynomial systems
• A new efficient algorithm for computing Gröbner bases (F₄)
• A polynomial-time algorithm for solving a class of underdetermined multivariate quadratic equations over fields of odd characteristics
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Analysis of QUAD
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• scientific article; zbMATH DE number 2085432 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• Hybrid approach for solving multivariate systems over finite fields
• Information and Communications Security
• On the complexity of solving quadratic Boolean systems
• Solving underdetermined systems of multivariate quadratic equations revisited
• Unbalanced Oil and Vinegar Signature Schemes

Cited in

(7)

• A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV
• An estimator for the hardness of the MQ problem
• An improvement of algorithms to solve under-defined systems of multivariate quadratic equations
• Improved cryptanalysis of SNOVA
• A simple noncommutative UOV scheme
• Just guess: improved (quantum) algorithm for the underdetermined MQ problem
• Post-quantum multivariate signature scheme QR-UOV: security, parameters, and implementations

This page was built for publication: Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem

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