Sert Kafes Sorunu nedir? Bir ip 🧵

Kafes tabanlı kriptografi, merkezi bir zorluk üzerine dayanır: bir tam sayı q (genellikle asal veya asal kuvvet) modüllü doğrusal denklemler sistemine kısa bir vektör çözümü s bulmak. Buna SIS (Kısa Tamsayı Çözümü) problemi denir; biçimi basit olsa da, kuantum/klasik saldırılara karşı sert bir şekilde kabul edilir.

İki ana versiyon vardır: tek yönlü fonksiyon olarak kullanılan homojen olmayan form f_A(s) = A * s mod q, burada A * s = t (mod q) verilen A ve hedef t...

... ve homojen SIS problemi, rastgele bir matris A için A * s = 0 (mod q) olacak bir kısa s bulmayı talep eder.

Taahhüt planının SIS'in sertliği nedeniyle bağlayıcı olacağı garanti ediliyor. Eğer A * s = t = A * s' ise, A * (s - s') = 0, yani farklı bir s' bulmak sert homojen SIS problemini çözer.

S'nin (küçük norm) kısalığı esastır. S sınırlamadan, klasik lineer cebir kullanılarak çözümler önemsizdir. Bu norm kısıtlaması, SIS'in kuantum bilgisayarlara karşı bile çözülmesi zor doğasının temelini oluşturur.

Ajtai'nin 1996 sonucu, SIS probleminin sertliğini en kötü durum kafes problemlerinin çözümüne bağladı ve kuantum sonrası kriptografi varsayımları için temel oluşturdu.

SIS problemi, büyük bir gizli vektörden (boyut M) daha kısa bir taahhüt t'ye sıkıştırmayı sağlar. A matrisi boyutları N x M'dir; burada N genellikle güvenlik parametresine bağlıdır, bu da kısalık gerektiren sıfır bilgi kanıtları için cazip hale getirir.

Bir arada ele alındığında, SIS'i ifade etmek kolay ama çözülmesi son derece zordur; taahhütlerde, sıfır bilgi kanıtlarında ve daha geniş post-kuantum güvenlikte temel bir rol oynar.