Quantum-resistant multivariate quadratic systems and digital signatures

Abstract

Teknolojik gelişmeler ışığında bilim insanları, yakın gelecekte kuantum bilgisayarların üretilip klasik olanların yerini almasını, müteakiben tüm simetrik ve asimetrik (açık-anahtarlı) şifreleme sistemlerinin geçersiz olmasını bekliyorlar. Bu da kuantum-dayanıklı algoritmalara dünya çapında bir ihtiyaç doğuruyor. Bu sebeple, kuantum sonrası şifrelemenin bir türü olan çok değişkenli açık anahtarlı şifreleme sistemlerine odaklandık. Bu tür şifreleme sistemleri ardındaki ana fikri açıklamak için, başlangıç noktası olarak, Matsumoto-Imai şifreleme sistemi, doğrusallaştırma denklemleri saldırısı ile birlikte detaylı bir biçimde incelenmiştir. Akabinde, hem tek-dallı Matsumoto-Imai şifreleme sisteminin hem de onun doğrusallaştırma denklemleri saldırısının kurgusunu göstermek için kendi örneğimizi oluşturduk. Bunların yanı sıra, orijinal olanın güvenliğini artırmak amacıyla geliştirilen Matsumoto-Imai varyantları çalışılmıştır. Ardından, çok değişkenli açık anahtarlı şifreleme sistemleri ailesinden gelen ve asıl amacımız olan Çok Değişkenli İkinci Dereceden Sayısal İmza Şemasının analizine geçilmiştir. Bu süreçte onun yapısal araçları, güvenlik kaynakları, parametre setleri, genel tanımlaması, ayrıntılı tanımlaması ve güvenlik analizleri çalışılmıştır. Tüm bunların bir sonucu olarak farkettik ki, Çok Değişkenli İkinci Dereceden Sayısal İmza Şemasının, hem klasik hem de kuantum bilgisayarlara karşı güvenliği, çok değişkenli ikinci dereceden problemin zorluğuna, bu algoritmanın yapısal araçlarından olan bağlılık şemalarının güçlüğüne, standart 2n+1-geçişli kimlik saptama şemalarının özel bir türü olan ve Sakumoto-Shirai-Hiwatari 5-geçişli kimlik saptama şemasından gelen gizli anahtarı ikiye ayırma fikrine ve kimlik saptama şemasından imza şeması elde etme sürecinde güvenliği sağlayan Fiat-Shamir dönüşümüne dayalıdır. Yani, bu araçların ve fikirlerin optimize edilmiş parametre setleriyle kombinasyonunu geliştirerek daha güvenli ve etkili şifreleme protokolleri oluşturmak mümkündür.

In the light of technological advances, scientists expect that quantum computers will be generated and substitute with classical ones, then all symmetric and asymmetric (public-key) cryptosystems will be invalid in the near future. This causes the need for quantum-resistant algorithms all araund the world. That's why, we have focused on multivariate public-key cryptosystems as a kind of post-quantum cryptography. In order to explain the root idea behind this kind of cryptosystems, as a starting point, the Matsumoto-Imai cryptosystem has been scrutinised together with its linearization equations attack. After that, we have constructed our own specific toy example for illustrating the construction of both the single-branch Matsumoto-Imai cryptosystem and its linearization equations attack. As well as these, Matsumoto-Imai variants which were developed with the aim of increasing the security of original one, have been examined. Then, it has been passed on to our main aim which is the analysis of the Multivariate Quadratic Digital Signature Scheme which comes from the family of multivariate public-key cryptosystems. In this process, its structural tools, security sources, parameter sets, general description, detailed description and security analysis have been studied. As a consequence of all these, we have realized that the security of Multivariate Quadratic Digital Signature Scheme against both classical and quantum computers is based on the multivariate quadratic problem, the hardness of the commitment schemes which are the structural tools of this algorithm, the splitting idea of the secret-key that comes from the Sakumoto-Shirai-Hiwatari 5-pass Identification Scheme is a special kind of canonical 2n+1-pass identification schemes, and the Fiat-Shamir transform which maintains the security in the process of obtaining a signature scheme from an identification scheme. That is, it is possible to generate more secure and effective cryptographic protocols by improving the combination of these tools and ideas with the optimized parameter sets.