Zero Knowledge Proof SystemsZero Knowledge ProofsInteractive Proof SystemsSlide 4Zero Knowledge Tunnel ExampleTunnel ObservationsOther Tunnel ObservationsZero Knowledge Technique 1Slide 9Slide 10Slide 11Zero Knowledge in PracticeZero Knowledge In PracticeHomeworkZero Knowledge Proof SystemsJoseph John Armbruster IVZero Knowledge ProofsAllow one person to convince another person of some fact without ever revealing any information about the proof.Are NOT proofs in a strict mathematical sense.Provide overwhelming evidence towards the truth of a statementInteractive Proof SystemsChallenge / Response–Peggy – The Prover–Vic – The Verifier–Peggy wishes to prove a statements truth to Vic–Peggy and Vic will communicate via a series of “Rounds” in a Challenge / Response manner–If Peggy can give a successful reply to all of Vic’s challenges, Vic accepts the truth of Peggy’s statementInteractive Proof SystemsHow does the Proof go?i. Peggy makes a claimii. Vic will challenge Peggyiii. Peggy will respondiv. Vic will accept or reject the response (end or ret. ii)After N rounds (where N is determined by Vic), Vic will accept or reject Peggy’s claim.Zero Knowledge Tunnel ExampleLocked DoorI can go through the door Prove it!Come out to the left.Here I am.OK, you succeed.Come out to the right.Here I am.OK, you succeed.Observation PointCome out to the left.Here I am.Ok. You fail!Tunnel ObservationsPeggy must choose the left or right side:–50% chance of fooling Vic !Suppose we test Peggy 10 times and she comes out the correct side.–There is one chance in 2^10 that Peggy does not know how to go through the door.Victor is therefore convinced she can (although he can keep on testing for further verification)Other Tunnel ObservationsWhat if someone was watching?–Are they convinced Peggy can go through the door?NO, Peggy and Victor could have planned the sequence of lefts and rights ahead of timeIs there ever a proof?–Not in the strict mathematical sense.There is overwhelming evidence obtained through a series of challenges and responses. Note: This is how a Zero Knowledge proof “works”Zero Knowledge Technique 1Let N be the product of two primes, P and QLet Y be a square mod N with gcd(Y,N)=1–Note: Finding square roots modulo N is equivalent to factoring NPeggy Claims to know a square root S of Y.Victor wants to verify this, but Peggy does not want to reveal S!Zero Knowledge Technique 1Peggy chooses two random numbers R1, R2 with (R1)(R2) = S (mod N )–Note: R1 is chosen at Random with gcd(R1,N)=1 and she lets R2 = (S) (invR1)Peggy Computes: X1=R1^2 (mod N) and X2=R2^2 (mod N)Peggy Sends X1 and X2 to VictorZero Knowledge Technique 1Victor checks that (X1)(X2)=Y (mod N)Victor randomly chooses X1 or X2 and asks Peggy to supply a square root of it. He then checks that it is an actual square root.These steps are repeated until Victor is convincedZero Knowledge Technique 1What if Peggy does not know the square root of Y?–She sends Victor X1 and X2 with (X1)(X2)=Y–IF she knows the square root of Y, THEN she knows the square roots of X1 and X2.–IF she does not know the square root of Y, THEN it is still possible for her to know the square root of ONE of X1 and X2, but not both.Zero Knowledge in PracticeIdentification Schemes:–Is it possible for Alice to identify herself to Bob without “giving away” her identifying information.Examples:–Feige-Fiat-Shamir Identification (FFS) – Reduces the number of communications between Peggy and Victor. This is used as a general purpose Identification scheme.–Schnorr Identification – The most attractive scheme. Requires a Trusted Authority (TA) to produce an ID which contains personal information.Zero Knowledge In Practice–Okamoto Identification Scheme – A modified Schnorr method which has been proven to be secure.–Guillou-Quisquater Scheme – Identification scheme built upon RSA. This scheme has not been proven to be secure (even assuming the RSA cryptosystem is secure!) Like RSA, this method is a computationally intensive.HomeworkQuestions or comments?Does everyone understand what the questions are looking
View Full Document
Unlocking...