Secure Computation Lecture Recap and Solutions
Lectures 19-20 by Arpita Patra cover secure computation, with a focus on perfect MPC in a malicious setting, VSS, multiplication protocols, Yao's 2-party protocol, and solutions to identified problems for garbled circuits construction and evaluation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Secure Computation Lecture 19-20 Arpita Patra
Recap and Roadmap >> i.t (perfect) MPC in malicious Setting > VSS (four round sharing + RS code based Reconstruction) > Multiplication Protocol with perfect secrecy. >> Yao in malicious Setting: LindellPinkas11 > Identify the problems > Fix the problems
Yaos 2 Party Protocol GC Constructor GC Evaluator P1 P0 Y = (y1,y2, yk ) X = (x1,x2, xk ) Construct a Garbled Circuit GC for Circuit C Problem 1: P0 may not construct GC for the agreed function. Keys corresponding to X = (x1,x2, xk )and GC y1 ky1w1 k0w1 k1w1 OT1 yk kykwk k0wk k1wk OTk Evaluate GC with the given input keys and interpret the output Z using output decryption tables Z
Fix for Problem 1 GC Constructor GC Evaluator P1 P0 Construct many Garbled Circuits for Circuit C Check some of them. Abort if there is a problem Get both keys for all input wires for those circuits How to check? Need to ensure that the probability of escape is negligible How many to check? Cut and Choose Paradigm: Classical Technique used against malicious adversary
Fix for Problem 1 GC Constructor GC Evaluator P1 P0 Construct s Garbled Circuits for Circuit C: GC1, ,GCs Check half (s/2) of them. Abort if there is a problem Get both keys for all input wires for those circuits How to check? s/2. Check circuits How many to check? s/2. Evaluation circuits How many to Evaluate? If all the evaluation circuits output the same, output that How to calculate output? Majority of the outputs of Evaluation circuits value; else output bot Clue: tweak one GC such that it outputs correct value if first bit of P1 is 0, else garbage Cut-and-choose security Parameter: s
Fix for Problem 1 noAbort: P1 does not abort badMaj: Majority of the circuits are bad Claim: Cheating Probability = Pr(noAbort badMaj) = Partial Proof (on the broad). Cut-and-choose security Parameter: s
