Solving quadratic equations with XL on parallel architectures

DOI10.1007/978-3-642-33027-8_21MaRDI QIDQ4649782zbMATH OpenOpenAlexFDO

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

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

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)

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

Cited in

(13)

• Cryptanalysis of the lifted unbalanced oil vinegar signature scheme
• Worst-case subexponential attacks on PRGs of constant degree or constant locality
• An improvement of algorithms to solve under-defined systems of multivariate quadratic equations
• Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
• Operating degrees for XL vs. \(F_{4}/F_{5}\) for generic \(\mathcal{M}Q\) with number of equations linear in that of variables
• Breaking rainbow takes a weekend on a laptop
• Fast exhaustive search for quadratic systems in \(\mathbb {F}_2\) on FPGAs
• A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions
• Analysis of multivariate encryption schemes: application to Dob
• Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU
• 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)