Come posso spiegare "zero knowledge proof" a un utente finale?

Ho sentito questo esempio durante una delle lezioni degli ospiti nella mia scuola di specializzazione. Penso che sia abbastanza semplice da quando l'ho usato molte volte, per spiegare ZKP a persone con quasi Conoscenza zero di crypto / math.

Diciamo che voglio convincerti che ho un superpotere per contare il numero esatto di foglie su un albero, in pochi secondi. Voglio convincerti senza rivelare effettivamente numero esatto e senza rivelare come funziona la mia superpotenza . Posso ideare un semplice protocollo:

Chiuderò gli occhi e ti darò una scelta per tirare fuori una foglia da quell'albero. Dal momento che è solo una scelta, lo farai o non lo farai. Non ho altro modo di sapere se lo hai fatto o meno di contare rapidamente le foglie con il mio superpotere . Ora, quando guarderò l'albero, mi chiederai se lo hai effettivamente estratto oppure no.

Se ti fornisco una risposta sbagliata, saprai immediatamente che il mio superpotere è falso e quindi ne sono a conoscenza. Tuttavia, se la mia risposta è giusta, potresti pensare che sono solo fortunato. In tal caso, possiamo ripetere i passaggi precedenti. Possiamo continuare a ripetere questi passaggi fino al punto in cui sei soddisfatto del fatto che possiedo effettivamente il superpotere e che conosco il numero esatto .

La migliore dimostrazione di prove a conoscenza zero che ho trovato è "Crittografia di Kid Applied, o Come convincere i tuoi figli che non stai tradendo " di Moni Naor, Yael Naor e Omer Reingold. Esaminano un problema crittografico semplice ma reale: come convincere le persone che conosci la soluzione per un Dove è Waldo puzzle senza lasciare alcuna informazione sulla sua posizione. Come suggerisce il titolo del documento, la spiegazione mira a essere abbastanza semplice da comprendere per un bambino.

La buona risposta è questa storia: Il caso degno di nota è la metafora della "caverna di Ali Baba" usata per illustrare i meccanismi di base di una prova a conoscenza zero: il prover deve convincere il verificatore della sua conoscenza tramite un protocollo interattivo, ma allo stesso tempo uno spettatore non deve ottenere qualsiasi informazione sulla conoscenza segreta.

• Dal libro: Spiega gli algoritmi usando le metafore, Michal Forišek · Monika Steinová, 2013
• Il riferimento del libro è questo articolo per il 1990: Come spiegare i protocolli Zero-Knowledge ai tuoi figli.

Kudos sull'Rsa che mescola l'analogia. Un'ottima scoperta.

Lo zkp dipende in gran parte da un'operazione di qualche tipo, con la parte che verifica che è in grado di dettare alcuni termini che la parte avversaria può usare. Ovviamente questo dipende molto dalla domanda che viene posta in primo luogo.

La combinazione di porte segrete peggy victor non avrebbe funzionato se la domanda fosse stata formulata come Victor che voleva sapere se Peggy poteva raggiungere il lato sinistro / destro del tunnel invece di conoscere la password per passare attraverso la porta.

Quindi la domanda nella vita reale potrebbe essere riassunta per i bambini in questo modo:

Vorrei sapere se comprendi come funziona A / B / C o se sei al corrente di una conoscenza che dice che lo fai. La prova di quale potrebbe essere una qualche forma di test, che potrebbe eventualmente tradursi in una qualche forma di esposizione verbale della risposta accettata, o un'espressione fisica della conoscenza (cioè sai come funziona il motore a combustione, e sì, ecco l'appartamento 8 con due gemelli che ho fatto a mani nude con l'acciaio estratto dalle profondità di una miniera da qualche parte nelle regioni settentrionali della Russia). La cosa complicata con ZKP, e questo si estende a molte altre aree, è se al momento di produrre la dimostrazione, esso stesso rivela il modo in cui derivare la risposta.

E appare nella vita reale, che si traduce nella quantità di tempo necessario affinché la parte verificatrice effettui il reverse engineering della prova per determinare le macchinazioni all'interno. Quindi sostengo che ZKP sta anche aumentando questo tempo in una proporzione in cui non ha senso capirlo.

E con questo potresti applicarlo a un buon numero di esempi del mondo reale.

Supponiamo che ci siano due tipi di bevande che si ritiene siano largamente uguali ma in confezioni diverse. Ma A conoscere il fatto che sono uguali cerca di scoprire un test per distinguere tra i due. Il prossimo A vorrebbe convincere B che due bevande non sono uguali.

a) Un modo banale per dimostrare che sarebbe per A inviare i dettagli del suo test a B e lasciare che B esegua il test. b) Supponiamo che A non voglia divulgare nulla sul test condotto. Quindi A potrebbe ancora convincere B usando il seguente protocollo.

Va come: B prende una lattina di bevanda di ogni marca e sceglie a caso una lattina, ne versa un po '(tutto in privato) e la dà ad A. A quindi testa il campione e dice a B a quale marca appartiene il campione. Ripetono questa procedura più volte. Se A risponde correttamente ogni volta, allora B accetterà l'affermazione secondo cui le bevande non sono identiche.

In questo protocollo, in primo luogo, se le bevande sono diverse e A ha un test affidabile per distinguerle, allora A può sempre convincere B. D'altra parte, se in effetti le bevande di entrambi i barattoli sono identiche, allora A non posso distinguerli.