Connecting the Complexity of MQ- and Code-Based Cryptosystems
Author:
Open Access
- 26 September 2017
- journal article
- research article
- Published by Walter de Gruyter GmbH in Tatra Mountains Mathematical Publications
- Vol. 70 (1) , 163-177
Abstract
We study the connection between the MQ problem and the decoding problem, through the intermediate MRHS representation. The main goal of this study is to explicitly bound the complexity of solving MQ systems with decoding tools. The main observation is that although the MQ problem over GF(2) can be efficiently transformed to syndrome decoding, the existing general decoding methods are not suitable to solve the system as efficiently as expected from the MQ representation.Keywords
This publication has 8 references indexed in Scilit:
- MRHS Equation Systems that can be Solved in Polynomial TimeTatra Mountains Mathematical Publications, 2016
- Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexityDesigns, Codes and Cryptography, 2016
- A new method to solve MRHS equation systems and its connection to group factorizationJournal of Mathematical Cryptology, 2013
- On the complexity of solving quadratic Boolean systemsJournal of Complexity, 2013
- Selecting parameters for secure McEliece-based cryptosystemsInternational Journal of Information Security, 2012
- Solving Multiple Right Hand Sides linear equationsDesigns, Codes and Cryptography, 2008
- On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1)Theoretical Computer Science, 2000
- On the inherent intractability of certain coding problems (Corresp.)IEEE Transactions on Information Theory, 1978