Trapdoored Matrisler için Optimal Karışım Algoritması Bulundu

Kriptografide gizli anahtar olmadan hızlı çarpma işlemi yapılamayan psödorandom matrisler kullanılıyor. Bunlara trapdoored matrisler deniyor. Araştırıcılar, bu matrislerin transveksiyon yürüyüşü (transvection walks) yöntemiyle üretilmesi durumunda, optimal karışım zamanını matematiksel olarak belirlediler.

Transveksiyon yürüyüşü, bir matrisin satırlarına rastgele katlar ekleyerek yeni matrisler oluşturan bir işlem. Çalışma, herhangi bir matris girdisi kümesinin istatistiksel olarak rastgele hale gelmesi için gereken adım sayısını hesapladı. Sonuç: Θ(|S| + n log(n/ε)), burada |S| girdi sayısı, n matris boyutu, ε istenen yakınlık.

Bu bulgu neden önemli? Trapdoored matrisler, homomorfik şifreleme ve post-kuantum kriptografisi gibi ileri güvenlik sistemlerinin temelini oluşturuyor. Karışım zamanının optimal olduğunun kanıtlanması, bu matrislerin güvenlik garantilerini matematiksel olarak sağlamlaştırıyor. Araştırma aynı zamanda n ≥ 256 için somut sınırlar sunuyor; bu da gerçek uygulamalarda kaç adım gerektiğini gösteriyor.

Sürpriz bulgu: Satır çiftlerinin yapısına bağlı olarak da sınırların geçerli kalması, algoritmanın sağlamlığını gösteriyor. Bundan sonra trapdoored matris tasarımında bu sonuçlar referans olacak.