Tez No	İndirme	Tez Künye	Durumu
648938		Efficient implementation of lattice-based schemes / Kafes tabanlı algoritmaların verimli gerçeklenmesi Yazar:YUSUF ALPER BİLGİN Danışman: DOÇ. DR. MURAT CENK Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Uygulamalı Matematik Enstitüsü / Kriptografi Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Matematik = Mathematics Dizin:Açık anahtarlı kripto sistemler = Public key cryptosystems	Onaylandı Doktora İngilizce 2020 94 s.
Kuantum bilgisayarlar neredeyse otuz yıldır tartışılmasına rağmen bu konuda araştırmalar büyük ölçüde teoride kalmıştır. Son yıllarda, Google, IBM ve Microsoft gibi tanınmış şirketler büyük ölçekli bir kuantum bilgisayar yapabilmek için çaba sarf etmektedir. Bu bilgisayarlar ile çarpanlarına ayırma ve ayrık logaritmalar gibi zor bilinen problemler büyük ölçekli bir kuantum bilgisayar tarafından kırılabilecektir. Bu yüzden, dijital iletişimin gizliliği ve bütünlüğü ciddi biçimde tehlikeye girecektir. Büyük ölçekli kuantum bilgisayarların ne zaman yapılacağı sorusu hala açık bir sorudur. Önümüzdeki 10 yıl içinde, hâlihazırda kullanımda olan tüm açık anahtar algoritmalarını kırmak için yeterince büyük kuantum bilgisayarların inşa edileceği konusunda bazı tahminler vardır. Bu nedenle, NIST, bilgi güvenlik sistemlerimizi kuantum bilgisayarlarına karşı koruyabilmek için 2016 yılında bir standartlaştırma süreci başlatmıştır. Bu sürecin ilk iki turu tamamlanmıştır ve yedi tane aday algoritma, sekiz tane de alternatif algoritma seçilmiştir. Bu 15 algoritma içerisinden sekiz tanesi kafes tabanlıdır. Bu tez kapsamında kafes tabanlı algoritmaların verimli bir şekilde gerçeklenmesi üzerine çalışılmıştır. İlk olarak, NIST kuantum sonrası standartlaştırma süreci ikinci tur adayı olan NewHope algoritmasının hızlı ve kompakt bir varyasyonu olan NewHope-Compact algoritması önerilmiştir. Önerilen bu algoritma sayı teorik dönüşümünde (NTT) olan son gelişmeleri yoğun bir şekilde kullanmaktadır. Bunun için elemanlar arası çarpmada kullanılan her bir elemanın tanımı değiştirilmiştir. Güvenlik seviyesini değiştirmek için sadece polinom boyutunu ve eleman tanımını değiştirmenin yeterli olduğu gösterilmiştir. Daha sonra, NTT'yi kullanan kafes tabanlı algoritmalar için ARM Cortex-M4 üzerinde çeşitli optimizasyonlar sunulmuştur. Bu optimizasyonlar ile daha verimili modüler indirgeme, optimize edilmiş küçük terimli polinom çarpımı ve daha agresif NTT katmanı birleşimi kullanılarak daha hızlı bir uygulama sunulmuştur. Gerçekleştirilen bu performans optimizasyonun yanında yığın bellek kullanımı da azaltılmıştır. Bu optimizasyonlar, NIST kuantum sonrası standartlaşma sürecinde üçüntü tur adayı olan Kyber, ikinci tur adayı olan ve üçüncü turda elenen NewHope ve kendi önerdiğimiz NewHope-Compact üzerinde test edilmiştir.
Quantum computing and quantum computers have been discussed for almost three decades. However, they remain mainly in theory. Almost all big companies like Google, IBM, and Microsoft have put their effort to build the most scalable quantum computers in recent years. These computers can change the game in cryptography since the known hard problems such as integer factorization and discrete logarithms can be broken with a large-scale quantum computer. These computers would seriously jeopardize the confidentiality and integrity of all digital communications. The question of when large-scale quantum computers will be built is still an open question. There are some educated predictions that sufficiently large quantum computers will be built to break all public-key schemes currently in use within the next ten or so years. That is why the National Institute of Standards and Technology (NIST) has announced a standardization process in 2016 to prepare our information security systems to be able to resist in quantum computing. The first two rounds of this process have been completed, and there are seven on-going candidates and eight alternate candidates. Among these 15 schemes, seven of them are based on lattices. In this thesis, we study the efficient implementation of lattice-based schemes. We first propose an efficient and compact variant of NewHope, one of the most efficient second-round candidates of the NIST post-quantum standardization project. The proposed algorithm NewHope-Compact heavily uses recent advances on Number Theoretic Transform (NTT), so that transformation from one polynomial to another is easy. To make it possible, we changed the definition of a component in component-wise multiplication during polynomial multiplication and show that changing the security level only requires to change the size of the polynomial and the definition of a component. Then, we present various optimizations for lattice-based KEMs using the NTT on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of Kyber, one of the round three candidates in the NIST post-quantum project, NewHope, and NewHope-Compact.