On the NTRU public key cryptosystem

Abstract

Açık anahtar sistemi NTRU ilk olarak 1996 yılında tanıtıldı. Halka tabanlı bir kriptosistem olan NTRU'nun güvenliği iyi bilinen bir kafes problemi olan en kısa vektör problemine dayanır. En kısa vektör problemini yüksek boyutlu kafesler için tam olarak çözen bir algoritma yoktur. Ancak, yaklaşık sonuçlar kafes indirgeme algoritmalarıyla bulunabilir. LLL algoritması makul kısalıkta kafes vektörlerini bulan polinom zamanlı ilk algoritmadır.NTRU kriptosistemi üzerine bilinen en iyi saldırılar kafes saldırılarıdır. Bu saldırılarda gizli anahtarı bulmak için sistemin açık anahtarıyla oluşturulan kafes kullanılır. Gizli anahtarı içeren hedef vektör kafesin kısa vektörlerinden biridir. NTRU kafesine hedef vektörü bulmak için kafes indirgeme algoritması uygulanır.Bu tezde NTRU kriptosistemini ve NTRU'ya uygulanan kafes saldırılarını çalıştık ve küçük boyutlu bir NTRU kafesine saldırı uyguladık.

NTRU is a public key cryptosystem which was first introduced in 1996. It is a ring-based cryptosystem and its security relies on the complexity of a well-known lattice problem, i.e. shortest vector problem (SVP). There is no efficient algorithm known to solve SVP exactly in arbitrary high dimensional lattices. However, approximate solutions to SVP can be found by lattice reduction algorithms. LLL is the first polynomial time algorithm that finds reasonable short vectors of a lattice.The best known attacks on the NTRU cryptosystem are lattice attacks. In these attacks, the lattice constructed by the public key of the system is used to find the private key. The target vector which includes private key of the system is one of the short vectors of the NTRU lattice.In this thesis, we study NTRU cryptosystem and lattice attacks on NTRU. We applied an attack to a small dimensional NTRU lattice.