Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinin bir çalışma alanı olan veri güvenliği konusunda kullanılan bir algoritmadır. Sıfır bilgi protokolü (zero knowledge protocol) ismi de verilir. Algoritmanın çözmeye çalıştığı problem aslında oldukça eski ve sık rastlanır bir problemdir.
“Bir bilgiyi bildiğimi, karşı tarafa bu bilgiyi vermeden nasıl ispat edebilirim?”
şeklindeki bir soruya cevap arar. Yani örneğin elimizde bir şekilde (graph) bulunan asgari tarama ağacı (minimum spanning tree) bilgisi olsun. Bu bilgiyi bildiğimizi ispat etmek istiyoruz ancak karşı tarafa da bu bilgiyi vermek istemiyoruz (Örneğin bu bilgiyi için ödeme alacağımız bir durum olabilir). Karşı taraf da kesin olarak bu bilgiyi bildiğimizden emin olmak istiyor (örneğin ödeme yapacak olsun). Bu durumda nasıl ispat yapılır?
Mağra Örneği
Problemin basit olarak anlaşılması için kullanılan mağra örneğinden yola çıkalım. A ve B kişilerinden A kişisi mağranın iki tarafını bağlayan kapının sihirli sözünü biliyor olsun (örneğin açıl susam açıl) ve bu bilgiyi B kişisine satmak istiyor olsun.
Yukarıdaki şekilde düşünülen mağra problemine göre A kişisi mağranın sağ veya sol tarafından girip diğer taraftan çıkabilmelidir.
Problemin çözümünde A kişisi mağraya girer ve kapının yanına geçer. Ardından B kişisi mağranın girişine girerek A kişisinin hangi yönden gelmesini istediğini bağırır. Şayet A kişisi doğru kelimeyi biliyorsa ve ters taraftaysa kapıyı açıp gelir. Şayet zaten istenen taraftaysa kapıyı açmasına ihtiyaç yoktur ve geri dönüp gelir.
Yukarıdaki örnekten de görüleceği üzere B kişisi %50 ihtimalle A kişisinin gizli kelimeyi bildiğinden emin olabilmektedir. Bu deney tekrarlanarak ihtimal arttırılabilir. Ancak hiçbir zaman %100 oranında emin olunması söz konusu olamaz (bilginin tamamı verilmeden).
Hamilton Döngüsü örneği
Sıfır bilgi ispatına konu olan ve üzerine düşünülen diğer bir problem de hamilton döngüsü (Hamiltonian Cycle) bilgisidir. Örneğin B kişisi şekli (graph) biliyor ancak bu şekil üzerindeki hamilton döngüsünü bilmiyor olsun. Bu bilgiyi bilen ve satmak isteyen A kişisi bu bilgiyi bildiğini nasıl ispat edebilir.
Sorunun çözümü için denkşekilli (isomoprhic , izomorfik) bir graf A kişisi tarafından oluşturulup bu şekil üzerinde bir hamilton döngüsü işaretlenir. (Tabi bu bilginin tamamı B kişisinden gizli tutuluyor)
Ardından B kişisi iki bilgiden birisini talep eder. Ya denkşekilli (isomorphic) olduğunun gösterilmesini ya da bu denkşekilli üzerinde hamilton döngüsünün gösterilmesini isteyebilir.
Sonuç
Kısacası A kişisi bilgiyi iki parçaya böler. Bu parçalar bir diğeri olmadan işe yaramaz ancak ikisi olduğunda bilginin bilindiğini ispatlayan parçalardır. Bilginin ispatlanacağı B kişisi bu bilgilerden birisini talep eder. A kişisi bu bilgilerden birisini verir ve şayet doğruysa %50 itimalle bildiğini ispatlamış olur.
Diğer bir deyişle şayet bilgiyi gerçekten bilmiyorsa %50 ihtimalle yanlış sonuç verir.
Yukarıdaki örnek bütün NP-Complete problemlere uygulanabilir.