Kafes tabanlı kriptografik protokollerde parametre seçim yöntemleri üzerine bir çalışma
A study on parameter selection methods for lattice-based cryptosystems
Yazar: HAMİ SATILMIŞ
Danışman: DOÇ. DR. SEDAT AKLEYLEK
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
Dizin: Açık anahtarlı kripto sistemler = Public key cryptosystems ; Bilgi güvenliği = Information security ; Kripto analiz = Cryptanalysis ; Kriptografi = Cryptography

Özet:
Shor'un algoritmasının kuantum bilgisayarlarda uygulanması ile, günümüzde
kullanılmakta olan açık anahtarlı mevcut kriptosistemlerin güvensiz olacağı
öngörülmektedir. Bu nedenden dolayı kuantum sonrası iletişim güvenliğinin
sağlanabilmesi için yeni kriptosistemlere ihtiyaç duyulmaktadır. Kuantum sonrası
güvenilir kriptosistemlerden olan ve günümüz kriptosistemleri ile benzer özellikler
göstermekte olan kafes tabanlı kriptosistemlerin güvenliği ve temeli, polinom
zamanda bile çözümü zor olan SVP ve CVP bazlı problemlere dayanmaktadır.

Bu tez çalışmasında, SVP probleminin çözümü için geliştirilen eleme algoritmaları ve
numaralandırma mantığı ile çalışan algoritmalar üzerine çalışılmıştır ve bu
algoritmaların verimli uygulamaları geliştirilmiştir. Eleme algoritmalarından
ListSieve, GaussSieve, ProGaussSieve ve HashSieve algoritmaları, yöntem, temel
işlem, çalışma zamanı ve alan karmaşıklığı özellikleri açısından irdelenmiştir. Daha
sonra, HashSieve eleme algoritması, güvenli parametre tahmin etmeye bir bakış açısı
sunmakta olan LWE-Estimator uygulamasında kullanılmıştır. LWE-Estimator
uygulamasının HashSieve algoritmasıyla verdiği çıktılar ile, kendi haliyle verdiği
çıktılar karşılaştırılmıştır. Bu tez kapsamında, literatürdeki uygulamalardan daha
verimli uygulamalar elde edebilmek amacıyla geliştirilen modüler yazılım altyapı
kütüphanesi kullanılarak, GaussSieve, ProGaussSieve ve HashSieve algoritmalarının
verimli uygulamaları gerçeklenmiştir. GaussSieve, ProGaussSieve ve HashSieve
verimli uygulamalarının çalışma süreleri ile literatürdeki uygulamaların çalışma
süreleri karşılaştırılmıştır. Son olarak, numaralandırma algoritmalarından Schnorr ve
Euchner'in numaralandırma algoritması (ENUM) ile bu algoritmayı kullanmakta olan
Schnorr ve Euchner'e ait BKZ indirgeme algoritmasının verimli uygulamaları,
modüler yazılım altyapı kütüphanesi kullanılarak geliştirilmiştir.

Abstract:
With the implementation of Shor's algorithm in quantum computers, it is clear that
widely used public key cryptosystems will be insecure. For this reason, new
cryptosystems are needed to ensure post-quantum communication security. The
security of lattice-based cryptosystems, which are post-quantum reliable
cryptosystems and show similar properties to today's cryptosystems, are based on
problems such as SVP and CVP, which are hard to solve even in polynomial time.

In this thesis, the sieving algorithms and enumeration-based running algorithms
constructed for the solution of the SVP problem are investigated and efficient
implementations of these algorithms are developed. Listsieve, GaussSieve,
ProGaussSieve, and HashSieve sieving algorithms are studied and compared in terms
of main idea, basic operation, running time and space complexity properties. Then,
HashSieve algorithm is used in the LWE-Estimator application, which provides an
overview of reliable parameter estimation. The outputs of LWE-Estimator application
using HashSieve algorithm is compared with the outputs of original LWE-Estimator.
Within the scope of this thesis, efficient implementations of GaussSieve,
ProGaussSieve and HashSieve algorithms are performed by using the modular
software infrastructure library developed to obtain more efficient implementations
from the previous ones. The running times of GaussSieve, ProGaussSieve and
HashSieve efficient implementations are compared with the running times of the
implementations in the literature. Finally, Schnorr and Euchner's enumeration
algorithm (ENUM) and efficient implementations of the BKZ reduction algorithm of
Schnorr and Euchner, which use this ENUM algorithm as a subprocessing, are
implemented using modular software infrastructure library.