MRHS Equation Systems that can be Solved in Polynomial Time

[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.009Search in Google Scholar

[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_6Search in Google Scholar

[3] RADDUM, H.—SEMAEV, I.: Solving multiple right hand sides linear equations, Des. Codes Cryptogr. 49 (2008), 147–160.10.1007/s10623-008-9180-zSearch in Google Scholar

[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

[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

[6] SEMAEV, I.: On solving sparse algebraic equations over finite fields, Technical report, Department of Informatics, University of Bergen, 2005.Search in Google Scholar

[7] SEMAEV, I.: Improved agreeing-gluing algorithm, Math. Comput. Sci. 7 (2013), 321–339.10.1007/s11786-013-0163-8Search in Google Scholar

[8] TOVEY, C. A.: A simplified NP-complete satisfiability problem, Discrete Appl. Math. 8 (1984), 85–89.10.1016/0166-218X(84)90081-7Search in Google Scholar

[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

[10] ZAJAC, P.: Solving trivium-based Boolean equations using the method of syllogisms, Fund. Inform. 114 (2012), 359–373.Search in Google Scholar

[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-5012Search in Google Scholar

[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

[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-xSearch in Google Scholar

[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-XSearch in Google Scholar