Kafes Tabanlı Yeni Anahtar Değişim Protokolleri ve Verimli Polinom Çarpımı

Abstract

Shor'un algoritmasından sonra, günümüzde kullanılan birçok asimetrik sistemin kuantum bilgisayarlara karşı güvenilir olmadığı bilinmektedir. NIST 2016 yılında kullanılan sistemlerin kuantum sonrasındaki güvenlik seviyelerini sunmuş ve yeni kriptografik sistemlere olan ihtiyacı belirtmiştir. Kafes tabanlı kriptografik sistemler, en kötü durumda kanıtlanabilir güvenlik seviyesine sahip olması, kuantum sonrasında güvenilir olması ve küçük boyutlu anahtar yapıları sayesinde asimptotik olarak verimli olması kriptografi topluluğunun ilgisini çekmektedir. Başka bir ifadeyle, bu sistemler kriptografik algoritmaların uygulanabilirliği ve verimliliği için gereken özelliklerin birçoğuna sahip bulunmaktadır. Bu kriptografik sistemler; şifreleme, elektronik imzalama ve anahtar değişimi olmak üzere üç temel işlemde kullanılmaktadır. Bu tez kapsamında, kuantum sonrasında güvenilir olduğu bilinen kafes tabanlı anahtar değişim protokolleri ve verimli uygulamalar üzerine çalışılmıştır. Polinom çarpımını klasik çarpmadan daha verimli bir şekilde gerçekleştirmek, hem kafes tabanlı hem de eliptik eğri tabanlı kriptografik uygulamaların verimliliğini arttırmayı sağlamaktadır. Bu nedenle iki polinomun çarpımında literatürde kullanılan Karatsuba-Ofman benzeri yöntemler aranmış ve üç terimli iki polinomun çarpımı için bir uygulama geliştirilmiştir. Elde edilen sonuçlar ile büyük boyutlu polinomların çarpımında genelleştirme yapmak amaçlanmıştır. Ayrıca kuantum sonrasında güvenilir kriptografik sistemlere olan ihtiyaç sebebi ile kafes tabanlı üç farklı anahtar değişim protokolü önerilmiştir. Bu protokollerden ikisi SVP probleminin zorluğuna dayanan NTRU sisteminin bir türevi olan MaTRU sistemi üzerine önerilmiştir. Diğeri zorluğu SIS problemine dayanan El-Gamal gibi maskeleme mantığıyla çalışan kafes tabanlı sistem üzerine önerilmiştir. Önerilen protokoller NTRU tabanlı anahtar değişim protokolü olan NTRU:KE ile verimlilik bakımından karşılaştırılmıştır.After Shor's algorithm, it is known that many systems used today are not reliable against quantum computers. NIST has presented post-quantum security levels for systems used in 2016, and has indicated the need for new cryptographic systems. Lattice based cryptographic systems are of interest to the cryptography community, which has proven security level in the worst case, is reliable after quantum, and asymptotically efficient due to small size key structures. In other words, these systems have many of the features needed for the applicability and efficiency of cryptographic algorithms. These cryptographic systems are used in three basic schemes: encryption, digital signature and key exchange. In this thesis, we have been working on lattice based key exchange protocols and efficient applications, which are known to be reliable after quantum computers. Performing the polynomial multiplication more efficiently than the classic multiplication, it improves the efficiency of both lattice based and elliptic curve based cryptographic applications. Therefore, Karatsuba-Ofman-like methods used in the literature in the multiplication of two polynomials were searched and an application for 3-term polynomials multiplication was developed. It is aimed to generalize the multiplication of large size polynomials by using the obtained results. In addition, three different lattice based key exchange protocols have been proposed because of the need for reliable cryptographic systems after quantum. Two of these protocols have been proposed on the MaTRU system, which is based on the difficulty of the SVP problem. The other key exchange protocol was proposed on lattice based version of discrete logarithm problem based El-Gamal public key encryption system. These protocols are compared with the proposed NTRU based key exchange protocol NTRU:KE in efficiency.