MRHS equation systems that can be solved in polynomial time

In: Tatra Mountains Mathematical Publications, vol. 67, no. 3

Pavol Zajac

Detaily:

Rok, strany: 2016, 207 - 221

Kľúčové slová:

algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography

O článku:

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.

Ako citovať:

ISO 690:

Zajac, P. 2016. MRHS equation systems that can be solved in polynomial time. In Tatra Mountains Mathematical Publications, vol. 67, no.3, pp. 207-221. 1210-3195.

APA:

Zajac, P. (2016). MRHS equation systems that can be solved in polynomial time. Tatra Mountains Mathematical Publications, 67(3), 207-221. 1210-3195.