Abstract examples Zero-knowledge proof

the ali baba cave

there well-known story presenting fundamental ideas of zero-knowledge proofs, first published jean-jacques quisquater , others in paper how explain zero-knowledge protocols children . common practice (see alice , bob) label 2 parties in zero-knowledge proof peggy (the prover of statement) , victor (the verifier of statement).

in story, peggy has uncovered secret word used open magic door in cave. cave shaped ring, entrance on 1 side , magic door blocking opposite side. victor wants know whether peggy knows secret word; peggy, being private person, not want reveal knowledge (the secret word) victor or reveal fact of knowledge world in general.

they label left , right paths entrance , b. first, victor waits outside cave peggy goes in. peggy takes either path or b; victor not allowed see path takes. then, victor enters cave , shouts name of path wants use return, either or b, chosen @ random. providing know magic word, easy: opens door, if necessary, , returns along desired path.

however, suppose did not know word. then, able return named path if victor give name of same path had entered. since victor choose or b @ random, have 50% chance of guessing correctly. if repeat trick many times, 20 times in row, chance of anticipating of victor s requests become vanishingly small (about 1 in million).

thus, if peggy repeatedly appears @ exit victor names, can conclude probable—astronomically probable—that peggy in fact know secret word.

one side note respect third-party observers: if victor wearing hidden camera records whole transaction, thing camera record in 1 case victor shouting a! , peggy appearing @ or in other case victor shouting b! , peggy appearing @ b. recording of type trivial 2 people fake (requiring peggy , victor agree beforehand on sequence of s , b s victor shout). such recording never convincing original participants. in fact, person present observer @ original experiment unconvinced, since victor , peggy might have orchestrated whole experiment start finish.

further notice if victor chooses s , b s flipping coin on-camera, protocol loses zero-knowledge property; on-camera coin flip convincing person watching recording later. thus, although not reveal secret word victor, make possible victor convince world in general peggy has knowledge—counter peggy s stated wishes. however, digital cryptography flips coins relying on pseudo-random number generator, akin coin fixed pattern of heads , tails known coin s owner. if victor s coin behaved way, again possible victor , peggy have faked experiment , using pseudo-random number generator not reveal peggy s knowledge world in same way using flipped coin would.

notice peggy prove victor knows magic word, without revealing him, in single trial. if both victor , peggy go mouth of cave, victor can watch peggy go in through , come out through b. prove certainty peggy knows magic word, without revealing magic word victor. however, such proof observed third party, or recorded victor , such proof convincing anybody. in other words, peggy not refute such proof claiming colluded victor, , therefore no longer in control of aware of knowledge.

two balls , colour-blind friend

this example requires 2 identical objects different colours, such 2 coloured balls, , considered 1 of easiest explanations of how interactive zero-knowledge proofs work. first demonstrated live software engineers konstantinos chalkias , mike hearn @ blockchain related conference in september 2017 , inspired work of prof. oded goldreich, used 2 differently coloured cards.

imagine friend colour-blind , have 2 balls: 1 red , 1 green, otherwise identical. friend seem identical , sceptical distinguishable. want prove him in fact differently-coloured, nothing else, not reveal 1 red , green.

here proof system. give 2 balls friend , puts them behind back. next, gets 1 of balls , brings out behind back. on put ball behind , probability 50% reveal 1 of 2 balls. each time ask you, did switch ball?

by looking @ colours, can of course certainty whether or not switched them. on other hand, if same colour , hence indistinguishable, there no way guess correctly probability higher 50%.

if , friend repeat proof multiple times (e.g. 128), friend should become convinced ( completeness ) balls indeed differently coloured; otherwise, probability have randomly succeeded @ identifying switch/non-switches close 0 ( soundness ).

the above proof zero-knowledge because friend never learns ball green , red; indeed, gains no knowledge how distinguish balls.