Computer Science Colloquia
Monday, April 25, 2011
Chih-hao Shen-PhD Qualifying Exam Presentation
Attending Faculty:Jack Davidson, Chair; David Evans; Gabriel Robins; abhi shelat
Olsson Hall 228E, 15:00:00
Two-Output Secure Computation with Malicious Players
Yao (FOC'82) proposed a method that allows two honest-but-curious players---a generator with secret input x, and an evaluator with secret input y---to jointly compute a function f(x,y) such that the generator receives nothing and the evaluator receives f(x,y). In this project, we present a method to transform Yao's two-player garbled circuit protocol into one that is secure against malicious adversaries that relies on witness indistinguishability. Our approach can enjoy lower communication and computation overhead than methods based on cut-and-choose (e.g., Lindell and Pinkas, EUROCRYPT'07) and lower overhead than methods based on commit-and-prove (e.g., Jarecki and Shmatikov, EUROCRYPT'07). To do so, we develop and analyze new solutions to issues arising with this transformation:
- How the evaluator can guarantee the generator's input consistency;
- How the evaluator can retrieve input keys but avoid selective failure attacks;
- How to support different outputs for each player without adding extra gates to the circuit of the function f being computed;
- Challenging 3/5 of the circuits is near optimal for cut-and-choose (and better than challenging 1/2).
Our protocol requires the existence of secure-OT and claw-free functions that have a weak malleability property. We discuss an experimental implementation of our protocol to validate our efficiency claims.