KEY AGREEMENT PROTOCOL OVER THE RING OF MULTIVARIATE POLYNOMIALS

Abstract

The key agreement protocol (KAP) using matrices over the ring of multivariate polynomials is presented. The compromisation of proposed KAP relies on the solution of multivariate quadratic (MQ) system of equations problem – the problem, which is reckoned as being NP-complete. The general method of solving MQ problem is Grobner basis algorithm, which is of exponential or even double exponential time in general case. For special cases such as overdefined and sparse systems, there are some special solution methods, i.e. XL and XSL algorithms. By choosing suitable security parameters for the compromisation of the proposed KAP, we obtained a random not overdefined and not sparse system of MQ equations and hence we recon that our KAP compromasation relies on the hard MQ problem.