Skip to main content
IBM 
ShopSupportDownloads
IBM HomeProductsConsultingIndustriesNewsAbout IBM
IBM : developerWorks : Security : Education - online courses
Introduction to cryptology: Pt. 3
Download tutorial zip fileView letter-sized PDF fileView A4-sized PDF fileE-mail this tutorial to a friend
Main menuSection menuGive feedback on this tutorialPreviousNext
4. "Exotic" protocols
  


Zero-knowledge proofs, part 5 page 11 of 12


So far, so good. What has this shown? If a Peggy imposter did not know the isomorphism of G and H, the best the imposter could do is to try to pass off an I that is isomorphic with G (she knows G and H, as does Victor), and just hope Victor doesn't ask for the isomorphism of H and I. Alternately, a Peggy imposter could try to pass off an I she constructed from H, and hope the opposite. Either way, the imposter has a 50% chance of getting caught by the protocol above.

Victor, however, probably does not find 1/2 confidence sufficient for Peggy to prove she knows the isomorphism. Fortunately, Victor can simply demand that Peggy now generate an I' and undergo the protocol again. If she passes now, Victor can be 3/4 confident about Peggy. If that's not good enough, she can do a third pass of the protocol with I'', and obtain a 7/8 confidence; or a 15/16 confidence, a 31/32 confidence, and so on. By iterating the protocol, Peggy can prove that she knows the isomorphism for an arbitrary confidence requirement by Victor (but always less than 100% by some amount). No matter how many times the protocol is iterated, Victor gains no knowledge that helps him in constructing his own G/H isomorphism, so "zero knowledge" is leaked to Victor.


Main menuSection menuGive feedback on this tutorialPreviousNext
PrivacyLegalContact