MRHS Equation Systems that can be Solved in Polynomial Time

DOI10.1515/TMMP-2016-0040MaRDI QIDQ2970278zbMATH OpenOpenAlexFDO

Authors Pavol Zajac

Publication date 29 March 2017

Published in Tatra Mountains Mathematical Publications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/tmmp-2016-0040

zbMATH Keywords

algebraic cryptanalysisMultiple Right-Hand Side (MRHS) equation systemsNP-hardpost-quantum cryptography

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Recommendations

• On solvability of systems of polynomial equations
• Solving systems of polynomial inequalities in subexponential time
• MRHS Equation Systems
• scientific article; zbMATH DE number 4201493
• An improvement of the complexity bound for solving systems of polynomial equations
• scientific article; zbMATH DE number 5270892
• Efficient solution of real polynomial systems of equations
• Systems with parameters, or efficiently solving systems of polynomial equations 33 years later. II
• Complexity of solving parametric polynomial systems
• Solving polynomial systems equation by equation

Cites work

• A new method to solve MRHS equation systems and its connection to group factorization
• Computational complexity of some restricted instances of 3-SAT

Cited in

(4)

• A new method to solve MRHS equation systems and its connection to group factorization
• On solving sparse MRHS equations with bit-flipping
• Polynomial reduction from syndrome decoding problem to regular decoding problem
• Algebraic cryptanalysis of Ascon using MRHS equations

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: MRHS Equation Systems that can be Solved in Polynomial Time

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