Bazı yararlı bilgilere sahip olduğunuzu hayal edin; belki gizli bir tarif ya da bir şifrenin anahtarı. Bir arkadaşınıza bu bilgiye sahip olduğunuzu, bu konuda hiçbir şey açıklamadan kanıtlayabilir misiniz? Bilgisayar bilimcileri, sıfır bilgi kanıtı denilen yöntemi kullanırsanız bunu yapabileceğinizi 30 yıldan fazla bir süre önce kanıtladılar.
Bu fikri anlamanın basit bir yolu olarak, arkadaşınıza yol hakkında hiçbir ayrıntı vermeden bir labirentten nasıl geçileceğini bildiğinizi göstermek istediğinizi varsayalım. Arkadaşınızın izlemesi yasakken siz labirenti belirli bir süre içinde geçebiliyordunuz. (Zaman sınırı gereklidir çünkü yeterli zaman verildiğinde herkes eninde sonunda deneme yanılma yoluyla çıkış yolunu bulabilir.) Arkadaşınız bunu yapabileceğinizi bilir ama nasıl yapılacağını bilemez.
Sıfır bilgi kanıtları, gizli bilgilerle çalışan kriptografçıların yanı sıra farklı problemlerin zorluklarını sınıflandırmakla ilgilenen hesaplama karmaşıklığı araştırmacıları için de faydalıdır. "Modern kriptografinin çoğu karmaşıklık varsayımlarına dayanıyor; belirli sorunların çözülmesinin zor olduğu varsayımına dayanıyor, dolayısıyla iki dünya arasında her zaman bazı bağlantılar olmuştur" dedi. Claude CrépeauMcGill Üniversitesi'nde bilgisayar bilimcisi. “Fakat [bu] kanıtlar koca bir bağlantı dünyası yarattı.”
Sıfır bilgi kanıtları etkileşimli kanıt olarak bilinen bir kategoriye aittir, bu nedenle ilkinin nasıl çalıştığını öğrenmek ikincisini anlamaya yardımcı olur. Birinci tarif edilen bilgisayar bilimcilerinin 1985 tarihli bir makalesinde Şafi GoldwasserSilvio Micali ve Charles Rackoff'a göre, etkileşimli kanıtlar bir sorgulama gibi çalışır: Bir dizi mesaj üzerinden, bir taraf (kanıtlayan) diğerini (doğrulayanı) belirli bir ifadenin doğru olduğuna ikna etmeye çalışır. Etkileşimli bir kanıtın iki özelliği karşılaması gerekir. Birincisi, doğru bir ifade her zaman dürüst bir doğrulayıcıyı eninde sonunda ikna edecektir. İkincisi, eğer verilen ifade yanlışsa, hiçbir kanıtlayıcı -belirli bir bilgiye sahipmiş gibi davranan biri bile- ihmal edilebilecek kadar küçük bir olasılık dışında doğrulayıcıyı ikna edemez.
Etkileşimli kanıtların doğası olasılıksaldır. Kanıtlayıcı bir veya iki soruyu şans eseri doğru bir şekilde yanıtlayabilir, bu nedenle doğrulayıcının, kanıtlayıcının ifadenin doğru olduğunu gerçekten bildiğinden emin olabilmesi için yeterince fazla sayıda zorluk gerekir ve bunların hepsinin doğru olması gerekir.
Bu etkileşim fikri, Micali ve Goldwasser'in (o zamanlar Berkeley'deki California Üniversitesi'nde yüksek lisans öğrencileri) ağ üzerinden poker oynamanın lojistiği konusunda kafa yormalarıyla ortaya çıktı. Tüm oyuncular, içlerinden biri sanal desteden bir kart aldığında sonucun rastgele olduğunu nasıl doğrulayabilir? Etkileşimli kanıtlar yol gösterebilir. Peki oyuncular, yol boyunca her oyuncunun elini açığa çıkarmadan, tüm protokolün (tüm kurallar dizisinin) doğru bir şekilde takip edildiğini nasıl doğrulayabilirler?
Bu amaca ulaşmak için Micali ve Goldwasser, etkileşimli kanıt için gereken iki özelliğe üçüncü bir özelliği ekledi: Kanıt, bilginin kendisi hakkında hiçbir şeyi ortaya çıkarmamalı, yalnızca ifadenin doğruluğunu ortaya koymalıdır. Goldwasser, "Bir protokolden geçme fikri var ve bunun sonunda [poker oyuncularının] bilmeleri gerekenden daha fazlasını bilmediklerine inanıyorsunuz" dedi.
Klasik örneği ele alalım. Alice, Bob'a belirli bir grafiğin olduğunu kanıtlamak istiyor. G - kenarlarla (çizgilerle) birbirine bağlanan benzersiz bir köşe (nokta) koleksiyonu - bir "Hamilton döngüsüne" sahiptir. Bu, grafiğin her noktayı tam olarak bir kez ziyaret eden ve başladığı noktada biten bir yola sahip olduğu anlamına gelir. Alice bunu basitçe Bob'a bunu yapan yolu göstererek yapabilirdi ama o zaman elbette yolu da biliyor olacaktı.
Alice'in Bob'u böyle bir yolun var olduğunu ona göstermeden bildiğine nasıl ikna edebileceğini burada bulabilirsiniz. Önce yeni bir grafik çiziyor, H, buna benzemiyor G ancak önemli bir açıdan benzerdir: Aynı şekilde bağlanmış, aynı sayıda köşeye sahiptir. (Eğer G Gerçekten bir Hamilton döngüsü var, bu benzerlik şu anlama geliyor: H da olacak.) Ardından, her kenarı kapladıktan sonra H maskeleme bandıyla kilitliyor H bir kutuya koyar ve kutuyu Bob'a verir. Bu onun doğrudan görmesini engeller ama aynı zamanda kadının onu değiştirmesini de engeller. Sonra Bob bir seçim yapar: Ya Alice'ten bunu göstermesini isteyebilir. H gerçekten buna benzer Gveya Hamilton çevrimini kendisine göstermesini isteyebilir. H. Her iki isteğin de Alice için kolay olması gerekir; H gerçekten yeterince benzer Gve o gerçekten yolu biliyor.
Elbette Alice Hamilton çevrimini bilmese bile G, benzer olmayan grafikler çizerek Bob'u kandırmaya çalışabilir. Gveya yolunu bilmediği grafikler göndererek. Ancak birden fazla tur oynadıktan sonra Alice'in Bob'u her seferinde aldatma şansı yok denecek kadar azalıyor. Eğer her şeyi doğru yaparsa, sonunda Bob, Alice'in grafikteki Hamilton çevrimini bildiğine ikna olacaktır. GBob onu hiç görmeden.
Bu tür kanıtları ilk kez tanımlayan ilk makalenin ardından Micali ve iki matematikçi (Oded Goldreich ve Avi Wigderson) geniş kapsamlı etkilere sahip beklenmedik bir sonuç keşfettiler. NP olarak bilinen, kabaca eşit zorluktaki önemli bir sorun kategorisiyle ilgilidir. Bu sorunları çözmek zordur ancak çözümlerini doğrulamak kolaydır. Üç araştırmacı bulundu, eğer gerçekten güvenli şifreleme ise mümkünNP'deki her sorunun çözümü sıfır bilgi kanıtıyla da kanıtlanabilir. Bu çalışma araştırmacılara yardımcı oldu gebe kalmak ilk etapta güvenli şifreleme gerektirmeyen sıfır bilgi kanıtlarının çeşitleri; bunlar çoklu kanıtlayıcı etkileşimli kanıtlar olarak bilinir.
Ve 1988'de Micali ve diğerleri gösterdi eğer bir kanıtlayıcı ve bir doğrulayıcı kısa bir rastgele bit dizisini paylaşıyorsa, hiçbir etkileşime gerek yoktur. Bu teorik olarak sıfır bilgi kanıtlarının etkileşimli olması gerekmediği anlamına geliyordu; bu da iki taraf arasında sürekli iletişimin gerekli olmadığı anlamına geliyordu. Bu, onları araştırmacılar için çok daha yararlı hale getirecekti, ancak bu tür kanıtların ortaya çıkması ancak 21. yüzyılın başlarına kadar mümkün oldu.
"2000'li yılların sonlarında sıfır bilgi kanıtları oluşturmak için etkili tekniklerin gelişimini görmeye başladık" dedi. Matthew D. YeşilJohn Hopkins Üniversitesi'nde bir kriptograf. "'Bir dakika, bunu pratikte kullanmanın bir yolu olabilir' diye anladık."
Artık bir kanıtlayıcı, her ikisinin de çevrimiçi olmasına gerek kalmadan doğrulayıcıya tek bir mesaj gönderebilir ve araştırmacılar, çok karmaşık problemler için bile hızlı bir şekilde doğrulanabilecek çok kısa bir kanıt oluşturabilir. Bu, bir kripto para birimi işleminden sonra işlemin ayrıntılarını gizleyerek blok zincirini hızlı bir şekilde doğrulama yeteneği gibi çeşitli pratik kullanıma yol açmıştır. Ve 2016'da bir grup fizikçi gösterdi Sıfır bilgi kanıtları nükleer silahsızlanmaya nasıl yardımcı olabilir: Bir ülke artık nükleer savaş başlığının tasarımıyla ilgili herhangi bir sırrı açıklamadan, nükleer denetçilere savaş başlığının aktif mi yoksa pasif mi olduğunu kanıtlayabilir.
Son zamanlarda kuantum hesaplamadaki ilerlemeler, Crépeau'yu sıfır bilgi protokollerinin hala geçerli olduğundan emin olmak için geçmiş araştırmaları stres testine tabi tutmaya zorladı. 2021'de yardım etti göstermek Çok kanıtlayıcılı etkileşimli kanıtların, kuantum bilgisayarları dahil olduğunda bile gizliliğini koruduğu, ancak aynı düzeyde güvenlik elde edilmesinin protokolü çok daha yavaş hale getirdiği. Bulgunun iyi bir haber olduğunu ancak teknoloji ilerledikçe yeni endişelerin ortaya çıkacağını söyledi.
Crépeau, "Gelecekte yapabileceğimiz her tür hesaplama kuantum bilgisayarları içerecek" dedi. "Dolayısıyla iyi paranoyak kriptograflar olarak, bir sistemin güvenliğini değerlendirdiğimizde, sistemimizin güvenli olduğundan emin olmak isteriz."
Editörün notu: Shafi Goldwasser, Simons Vakfı'ndan fon aldı ve bu fon da bunu finanse ediyor editöryal olarak bağımsız yayın. Simons Vakfı finansman kararlarının kapsamımız üzerinde hiçbir etkisi yoktur.
