Zero Knowledge ProofsSlide 2Zero Knowledge Proofs (ZKP)ZKPProperties of ZKPAdvantages of ZKPClassic ExampleFiat-Shamir Identification ProtocolFiat-Shamir Identification ProtocolSlide 10ApplicationsProductsReferencesZero Knowledge ProofsBySubha RajagopalanJaisheela KandagalZero Knowledge Proofs•Introduction•Properties of ZKP•Advantages of ZKP•Examples•Fiat-Shamir Identification Protocol•Real-Time ApplicationsZero Knowledge Proofs (ZKP)•Goldwasser, Micali, and Rackoff, 1985. •ZKP instance of Interactive Proof System•Interactive Proof Systems–Challenge-Response Authentication–Prover and Verifier–Verifier Accepts or Rejects the ProverZKP•Zero knowledge Transfer between the Prover and the Verifier•The verifier accepts or rejects the proof after multiple challenges and responses•Probabilistic Proof Protocol •Overcomes Problems with Password Based AuthenticationProperties of ZKP•Completeness–Succeeds with high probability for a true assertion given an honest verifier and an honest prover. •Soundness–Fails for any other false assertion, given a dishonest prover and an honest verifierAdvantages of ZKP•As name Suggests – Zero Knowledge Transfer•Computational Efficiency – No Encryption•No Degradation of the protocol•Based on problems like discrete logarithms and integer factorizationClassic Example •Ali Baba’s CaveAlice has to convince Bob She knows the secret to open the cave door without telling the secret (“Open Sesame”).(source: http://www.rsasecurity.com/rsalabs/faq/2-1-8.html)Fiat-Shamir Identification Protocol•3 Message Protocol•Alice A, the Prover and Bob B, the VerifierA B : x = r2 mod n A B : e { 0,1}A B : y = r * se mod n is y2 = x * ve ?•A random modulus n, product of two large prime numbers p and q generated by a trusted party and made public•Prover chooses secret s relatively prime to n•prover computes v = s2 mod n, where v is the public keyFiat-Shamir Identification Protocol•Alice chooses a random number r (1 r n-1) •Sends to Bob x = r2 mod n – commitment•Bob randomly sends either a 0 or a 1 ( e { 0,1}) as his challenge•Depending on the challenge from Bob, Alice computes the response as y = r if e = 0 or otherwise y = r*s mod n•Bob accepts the response upon checking y2 x * ve mod n•After many iterations, with a very high probability Bob can verify Alice’s identity•Alice’s response does not reveal the secret s (with y = r or y = r* s mod n)•An intruder can prove Alice’s identity without knowing the secret, if he knows Bob’s challenge in advance:–Generate random r–If expected challenge is 1, send x = r2/v mod n as commitment, and y = r as response–If expected challenge is 0, send x = r mod n as commitment•Probability that any Intruder impersonating the prover can send the right response is only ½ •Probability reduced as iterations are increased•Important - Alice should not repeat rFiat-Shamir Identification ProtocolApplications•Watermark Verification–Show the presence of watermark without revealing information about it–prevents from removing the watermark and reselling multiple duplicate copies•Others – e-voting, e-cash etc.Products•Sky’s VideoCrypt–Analogue decoding card for satellite DirecTV descrambler used to authenticate the subscriber’s card –Uses Fiat-Shamir Zero Knowledge Protocol•NGSCB – New Generation Secure Computing Base–Zero Knowledge for code attestationsReferences[1] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography. [2] Ross Anderson, Security Engineering[3] Wenbo Mao, Modern Cryptography theory and practice[4] Don Coppersmith (Ed.), Advances in Cryptology- CRYPTO ’95 Lecture Notes in Computer Science.[5] www.rsa.com[6] Oded Goldreich, Silvio Micali and Avi Wigderson, “ Proofs that yield nothing but their validity and a methodology of cryptographic protocol design”.[7] Oren, Y., “ Properties of Zero-knowledge Proofs”.[8] A Mitropoulos, and H. Meijer, “ Zero-knowledge proofs – a
View Full Document
Unlocking...