Ünlü Şifreleme Algoritması Yükseltiliyor | Quanta Dergisi

Giderek dijitalleşen yaşamlarımızda güvenlik, kriptografiye bağlıdır. Özel bir mesaj gönderin veya çevrimiçi bir fatura ödeyin; verilerinizi gizli tutmak için tasarlanmış algoritmalara güveniyorsunuz. Doğal olarak, bazı insanlar bu sırları ortaya çıkarmak istiyor; bu nedenle araştırmacılar, akıllı bir saldırganın eline geçmeyeceklerinden emin olmak için bu sistemlerin gücünü test etmeye çalışıyor.

Bu çalışmadaki önemli araçlardan biri, adını araştırmacılardan alan LLL algoritmasıdır. yayınladı 1982'de - Arjen Lenstra, Hendrik Lenstra Jr. ve László Lovász. LLL, birçok soyundan gelenlerle birlikte, bazı durumlarda kriptografik şemaları bozabilir; nasıl davrandıklarını incelemek, araştırmacıların saldırılara karşı daha az savunmasız sistemler tasarlamasına yardımcı olur. Ve algoritmanın yetenekleri kriptografinin ötesine uzanıyor: Aynı zamanda hesaplamalı sayı teorisi gibi ileri matematik alanlarında da yararlı bir araç.

Yıllar boyunca araştırmacılar, yaklaşımı daha pratik hale getirmek için HBÖ'nün çeşitlerini geliştirdiler - ancak yalnızca bir noktaya kadar. Şimdi, bir çift kriptograf, verimlilikte önemli bir artış sağlayan yeni bir LLL tarzı algoritma geliştirdi. Kazanan yeni teknik En İyi Bildiri ödülü at 2023 Uluslararası Kriptoloji Konferansı, bilgisayar bilimcileri ve matematikçilerin yaşam boyu öğrenme benzeri yaklaşımları fizibil bir şekilde kullanabilecekleri senaryo aralığını genişletiyor.

"Gerçekten heyecan vericiydi" dedi Chris PeikertMichigan Üniversitesi'nde gazetede yer almayan bir kriptograf. Aracın onlarca yıldır çalışmanın odak noktası olduğunu söyledi. "Üzerinde bu kadar uzun süredir çalışılan bir hedefin, hâlâ bulunabilecek sürprizler olduğunu göstermesi her zaman güzeldir."

LLL tipi algoritmalar kafeslerin dünyasında çalışır: düzenli aralıklı noktaların sonsuz koleksiyonu. Bunu görselleştirmenin bir yolu olarak, bir zemini döşediğinizi hayal edin. Bunu kare fayanslarla kaplayabilirsiniz ve bu fayansların köşeleri tek bir kafes oluşturur. Alternatif olarak, farklı bir kafes oluşturmak için farklı bir döşeme şekli (örneğin, uzun bir paralelkenar) seçebilirsiniz.

Bir kafes “temeli” kullanılarak tanımlanabilir. Bu, kafesteki her noktayı elde etmek için farklı şekillerde birleştirebileceğiniz bir dizi vektördür (esasen sayı listeleri). Tabanı iki vektörden oluşan bir kafes hayal edelim: [3, 2] ve [1, 4]. Kafes, bu vektörlerin kopyalarını toplayıp çıkararak ulaşabileceğiniz tüm noktalardır.

Bu vektör çifti kafesin tek temeli değil. En az iki boyutlu her kafesin sonsuz sayıda olası tabanı vardır. Ancak tüm üsler eşit yaratılmamıştır. Vektörleri daha kısa ve birbirine dik açıya daha yakın olan bir tabanla çalışmak genellikle daha kolaydır ve bazı hesaplama problemlerinin çözümünde daha kullanışlıdır, bu nedenle araştırmacılar bu tabanları "iyi" olarak adlandırır. Bunun bir örneği aşağıdaki şekildeki mavi vektör çiftidir. Kırmızı vektörler gibi daha uzun ve daha az dik vektörlerden oluşan tabanlar "kötü" olarak değerlendirilebilir.

Bu, LLL'nin işi: Ona (veya kardeşlerine) çok boyutlu bir kafesin temelini verin, daha iyisini 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 "eğer bunu gerçekten yapmak istiyorsanız, polinom zamanı her zaman o kadar uygun olmayabilir" dedi. Leo DucasHollanda'daki ulusal araştırma enstitüsü CWI'da kriptograf olarak çalışıyor.

Pratikte bu, orijinal LLL algoritmasının çok büyük girdileri işleyemeyeceği anlamına gelir. "Matematikçiler ve kriptograflar daha fazlasını yapabilme becerisini istiyorlardı" dedi keegan ryan, San Diego'daki Kaliforniya Üniversitesi'nde doktora öğrencisi. 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ı tarafından yazılan yeni makale, Nadia Heninger, HBÖ tarzı algoritmasının verimliliğini artırmak için birden fazla stratejiyi birleştirir. Ö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ışmalarda da benzer bir yaklaşım izlendi: 2021 kağıt ayrıca büyük kafeslerin hızlı çalışmasını sağlamak için özyineleme ve hassas yönetimi birleştirir, ancak yalnızca belirli kafes türleri için işe yaradı ve kriptografide önemli olanların hepsinde işe yaramadı. Yeni algoritma çok daha geniş bir aralıkta iyi performans gösteriyor. "Birinin bunu yapmasına gerçekten sevindim" dedi Thomas EspitauPQShield şirketinde kriptografi araştırmacısı ve 2021 sürümünün yazarı. 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ı. Aurel SayfasıFransız ulusal araştırma enstitüsü Inria'dan matematikçi, kendisinin ve ekibinin bazı hesaplamalı sayı teorisi görevleri üzerinde çalışmak üzere algoritmanın bir uyarlamasını yaptığını söyledi.

HBÖ tarzı algoritmalar, tasarlanmış kafes tabanlı kriptografi sistemleriyle ilgili araştırmalarda da rol oynayabilir. güvende kal güçlü kuantum bilgisayarların olduğu bir gelecekte bile. 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 araştırmacıların bildiği en iyi saldırılar, "temel yapı taşı" olarak LLL tarzı bir algoritma kullandıklarını söylüyor Wessel van WoerdenBordeaux Üniversitesi'nde bir kriptograf. 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.

Kuantum izleyicilerimize daha iyi hizmet verebilmek için bir dizi anket yürütüyor. Bizimkini al bilgisayar bilimi okuyucu anketi ve ücretsiz kazanmak için girileceksiniz Kuantum mal.