Solving quadratic equations with XL on parallel architectures

DOI10.1007/978-3-642-33027-8_21zbMATH Open1295.68202OpenAlexW1589365183MaRDI QIDQ4649782FDOQ4649782

Bo-Yin Yang, Tung Chou, Chen-Mou Cheng, Ruben Niederhagen

Publication date: 13 November 2012

Published in: Cryptographic Hardware and Embedded Systems – CHES 2012 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-33027-8_21

Recommendations

• Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU
• scientific article; zbMATH DE number 1962148
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• All in the XL Family: Theory and Practice
• Operating degrees for XL vs. \(F_{4}/F_{5}\) for generic \(\mathcal{M}Q\) with number of equations linear in that of variables

zbMATH Keywords

sparse solverXLmultivariate quadratic systemsblock Wiedemann algorithmGröbner basis

Mathematics Subject Classification ID

Cryptography (94A60) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Parallel algorithms in computer science (68W10)

Cited In (10)

• Worst-case subexponential attacks on PRGs of constant degree or constant locality
• Cryptanalysis of the lifted unbalanced oil vinegar signature scheme
• An improvement of algorithms to solve under-defined systems of multivariate quadratic equations
• Evaluation of Solving Time for Multivariate Quadratic Equation System Using XL Algorithm Over Small Finite Fields on GPU
• Breaking rainbow takes a weekend on a laptop
• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• Analysis of multivariate encryption schemes: application to Dob
• An estimator for the hardness of the MQ problem
• Analysis of multivariate encryption schemes: application to Dob and \(C^*\)
• Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow

This page was built for publication: Solving quadratic equations with XL on parallel architectures

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