In this paper, we propose an improved version of the Simple Matrix encryption scheme of PQCrypto2013. The main goal of our construction is to build a system with even stronger security claims. By using square matrices with random quadratic polynomials, we can claim that breaking the system using algebraic attacks is at least as hard as solving a set of random quadratic equations. Furthermore, due to the use of random polynomials in the matrix A, Rank attacks against our scheme are not feasible.