Kafes Tabanlı Kriptografik Protokollerde Parametre Seçim Yöntemleri Üzerine Bir Çalışma

Abstract

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.

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.