1Secret Sharing and Zero-knowledge ProofsDawn [email protected]• Digital signatures– What security properties is it designed to provide?– One-time signature– RSA signature– ElGamal signature• Secret-sharing schemes3Secret Sharing• A trusted authority TA has a secret K• Wants to split K into n shares S1, …, Sn, distributing to n users U1,…,Un respectively, s.t.– A reconstruction algorithm can be used to efficiently reconstruct K from any t of the n shares– Any t-1 of the n shares reveal no information about K• Such a scheme is called an (n,t) threshold secret sharing scheme4(n,n) Secret Sharing Scheme• Suppose the secret K is an integer btw 0 and M-1• (n,n) threshold scheme:– Pick S1,…,Sn-1uniformly at random btw 0 and M-1– Set Sn= K- (S1+ … + Sn-1) mod M• How to reconstruct K?• What happens if n-1 users get together?5(n,t) Threshold Scheme• Polynomials modulo prime p– Polynomials whose coefficients are elements mod p– E.g., f(x) = x2+ 2x + 4 mod 5– Degree-n polynomial f (mod p) is uniquely determined by any n+1 distinct pairs (xi, yi) s.t. f(xi) = yi» Lagrange interpolation• To (n,t) threshold share secret K:– Pick a random polynomial f (mod p) of degree t-1 s.t. f(0) = K– Share si= f(i) for i = 1 to n– How to recover K?– How many shares do you need to recover K?– What happens if you have fewer shares than t?6Zero-knowledge Proof• Alice->Bob: I know the solution to Que 3 in hw 2, but I can’t tell you what the solution is• Bob->Alice: tell me, o.w. I don’t believe you• Alice->Bob: Ok, I’ll prove to you that I know the solution in Zero-knowledge7Zero-knowledge protocol• Idea: (interactive) proof btw prover A & verifier B• At the end of the proof, B is convinced A knows a secret satisfying a fact F• But B has no information about that secret8The Zero-knowledge Cave (I)• Alice wants to prove to Bob that she knows how the magic word to open door– Without telling Bob the magic worddoor9The Zero-knowledge Cave (II)1. Alice walks to either C or D;2. Bob stands at V, calling either Left or Right;3. Alice complies, using her magic word to open door if needed;4. Alice & Bob repeats steps 1-3 for n timesCDV10The Zero-knowledge Cave (III)• What if Alice didn’t know the magic word?• What does Bob learn at the end of the proof?CDV11How to prove knowledge of square root• Finding square root mod N=pq is as hard as factoring• A knows b s.t. b2 =y mod pq, & wishes to prove to B that she knows such b.• A → B: s =: r2mod pq (A picks random r)• B flips coin• B → A: coin flip• If heads– A → B: t =: r mod pq– B verifies t2≡ s mod pq• If tails– B → A: t =: rb mod pq– A verifies t2≡ sy mod pq• What if A didn’t know the square root?• What did B learn after the proof?12Conclusion• Secret-sharing schemes– (n,t) threshold schemes using polynomials• Zero-knowledge proofs– Concepts– Zero-knowledge proof of square
View Full Document
Unlocking...