Kuantum sonrası kriptografi
Post quantum cryptography
Yazar: VEYSEL GÜLTEKİN
Danışman: PROF. DR. ENVER ÖZDEMİR
İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilişim Uygulamaları Ana Bilim Dalı / Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilim ve Teknoloji = Science and Technology
Dizin: Kriptografi = Cryptography ; Kriptosistem = Cryptosystem ; Kuantum = Quantum

Özet:
Kuantum bilgisayarların keşfi ile klasik kriptografi olarak adlandırdığımız ve 
günümüzde tüm kriptografik cihazlarda kullanılan kriptosistemlerin güvenliği tartışılır 
hale gelmiştir. Kuantum bilgisayarlardaki hızlı gelişme sonucunda kriptografideki 
çalışma alanı kuantum bilgisayarlara karşı güvenli sistemlerin tasarlanması ve analiz 
edilmesi yönünde değişmiştir. Shor Algoritması ile çarpanlara ayırma probleminin
çözümünün üstel zamandan polinom zamana indirilmesiyle özellikle asimetrik 
kriptosistemler tehdit altına girmiştir.
Günümüzde verilerin büyük çoğunluğu klasik kriptografide kullanılan anahtar 
anlaşma algoritmaları ile paylaşılan anahtar kullanılarak simetrik şifreleme 
algoritmaları ile şifreli olarak saklanmaktadır. Kuantum kriptografinin esas etkisi 
asimetrik kriptografiye olmasına rağmen simetrik şifreleme algoritmalarının 
anahtarları asimetrik kriptografi ile paylaşıldığı için tüm veriler kuantum tehtidinden 
etkilenmektedir. Özellikle şifrelenen verilerin geriye dönük olarak tutulabileceği göz 
önünde bulundurulursa ve yakın zamanda kuantum bilgisayların çarpanlara ayırma 
problemini etkili bir şekilde çözecek seviyeye gelmesi durumunda şu andan itibaren 
simetrik şifreleme algoritmaları ile şifrelenen veriler de ileride çözülebilecektir. İmza 
algoritmalarının etkilenmesi ise imzanın kimlik doğrulama mekanizmaları veya 
mesajın kaynağını doğrulamak gibi o ana ait bir kriptografik hizmeti sağladığı için 
daha kısıtlı olacaktır. Bu yüzden kuantum tehtidi için anahtar paylaşma probleminin 
çözümü imza probleminin çözümüne nazaran daha acil bir ihtiyaç olarak görülmektedir.
Bu sebeplerle bu çalışmada kuantum sonrası kriptografinin anahtar paylaşma 
problemine getirdiği çözümler üzerinde durulacaktır. Burada bahsedilen her iki 
problem için de daha önceden AES'i blok şifreleme algoritması olarak bir yarışma 
aracılığıyla standartlaştıran NIST (Ulusal Standartlar ve Teknoloji Enstitüsü), standart 
bir algoritma seçmek için 2016 yılında bir yarışma başlatarak standart bir kuantum 
sonrası anahtar değişim algoritması ve imza algoritması seçme kararı almıştır. Bu 
süreçten sonra algoritma tasarımı ve analizi üzerine çalışmalar hızlanmıştır. 
Yarışmaya katılan algoritmalar dayandıkları zorluklara göre farklı gruplara ayrılabilir. 
Bunlar kafes tabanlı kriptosistemler, kod tabanlı kriptosistemler, isojeni tabanlı 
kriptosistemler, özet tabanlı kriptosistemler ve çok değişkenli polinom tabanlı 
kriptosistemlerdir. Bunların içinden en çok dikkat çeken ve üzerine çalışan
homomorfik şifreleme gibi yapılarda da kullanılabilmesi itibariyle kafes tabanlı 
kriptosistemlerdir. Ayrıca yarışma neticesinde standart olarak seçilen Kyber 
Algoritması da kafes tabanlı bir anahtar değişim algoritmasıdır.
Kod tabanlı kriptosistemler McEliece tarafından ortaya atılılmıştır ve asimetrik 
kriptografinin en eski problemlerinden biri olan kod çözme problemine 
dayanmaktadır. Anahtar boyutlarının büyük olması dezavantajından dolayı, kuantum 
tehditi ortaya çıkana kadar, görece az çalışılan bir alan olarak kalmıştır. 
Niederreiter kriptosisteminin ortaya çıkması ve anahtar boyutlarında iyileştirmeler yapılması ile kuantum sonrası anahtar değiştirme algoritmaları için önemli bir aday durumuna gelmişlerdir.
Izojeni tabanlı algoritmalar klasik bilgisayarlarla kırılabilen bir saldırının ortaya 
çıkmasıyla riskli duruma düşmüştür. Her ne kadar NIST SIKE anahtar anlaşma 
algoritmasını alternatif algoritma adaylarına alsa da saldırı bu tarihten sonra ortaya 
çıktığı için kullanılması önerilmez ibaresi eklemiştir. Ayrıca bazı kriptosistemlerin 
analizi için üzerine yeterince çalışılmadığı düşünüldüğü için kuantum sonrası anahtar 
anlaşma algoritmalarının tek başına kullanılmasına şüpheyle bakılmaya başlanmıştır. 
Bu sebeple anahtar paylaşım problemini çözmek için kuantum sonrası algoritmalar, 
asimetrik kriptografi ve daha önce paylaşılmış ortak simetrik anahtarlardan en az iki 
tanesini kullanan hibrit anahtar paylaşım protokolleri de önerilmiştir.
Bu çalışma kapsamında anahtar anlaşma problemini çözmek için geliştirilen 
önerilerden kabaca bahsedilecektir. Kafes tabanlı kriptosistemler ile Kod tabanlı 
kriptosistemlerin dayandıkları problemler ve bu problemler üzerine anahtar değişim 
mekanizmalarının nasıl kurulduğu anlatılacaktır. Ayrıca bazı analiz metotları 
anlatılarak standartta bulunan bazı algoritmaların güvenlik seviyeleri ve analizi 
hakkında bilgi verilecektir.

