nessuna prova di conoscenza e il suo protocollo

Question

nessuna prova di conoscenza e il suo protocollo

#1 da (8 voti)
#2 da (7 voti)
#3 da (2 voti)

8

In Zero-Knowledge Proof dove prendiamo l'analogia di Peggy (Prover) e Victor (Verifier):

In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a circle, with the entrance on one side and the magic door blocking the opposite side. Victor says he'll pay her for the secret, but not until he's sure that she really knows it. Peggy says she'll tell him the secret, but not until she receives the money. They devise a scheme by which Peggy can prove that she knows the word without telling it to Victor.

First, Victor waits outside the cave as Peggy goes in. They label the left and right paths from the entrance A and B. Peggy randomly takes either path A or B. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. Note that Victor does not know which path she has gone down.

However, suppose she did not know the word. Then, she would only be able to return by the named path if Victor were to give the name of the same path that she had entered by. Since Victor would choose A or B at random, he would have a 50% chance of guessing correctly. If they were to repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests would become vanishingly small. Thus, if Peggy reliably appears at the exit Victor names, he can conclude that she is very likely to know the secret word.

Il seguente metodo di verifica è abbastanza convincente per me:

Victor attraversa entrambi i corridoi A e B e si assicura che non c'è modo di andare dall'altra parte (poiché Victor non sa nulla di segreto, è convinto che sia vero).
Potrebbe andare all'ingresso del corridoio A, chiedere a Peggy di attraversare l'ingresso B e arrivare dalla fine di A. (Peggy fa, e viene fuori dalla fine di A)
Victor procederà anche nella direzione opposta a quella in cui si trova all'ingresso di B e chiederà a Peggy di venire alla fine di B dopo aver attraversato A.
Se Peggy poteva fare sia il 2 che il 3, Victor è convinto che Peggy conosca il segreto.

Sento che questo metodo è sbagliato e mi chiedo perché. Quindi, perché dovrebbe essere preferito il metodo classico? Quali sono i punti deboli di questo metodo?

authentication cryptography

posta vaasu 02.07.2011 - 17:47

fonte

3 risposte

Leggi altre domande sui tag authentication cryptography

Attacchi di sicurezza su applicazioni Web PHP Servizi di sicurezza su Edge Router e Firewall standard

score 8 · Answer 1

La discussione su Wikipedia collegata a Kerrek SB è vicina ma forse non del tutto chiara.

Diciamo che Peggy riesce a convincere Victor che lei conosce il segreto. Victor può convincerti che Peggy conosce il segreto? In una prova a conoscenza zero, la risposta dovrebbe essere no. Victor non solo ottiene la conoscenza "zero" del segreto in sé, ma anche nessuna conoscenza trasferibile su chi conosce il segreto.

Come menzionato nel link, considera lo scenario in cui Victor registra la sessione per te. Nel primo protocollo, la videocassetta potrebbe essere falsificata semplicemente avendo Victor e Peggy d'accordo sulle "casuali" sfide che Victor darà a Peggy in anticipo. Dal momento che non hai modo di sapere se Victor ha detto o meno a Peggy le sfide, la videocassetta è in realtà priva di valore e non ti convince di nulla.

Tuttavia, nel tuo protocollo modificato, una videocassetta sarebbe convincente. Quindi perde più della conoscenza "zero". Ora avere la capacità di trasferire conoscenza non è sempre male! In alcune applicazioni, si desidera utilizzare qualcosa che sia a zero conoscenza a tutti gli effetti, tranne per il fatto che è possibile trasferire conoscenze (queste sono chiamate prove di conoscenza zero non interattive).

I commenti su Wikipedia passano quindi a trattare con un verificatore che è disonesto (cioè se Victor può dimostrare di aver generato la sua sfida dopo che Peggy è già in uno dei percorsi, magari lanciando la moneta sul video) e mantenendo zero -conoscere con blackbox riavvolgibile l'accesso al verificatore (che è dove l'analogia si rompe un po '). Tuttavia non è necessario considerare il caso disonesto per distinguere tra i due protocolli nel post originale.

score 7 · Answer 2

Il problema è che l'analogia con le caverne non può essere spinta così lontano. C'è una discussione su quella domanda esatta , dai un'occhiata. La parte "zero knowledge" richiede che la dimostrazione non possa essere distinta da una simulazione da parte di un verificatore fraudolento.

score 2 · Answer 3

Prendendo l'analogia per quanto è semplice, non sa quale percorso abbia la porta magica e quale sia la password. Oh, e gli è permesso solo di prendere una strada fino alla fine. Quindi non può ancora passare.

Ok, è un'allineamento sull'analogia, quello che ho sentito, ci sono due porte magiche e Alice conosce il passaggio per entrambi che hanno password diverse, questo è più vicino all'algoritmo vero e fa l'analogia molto di più senso. Questo, naturalmente, mi dà un'idea per un puzzle labirinto di cristalli in cui fondamentalmente devono risolverlo con questa analogia.