Kafes tabanlı kriptografik protokollerin verimli uygulamaları
Efficient implementations of lattice based cryptographic protocols
Yazar: BİLGE KAĞAN YAZAR
Danışman: DR. ÖĞR. ÜYESİ ERDEM ALKIM
Ondokuz Mayıs Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Taraflar arasındaki iletişimin gizliliğinin ve bütünlüğünün korunabilmesi için kriptografik sistemlere ihtiyaç bulunmaktadır. Günümüzde güvenilir olduğu düşünülen açık anahtarlı şifreleme sistemlerinin çoğu çözümlerinin zor olduğu bilinen matematik problemlerine dayanmaktadır. Bu problemlerden en çok kullanılanları çarpanlara ayırma ve ayrık logaritma problemleridir. Günümüzde kullanılan bilgisayarlar ile  bu problemlerin polinom zamanda çözülmesi çok zordur. 1994 yılında Peter Shor yaptığı bir çalışmada, çarpanlarına ayırma ve ayrık logaritma problemlerini kuantum bilgisayarlarla birlikte polinom zamanda çözebilen bir algoritma önermiştir. Bundan dolayı, günümüzde kullanılan RSA, Diffie-Hellman, ECC gibi açık anahtarlı şifeleme sistemlerinin, yeterli büyüklükte kuantum bilgisayarlar üretildiğinde güvensiz hale geleceği düşünülmektedir. Bu durum kuantum bilgisayarlar sonrasında kullanılabilecek güvenli kriptografik sistemlere ihtiyaç duyulduğunu göstermektedir. Kafes tabanlı sistemler kuantum sonrası için güvenilir yapılardan ve verimlilik açısından en çok tercih edilen sistemlerdendir. 

Bu tez çalışmasında, kuantum bilgisayarlarla bile polinom zamanda çözülemeyeceği düşünülen, kafes yapısı üzerinde tanımlanmış zor problemlerden birisi olan hatalar ile öğrenme problemi (LWE) incelenmiştir. Bu problemi kullanan anahtar kapsülleme protokolleri ve bu protokollerde kullanılmakta olan matris vektör çarpım işlemleri incelenmiştir. Bu protokoller içerisinde kullanılmakta olan matris vektör çarpım işlemleri rastgele sayı üretiminden sonra en çok zaman almakta olan kısımlardır. Bu sebeple bu çarpım işlemlerinin hızlandırılması, optimize edilmesi ve verimli bir şekilde yapılmaları gerekmektedir. Tez kapsamında LWE problemini kullanan FrodoKEM, Lizard, Emblem ve Lotus protokolleri incelenmiştir. FrodoKEM protokolü içerisindeki matris vektör çarpım işlemleri temel alınarak verimli bir matris vektör çarpım kütüphanesi oluşturulmuştur ve diğer protokollere bu çarpım işlemleri uygulanarak elde edilen sonuçlar incelenmiştir. Ek olarak protokollerin genel verimliliklerini artırmak adına uygulamalarda yapılan değişikliklerden bahsedilmiştir.

Abstract:
Cryptographic systems are needed to protect the confidentiality and integrity of communication between the parties. Most public-key cryptosystems, which are now considered to be reliable, are based on mathematical problems that are known to be difficult to solve. The most commonly used problems are factorization and discrete logarithm problems. It is hard to solve these problems in polynomial time with the computers used today. In 1994, Peter Shor proposed an algorithm that could solve the problems of factorization and discrete logarithm with quantum computers in polynomial time. Therefore, public-key cryptosystems such as RSA, Diffie-Hellman, ECC, which are used today, are thought to become insecure when sufficient size quantum computers are produced. This shows that there is a need for secure cryptographic systems that can be used after quantum computers. Lattice-based systems are the most preferred systems in terms of efficiency and reliability for post-quantum structures.

In this thesis, learning with errors (LWE) problem is examined, which is one of the difficult problems defined on the lattice structure, which is thought to be solved in polynomial time even with quantum computers. Key encapsulation protocols using this problem and matrix-vector product used in these protocols are examined. The matrix-vector multiplications used in these protocols are the ones that take the most time after random number generation. For this reason, these multiplications need to be accelerated, optimized and efficiently performed. In this thesis, FrodoKEM, Lizard, Emblem and Lotus protocols using the LWE problem are examined. An efficient matrix-vector multiplication library was created based on the matrix-vector multiplication operations within FrodoKEM protocol and the results obtained by applying these multiplication operations to other protocols were examined. Also, changes in the implementations of the protocols to increase the overall efficiency of the protocols are mentioned.