Çok Değişkenli Polinom Sistemlerine Dayalı Kuantum Bilgisayarlar Sonrası Güvenilir Yeni Kimlik Doğrulama ve İmzalama Şemaları

Abstract

İki taraf arasında haberleşmenin sağlıklı bir şekilde yürütülebilmesi için haberleşen tarafların kimliklerinin doğrulanması gerekmektedir. Bu bakımdan kimlik doğrulama şemaları günlük hayatımızın önemli bir parçası olmuştur. Akıllı kartlarda, uzaktan kumanda sistemlerinde kimlik doğrulama şemaları kullanılmaktadır. Günümüzde güvenilir olarak nitelendirdiğimiz açık anahtarlı kriptosistemler, klasik bilgisayarların hesaplama gücüyle polinom zamanda çözülemeyen çarpanlarına ayırma, ayrık logaritma problemleri gibi zor problemlere dayanmaktadır. Shor, 1994 yılında çarpanlarına ayırma ve ayrık logaritma problemlerini kuantum bilgisayarlarda polinom zamanda çözen algoritma önermiştir. Bundan dolayı, günümüzde kullanılan RSA, Diffie-Hellman, ECDSA gibi açık anahtarlı kriptosistemler kuantum bilgisayarlar sonrası güvensiz hale gelecektir. Bu da kuantum sonrasında kullanılabilecek güvenilir kriptosistemlere olan ihtiyacı vurgulamaktadır. Çok değişkenli polinomlara dayanan sistemler kuantum sonrasında güvenilir yapılardan ve verimlilik açısından tercih edilenlerden birisidir. Bu tez çalışmasında, kuantum bilgisayarlarda bile polinom zamanda çözülemeyecek çok değişkenli polinomlara dayanan kimlik doğrulama şemaları ve bunların üzerine inşa edilen imzalama sistemleri üzerine çalışılmıştır. Literatürde yer alan kimlik doğrulama şemalarından farklı, kes-ve-seç mantığına dayanan üç ve beş aşamalı sıfır bilgi paylaşımlı yeni kimlik doğrulama şemaları önerilmiştir. Kimlik doğrulama şemalarının verimliliği üzerine yeni ölçüt tanımı yapılmış ve varolan sistemler karşılaştırılmıştır. Son olarak, önerilen kimlik doğrulama şemasına Fiat-Shamir dönüşümü uygulanarak yeni bir imzalama algoritması oluşturulmuş ve güvenlik analizi detaylandırılmıştır. Önerilen kimlik doğrulama ve imzalama şemasının verimlilik ölçütüne göre önceki çalışmalar ile benzer durumda olduğu gösterilmiştir.

The identity of the communicating parties needs to be verified to satisfy secure the communication between the two parties. In this respect, identification schemes have become an important part of our daily life. The identification schemes are used in smart cards, remote control systems. Traditional public key cryptosystems are based on computationally hard problems in conventional computers such as factorization and discrete logarithm. In 1994, Shor proposed an algorithm to solve the factorization and the discrete logarithm problem in polynomial time by using quantum computers. Therefore, public key cryptosystems such as RSA, Diffie-Hellman, ECDSA widely used today, will become insecure after the invention of quantum computers. This emphasizes the need for secure cryptosystems that can be used in the post-quantum world. Systems based on multivariate polynomials are one of the preferred systems in terms of efficiency and secure under quantum attacks. In this thesis, identification schemes based on multivariate polynomials, which cannot be solved even in quantum computers, and signature schemes based on those have been studied on. Three and five pass new identification schemes having zero-knowledge property, different from the identification schemes in literature, are proposed by using the cut-and-choose approach. A new metric to measure the efficiency of the identification schemes is defined. Then, a comparison is provided with the previous ones. Finally, a new signature algorithm is constructed by applying the Fiat-Shamir transformation to the proposed identification scheme and the security analysis is detailed. It is shown that the proposed identification and signature scheme is similar to previous studies according to efficiency metric.