In this paper, we propose a new variant of the NTRU public key cryptosystem – the MaTRU cryptosystem. MaTRU works under the same general principles as the NTRU cryptosystem, except that it operates in a different ring with a different linear transformation for encryption and decryption. In particular, it operates in the ring of
matrices of polynomials in
− 1), whereas NTRU operates in the ring ℤ[
− 1). Note that an instance of MaTRU has the same number of bits per message as an instance of NTRU when
. The improved efficiency of the linear transformation in MaTRU leads to respectable speed improvements by a factor of
) over NTRU at the cost of a somewhat larger public key.