Bu LLL’nin işi: Ona (veya kardeşlerine) çok boyutlu bir kafesin temelini verin, o daha iyi bir tane ortaya çıkaracaktır. Bu süreç kafes bazında indirgeme olarak bilinir.
Bütün bunların kriptografiyle ne ilgisi var? Bir kriptografik sistemi kırma görevinin bazı durumlarda başka bir problem olarak yeniden şekillendirilebileceği ortaya çıktı: kafeste nispeten kısa bir vektör bulmak. Ve bazen bu vektör, LLL tarzı bir algoritma tarafından oluşturulan indirgenmiş tabandan elde edilebilir. Bu strateji, araştırmacıların yüzeyde kafeslerle pek ilgisi olmayan sistemleri devirmelerine yardımcı oldu.
Teorik anlamda, orijinal LLL algoritması hızlı çalışır: Çalıştırılması için gereken süre, girdinin boyutuyla (yani kafesin boyutuyla ve kafesteki sayıların boyutuyla (bit cinsinden)) üstel olarak ölçeklenmez. temel vektörler. Ancak bir polinom fonksiyonu olarak artıyor ve Hollanda’daki ulusal araştırma enstitüsü CWI’de kriptograf olan Léo Ducas, “Eğer bunu gerçekten yapmak istiyorsanız, polinom zamanı her zaman o kadar da mümkün olmuyor” dedi.
Uygulamada bu, orijinal LLL algoritmasının çok büyük girdileri işleyemeyeceği anlamına gelir. San Diego’daki California Üniversitesi’nde doktora öğrencisi olan Keegan Ryan, “Matematikçiler ve kriptograflar daha fazlasını yapabilme becerisini istiyorlardı” dedi. Araştırmacılar, daha büyük girdilere uyum sağlamak için HBÖ tarzı algoritmaları optimize etmeye çalıştılar ve genellikle iyi performans elde ettiler. Yine de bazı görevler inatla ulaşılamaz durumda kaldı.
Ryan ve danışmanı Nadia Heninger tarafından yazılan yeni makale, HBÖ tarzı algoritmanın verimliliğini artırmak için birden fazla stratejiyi birleştiriyor. Öncelikle teknik, görevi daha küçük parçalara ayıran yinelemeli bir yapı kullanıyor. İkincisi, algoritma, hız ile doğru sonuç arasında bir denge kurarak ilgili sayıların hassasiyetini dikkatle yönetir. Yeni çalışma, araştırmacıların kafeslerin tabanlarını binlerce boyuta indirgemesini mümkün kılıyor.
Geçmişteki çalışmalar da benzer bir yaklaşımı izlemişti: 2021 tarihli bir makale, büyük kafeslerin hızlı çalışmasını sağlamak için özyineleme ve hassas yönetimi birleştiriyor, ancak yalnızca belirli kafes türleri için işe yaradı ve kriptografide önemli olanların tümü için işe yaramadı. Yeni algoritma çok daha geniş bir aralıkta iyi performans gösteriyor. PQShield şirketinde kriptografi araştırmacısı ve 2021 sürümünün yazarı Thomas Espitau, “Birinin bunu yaptığına gerçekten sevindim” dedi. Ekibinin çalışmasının bir “kavram kanıtı” sunduğunu söyledi; yeni sonuç, “çok hızlı kafes azaltmayı sağlam bir şekilde yapabileceğinizi” gösteriyor.
Yeni teknik şimdiden faydalı olmaya başladı. Fransız ulusal araştırma enstitüsü Inria’da matematikçi olan Aurel Page, kendisinin ve ekibinin bazı hesaplamalı sayı teorisi görevleri üzerinde çalışmak üzere algoritmanın bir uyarlamasını yaptığını söyledi.
LLL tarzı algoritmalar, güçlü kuantum bilgisayarların olduğu bir gelecekte bile güvende kalacak şekilde tasarlanmış kafes tabanlı kriptografi sistemleriyle ilgili araştırmalarda da rol oynayabilir. Bu tür sistemler için bir tehdit oluşturmazlar çünkü bunları kaldırmak, bu algoritmaların başarabileceğinden daha kısa vektörler bulmayı gerektirir. Ancak Bordeaux Üniversitesi’nden kriptograf Wessel van Woerden, araştırmacıların bildiği en iyi saldırıların “temel yapı taşı” olarak LLL tarzı bir algoritma kullandığını söylüyor. Bu saldırıları incelemek için yapılan pratik deneylerde, bu yapı taşı her şeyi yavaşlatabilir. Yeni aracı kullanarak araştırmacılar, saldırı algoritmaları üzerinde gerçekleştirebilecekleri deneylerin kapsamını genişletebilir ve bu algoritmaların nasıl performans gösterdiğine dair daha net bir resim sunabilir.
Orijinal hikaye izniyle yeniden basılmıştır Quanta Dergisi, editoryal açıdan bağımsız bir yayındır. Simons Vakfı Misyonu matematik, fizik ve yaşam bilimlerindeki araştırma gelişmelerini ve eğilimlerini kapsayarak halkın bilim anlayışını geliştirmektir.