[edanm]

I also really love the Waldo example, and give it often. Just FYI (as noted by SilasX in other comments), this is not officially a Zero Knowledge proof, since you're "proving too much" (people who are not the verifier will "know that you know", which is not allowed in ZKPs).

Btw, another favorite of mine which I often give as a riddle (not a ZKP, but an interactive proof): Assume I claim to have the superpower of knowing exactly how many leaves are on a tree just by looking at it. How can you verify this without actually having to count an entire tree's worth of leaves?

[lccarrasco]

rot13'd to avoid spoilers

Vf vg ol erzbivat n pregnva ahzore bs yrnirf naq nfxvat sbe gur gbgny pbhag ntnva, gura fhogenpgvat obgu naq pbzcnevat gur qvssrerapr?

[edanm]

Yep.

Also rot13'd:

Lbh erzbir n xabja (gb lbh) ahzore bs yrnirf juvyr zl onpx vf ghearq, gura nfx zr ntnva. Gura lbh pna frr vs guvf ahzore vf pbeerpg. Lbh pna ercrng guvf nf znal gvzrf nf lbh yvxr.

Lbh pna "fvzcyvsl" guvf ol whfg pubbfvat rnpu gvzr jurgure gb erzbir n yrns be abg, gura nfxvat zr vs lbh qvq be abg. Gura vg'f rnfl gb frr gung gur cebonoyl bs trggvat guvf evtug a gvzrf vf 1/2^a.

[phyzome]

I was stumped at first, but then I changed my approach:

Vs fbzrbar unf guvf novyvgl, gura gurl'er abg whfg rfgvzngvat -- gurl xabj gur rknpg ahzore. Gung zrnaf gurl pna gryy gur qvssrerapr orgjrra n gerr jvgu gubhfnaq yrnirf if. n gubhfnaq naq bar...

...naq gung'f jura vg uvg zr. :-)

[lccarrasco]

Ohhh, that's cool, thanks for sharing!