Leakage Resilient Secure Two-Party Computation

In the traditional {\em secure function evaluation} setting, some set of distrusting parties jointly compute a function of their respective inputs {\em securely} as if the computation is executed in an ideal setting where the parties send inputs to a trusted party that performs the computation and returns its result. Almost independently of secure computation, the area of {\em leakage resilient cryptography} has recently been evolving intensively, studying the question of designing cryptographic primitives that remain secure even when some information about the secret key is leaked. In this paper we initiate the study of {\em secure two-party computation in the presence of leakage}, where on top of corrupting one of the parties the adversary obtains leakage from the content of the secret memory of the honest party. Our study involves the following contributions: \BE \item {\em Security Definitions.} We formalize the notion of secure two-party computation in the presence of leakage and introduce security definitions in the {\em ideal/real framework}. Our formalization induces two types of adversarial attacks. We further study the feasibility of our definitions in the computational setting and explore some of the conditions under which these definitions are met. \item {\em Composition Theorems.} We provide compositions theorems for our new modelings. Our results provide compositions theorems for the case where the inputs of the parties are sampled from a min-entropy source distribution. \item {\em Leakage resilient oblivious transfer.} We present the first construction for 1-out-of-2 oblivious transfer with security against leakage of a constant fraction of the honest party's memory. Our protocol is based on the OT construction presented by Peikert et al.~\cite{PeikertVW08}. \item {\em Leakage resilient Yao's Garbled Circuit~\cite{Yao82}.} We provide the first general construction for secure two-party computation and show how to adapt the proof from~\cite{LP09} of Yao's protocol into the leakage resilient setting. Our result holds for a restricted set of functions due to technicalities arise in the proof. \EE