Increasing the speed of QTRU using the Gaussian and Brent equations multiplication

摘要

The lattice based cryptography is based on the public key cryptography systems and was firstly presented by Ajatai. However, its security is related to the worst case problems. Since factorizing composite numbers in RSA and computing the discrete algorithm in the ELGamal do only require a quantum computer, the lattice based cryptography is safe and quick in regard to computations. There are two known classic problems in lattice based cryptography which includes the shortest vector problem (SVP) and the closest vector problem (CVP). The best known way for reducing lattices is the Lenstra Lenstra Lovasz (LLL). Lots of researches had been conducted in the field of lattice based cryptography and one of them is called GGH (i.e., presented by GoldReich, GoldWasser and Halevi). The other cipher, NTRU, was presented by Hoffstein, Pipher and Silverman. The GGH is based on CVP while NTRU is based on SVP and this makes the NTRU a stronger cipher. One of the developed versions of NTRU is QTRU which is based on Quaternion algebra and it is very difficult to break according to lattice reduction algorithms. The QTRU with its low dimension has the same security as NTRU in high dimensions. For key generation in QTRU we need sixteen multiplications which makes its calculations slow. By using Gaussian and Brent equations we reduce the number of multiplications into twelve. For this reason we will use Multiplicative Complexity for optimizing algebraic computations in non-commutative rings. As a result, the efficiency of QTRU has been increased in less time.