Due to the importance of the NTRU public key cryptosystem, many improvements have been made to it by increasing security or speed to keep pace with the process of technological development in exchanging various data. In this paper, we construct a public key cryptosystem called HAQTR using non-commutative quaternion algebra with the change of the mathematical structure.