Sıfır bilgi kanıtları açıklandı Bölüm 2: Etkileşimli olmayan sıfır bilgi kanıtları

Sıfır bilgi kanıt serimizin 1. bölümünde, doğrulayıcı ve kanıtlayıcı birbiriyle etkileşime girdiğinde sıfır bilgi kanıtının nasıl çalışabileceğini açıkladık.

Etkileşimli sıfır bilgi kanıtı, yalnızca doğrulayıcının, kanıtlayıcının bilgiye sahip olduğuna kesinlikle ikna olabilmesi avantajına sahiptir. Ancak bu bir dezavantaj da olabilir.

İzleyenler ve gözlemciler iddiayı doğrulayamazlarsa, kanıtlayan her doğrulayıcıyla bağımsız olarak etkileşim kurmalıdır – bu da zaman alır ve yoğun kaynak gerektirir.

Bu bölüm 2’de interaktif olmayan sıfır bilgi kanıtlarına bakacağız.

Etkileşimli olmayan sıfır bilgi kanıtları

Etkileşimli olmayan sıfır bilgi kanıtlarının nedeni, çok sayıda gözlemcinin kanıtı etkili bir şekilde doğrulamasına izin vermektir..

Sıfır bilgi kanıtlarını her zaman etkileşimli yapmamıza gerek yoktur. Genellikle kanıtın bütünlüğünü garanti eden güvenilir bir doğrulayıcı bulmak mümkündür..

Etkileşimli olmayan sıfır bilgi ispatı örneği: Sudoku ve oyun kartları

Sudoku, farklı zorluk seviyelerine sahip ancak nispeten basit kurallara sahip bir oyundur. 9 satır, 9 sütun ve 9 kesimin (kalın siyah çizgi ile gösterildiği gibi) her biri 1’den 9’a kadar her sayıyı tam olarak bir kez içermelidir.

Bir sudoku bulmacasının çözümünün özellikle zor olduğunu ve bir süper bilgisayarın bile hesaplanmasının günler sürdüğünü hayal edin.

Ama birileri (ispatcı) bulmacanın çözümüne sahip olduğunu iddia ediyor ve bir fiyata satmaya hazır. Çözümü ifşa etmeden kanıtladıklarını nasıl kanıtlayabilirler ki doğrulayıcı ödeme yapmaya hazırdır?

Kanıt:

Prover’ın toplamda 1-9—243 numaralı 27 iskambil kartına ihtiyacı var.

Şimdi, prover her kutuya doğru Sudoku çözümüne karşılık gelen sayı ile üç kart koyar. Örneğin, kutu için doğru cevap 7 ise, prover 7 değeri olan 3 oyun kartı koyacaktır..

Sudoku tablosunda, bazı cevaplar görülebilir. Bu, cevaplanan kutulara oyun kartları yerleştirilir yüz yukarı. Boş Sudoku kutularına kartlar yerleştirilir yüzü aşağı dönük.

Ön yüzü aşağı dönük kartların doğru konumda olduğunu (çözümü göstermeden) kanıtlamak için, kanıtlayıcı şunları yapmalıdır:

• Her karttan en iyi kartı alın kürek çekmek ve 9 kazık yap
• Her karttan en iyi kartı alın kolon ve 9 kazık yap
• Kalan kartları her sektör ve 9 kazık yap

Her yığın daha sonra karıştırılır ve ters çevrilir.

1-9 arasındaki her sayı, her Sudoku satırında, sütununda ve kesiminde görünmelidir. Dolayısıyla, prover kartlarının her yığını (satır, sütun ve sektör yığınlarından) 1-9 değerli her bir oyun kartını içeriyorsa, çözüme sahip olmaları gerektiğini biliyoruz.

Sıfır bilgi ispatları için başvurular

Kuşkusuz, sıfır bilgi kanıtlarının nispeten genç alanı henüz hak edebileceği kabulünü bulamamıştır. Bununla birlikte, çok değerli olduklarını kanıtlayabilirler.

Birçok matematik problemi Sudoku bulmacasına benzer (örneğin Grafik Boyama problemi). Yukarıdaki prensibi kullanabilir ve bunu çeşitli problemlere başarıyla uygulayabilirsek, hesaplama kaynaklarını ve matematiksel problemleri daha verimli bir şekilde kullanabilir ve ticaretini yapabiliriz. Veya matematiksel problemleri daha çabuk çözün.

Kudos’dan Ronen Gradwohl, Moni Naor, Benny Pinkas ve Guy Rothblum