MRHS Equation Systems that can be Solved in Polynomial Time

Pavol Zajac

doi:10.1515/tmmp-2016-0040

.blurhash-client-img { display: none !important; }

MRHS Equation Systems that can be Solved in Polynomial Time

Tatra Mountains Mathematical Publications

Volume 67 (2016): Issue 1 (September 2016)

By: Pavol Zajac

Open Access

|Feb 2017

Abstract

In this article we study the difficulty of solving Multiple Right-Hand Side (MRHS) equation systems. In the first part we show that, in general, solving MRHS systems is NP-hard. In the next part we focus on special (large) families of MRHS systems that can be solved in polynomial time with two algorithms: one based on linearisation of MRHS equations, and the second one based on decoding problems that can be solved in polynomial time.

References

[1] BERMAN, P.—KARPINSKI, M.—SCOTT, A. D.: Computational complexity of some restricted instances of 3-SAT, Discrete Appl. Math. 155 (2007), 649–653.10.1016/j.dam.2006.07.009
Search in Google Scholar Back to article
[2] DING, J.—YANG, B.-Y.: Multivariate public key cryptography, in: Post-Quantum Cryptography (D. J. Bernstein et al., eds.), Springer-Verlag, Berlin, 2009, pp. 193–241.10.1007/978-3-540-88702-7_6
Search in Google Scholar Back to article
[3] RADDUM, H.—SEMAEV, I.: Solving multiple right hand sides linear equations, Des. Codes Cryptogr. 49 (2008), 147–160.10.1007/s10623-008-9180-z
Search in Google Scholar Back to article
[4] REPKA, M.—ZAJAC, P.: Overview of the Mceliece cryptosystem and its security, Tatra Mt. Math. Publ. 60 (2014), 57–83.
Search in Google Scholar Back to article
[5] SCHILLING, T.E.—RADDUM, H.: Analysis of Trivium using compressed right hand side equations, in: Information Security and Cryptology—ICISC ’11 (H. Kim, ed.), 14th Internat. Conf., Seoul, Korea, 2011, Lecture Notes in Comput. Sci., Vol. 7259, Springer-Verlag, Berlin, 2012, pp. 18–32.
Search in Google Scholar Back to article
[6] SEMAEV, I.: On solving sparse algebraic equations over finite fields, Technical report, Department of Informatics, University of Bergen, 2005.
Search in Google Scholar Back to article
[7] SEMAEV, I.: Improved agreeing-gluing algorithm, Math. Comput. Sci. 7 (2013), 321–339.10.1007/s11786-013-0163-8
Search in Google Scholar Back to article
[8] TOVEY, C. A.: A simplified NP-complete satisfiability problem, Discrete Appl. Math. 8 (1984), 85–89.10.1016/0166-218X(84)90081-7
Search in Google Scholar Back to article
[9] ZAJAC, P.: On the use of the method of syllogisms in algebraic cryptanalysis, in: Proc. of the 1st Plenary Conf. of the NIL-I-004, University of Bergen, Norway, 2009, pp. 21–30.
Search in Google Scholar Back to article
[10] ZAJAC, P.: Solving trivium-based Boolean equations using the method of syllogisms, Fund. Inform. 114 (2012), 359–373.
Search in Google Scholar Back to article
[11] ZAJAC, P.: A new method to solve MRHS equation systems and its connection to group factorization, J. Math. Cryptol. 7 (2013), 367–381.10.1515/jmc-2013-5012
Search in Google Scholar Back to article
[12] ZAJAC, P.: Some notes on MRHS equations over GF(2) with two left-hand sides, in: Norwegain-Slovakian Workshop in Crypto, Bergen, Norway, 2016, Slovak University of Technology, Bratislava, 2016, pp. 65–70.
Search in Google Scholar Back to article
[13] ZAJAC, P.: Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity, Des. Codes Cryptogr. 2016, 1–14.10.1007/s10623-016-0256-x
Search in Google Scholar Back to article
[14] ZHAO, Y.—DENG, X.—LEE, C. H.—ZHU, H.: (2 + f(n))-SAT and its properties, Discrete Appl. Math. 136 (2004), 3–11.10.1016/S0166-218X(03)00194-X
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.1515/tmmp-2016-0040 | Journal eISSN: 1338-9750 | Journal ISSN: 1210-3195

Journal RSS Feed

Language: English

Page range: 205 - 219

Submitted on: Aug 17, 2016

Published on: Feb 25, 2017

Published by: Slovak Academy of Sciences, Mathematical Institute

In partnership with: Paradigm Publishing Services

Publication frequency: 1 issue per year

Keywords:

algebraic cryptanalysis,

MRHS equations,

NP-hard,

post-quantum cryptography

Related subjects:

Mathematics,

General mathematics

© 2017 Pavol Zajac, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 67 (2016): Issue 1 (September 2016)