Odczuwam pewien zaledwie minimalny opór przed napisaniem kilku słów na temat, który interesuje pewnie tylko mnie oraz nieliczną grupkę leworęcznych matematyków z syndromem Apergera. Jest niedziela wcześnie rano, Kraków śpi, nad Salwatorem lekka mgiełka a ja zastanawiam się nad następującym problemem. Czy jest możliwe by przekonać kogoś, że dysponuje się pewną informacją bez jej ujawniania? Wyobraź sobie, że znasz pewien sekret i chcesz kogoś przekonać, że go znasz bez ujawniania nawet ułamka jego treści. Odruchowa odpowiedź brzmi „nie!”, więc rzecz jest ciekawa. Pytanie to wydaje mi się absolutnie fascynujące zarówno z powodów praktycznych jak i filozoficznych.

Masz więc dwie niemalże identyczne piłki, które nie różnią się rozmiarem, wagą oraz są identyczne w dotyku. Jedna jest jednak czerwona a druga zielona. To nic nie szkodzi bo partner Twojej zabawy jest kompletnym daltonistą i postrzega je identycznie mimo tej jedynej różnicy kolorystycznej. Posiadasz więc pewną tajemnicę, której on nie zna. Chcesz go przekonać, że piłki różnią się kolorem nie ujawniając która jest jaka. Piłki łatwo mieszczą się w dłoni i można obie schować za plecami. Dajesz więc zieloną piłkę do lewej ręki daltonisty i czerwoną do prawej. Informujesz go, że może za plecami zamienić je miejscami i następnie je pokazać. On na prawdę postrzega je identycznie. Dlatego, z jego punktu widzenia, schowanie piłek jest konieczne. Pokazując piłki daltonista pyta Cię czy zamienił piłki miejscami. Jeśli w kilkunastu próbach  udzielasz poprawnej odpowiedzi to daltonista przekona się, że piłki są różnych kolorów ale nadal nie wie która jest jaka. Fantastyczne! Nieprawdaż? Pewność zbliża się do jedynki wraz z liczbą  n prób jak 1 – (1/2)^n.

Jest to tzw. „dowód z zerową wiedzą” – przykład procedury kryptograficznej w której jedna ze stron potrafi udowodnić drugiej, że dysponuje pewną informacją, bez ujawniania nawet fragmentu jej treści. Dowód nie jest dowodem w tradycyjnym sensie matematycznym lecz probabilistycznym. Zwiększając tak jak wyżej liczbę  prób można dowolnie zbliżyć się do prawdopodobieństwa równego jeden. Ten dział matematyki rozwinął się w ostatnich kilku latach. Pierwsze przełomowe prace ukazały się w latach 90-tych ubiegłego wieku i ich autorzy (między innymi węgierski geniusz László Babai) zostali wyróżnieni nagroda Godela. Prace dotyczyły pewnych cech izomorfizmów grafów.

Skoro piszę o tym w niedzielę o świcie to znaczy, że jakoś istotnie to mną wstrząsnęło. Tak – zdaje się, że  dowodzenie z zerową wiedzą ma głębokie implikacje epistemologiczne i nie tylko. Jeśli ktoś wiele razy z rzędu robi niesamowity „trick”, którego nie rozumiesz (niczym ten daltonista) to dowodzi, że posiada on jakąś brakującą Ci informacje. Teraz, nie przekazując dodatkowych informacji, błyskotliwy Czytelnik łatwo się domyśli dlaczego ten tekst umieściłem w dziale bloga poświęconym buddyzmowi. Czego wszystkim i sobie życzę!