Abstract:
With the discovery of quantum computers, the security of cryptosystems, which we 
call classical cryptography and used in all cryptographic devices, has become 
controversial. As a result of the rapid development in quantum computers, the field of 
study in cryptography has changed to design and analyze systems that are secure 
against quantum computers. Asymmetric cryptosystems are especially threatened by 
reducing the factorization problem from exponential time to polynomial time with 
Shor's Algorithm.
Nowadays, most of the data is stored encrypted with symmetric encryption algorithms 
using the shared key with the key agreement algorithms used in classical cryptography.
Although the main effect of quantum cryptography is asymmetric cryptography, all 
data is affected by the quantum threat since the keys of symmetric encryption 
algorithms are shared with asymmetric cryptography. Especially considering that the 
encrypted data can be kept retrospectively, and in the near future, if quantum 
computers come to a level that can effectively solve the factorization problem, the data 
encrypted with the AES algorithm from now on will also be able to be decrypted in 
the future. If signature algorithms are affected, the retrospective effect will be more 
limited as the signature provides a current cryptographic service, such as 
authentication mechanisms or verifying the origin of the message. Therefore, the 
solution of the key sharing problem for the quantum threat is seen as a more urgent 
need than the solution of the signature problem.
For these reasons, this study will focus on the solutions brought by post-quantum 
cryptography to the key sharing problem. For both problems mentioned here, NIST 
(National Institute of Standards and Technology), which previously standardized AES 
as a block cipher algorithm through a competition, started a competition in 2016 to 
choose a post-quantum key exchange algorithm and a signature algorithm to choose a 
standard algorithm. After this process, studies on algorithm design and analysis 
accelerated. Algorithms participating in the competition can be divided into different 
groups according to the difficulties they rely on. These are lattice-based cryptosystems, 
code-based cryptosystems, isogeny-based cryptosystems, hash-based cryptosystems, 
and multivariate polynomial-based cryptosystems. Lattice-based cryptosystems are 
the most remarkable and can be used in structures such as homomorphic encryption 
that works on them. In addition, the Kyber Algorithm, which was chosen as a standard 
as a result of the competition, is a lattice-based key exchange algorithm.
Isogeny-based algorithms have become risky with the emergence of an attack that can 
be cracked by classical computers. Although NIST has taken the SIKE key agreement 
algorithm to alternative algorithm candidates, it is not recommended to use since the 
attack occurred after this date. In addition, since it is thought that some cryptosystems 
have not been studied enough for the analysis, the use of post-quantum key agreement 
algorithms alone has begun to be viewed with suspicion. For this reason, hybrid key sharing protocols, which include at least two of the options of post-quantum 
algorithms, asymmetric cryptography and previously shared common symmetric key, 
have also been proposed to solve the key sharing problem.
Within the scope of this study, the suggestions developed to solve the key agreement 
problem will be mentioned roughly. The problems of lattice-based cryptosystems and 
code-based cryptosystems and how key exchange mechanisms are built on these 
problems will be explained. In addition, some analysis methods will be explained and 
information will be given about the security levels and analysis of some algorithms in 
the standard.
The use of lattice structures in cryptosystems first started with the study of Ajtai. In 
this study, Ajtai showed the worst-to-average-case reductions for lattice problems and 
paved the way for the use of these problems in cryptosystems. Following this 
development, the first lattice-based public-key encryption algorithm emerged by Ajtai
and Dwork. With the study of Aharonov and Regev, the average-case learning with 
error problem and a public-key cryptosystem based on this problem have been 
proposed. In this cryptosystem, a structure in which 1-bit data is encrypted is shown. 
With the study of Lyubashevsky, the problem of learning with errors on the rings, 
which increases the amount of encrypted data, is introduced. With this structure, a 
mathematical structure was added to the problem of learning with errors. With the 
study of Langlois and Stehle, a module learning with error structure was introduced, 
which complicates this mathematical structure. During this study, learning with errors, 
ring learning with errors and module learning with errors will be defined.
When transforming lattice structures into cryptosystems, problems such as learning 
with errors and shortest integer solution are used. The solution of these problems is 
based on the difficulty of solving basic lattice structure problems such as the shortest 
vector problem and the closest vector problem. In this study, the difficulty of learning 
with errors for lattice-based cryptosystems will be emphasized. It will be shown how 
the learning with errors problem is reduced to the shortest vector problem. LLL and 
BKZ algorithms are used to solve the shortest vector problem in lattice structures. The 
security of the algorithm is defined over the complexity of these algorithms. For these 
reasons, we will focus on how these algorithms work.
The Kyber Algorithm is a lattice-based key encapsulation algorithm that uses the 
module learning with errors problem and is accepted as a standard by NIST. The Kyber 
Algorithm is explained in this study to be an example of lattice-based cryptosystems 
and to understand how the key encapsulation mechanism works.
Code-based cryptosystems were introduced by McEliece. It is based on the decoding 
problem, which is one of the oldest problems of asymmetric cryptography. Due to the 
disadvantage of large key sizes, it remained a relatively understudied area until the
quantum threat emerged. With the emergence of the Niederreiter cryptosystem and 
improvements in key sizes, it has become an important candidate for post-quantum 
key exchange algorithms.
It started with information set decoding attacks with Prange Algorithm at 1962, which 
is the first type of attack described in code-based cryptosystems, and many algorithms 
have been developed using this technique. However, the attack complexity could not 
be significantly reduced. Therefore, the security of code-based cryptosystems has been 
studied more than other cryptosystems and is considered to be safe. In this study, in order to better understand code-based cryptosystems, the problems on 
which code-based cryptosystems are built are explained by giving information with 
basic level error correction codes. McEliece and Niederreiter cryptosystem is 
introduced. Besides McEliece algorithm, which is selected as an alternative by NIST 
from code-based key encapsulation algorithms, is shown as an example in this study. 
By giving the definition of the algorithm, the key encapsulation process is explained 
through the algorithm.