Malicious Security. A New Take on Dual Execution with Privacy- Correctness Tradeoffs While Yao’s garbled circuits are naturally secure against a malicious evaluator, they have the drawback of being insecure against a ma- licious garbler. A garbler can “mis-garble” the function, either replacing it with a different function entirely or causing an error to occur in an informative way (this is known as “selective failure”). Typically, malicious security is introduced to Yao’s garbled circuits by using the cut-and-choose transformation [35, 41, 43]. To achieve a 2−λ probability of cheating without detection, the parties need to exchange λ garbled circuits [41].8 Some of the garbled circuits are “checked”, and the rest of them are evaluated, their outputs checked against one another for consistency. Because of the factor of λ computational overhead, though, cut-and-choose is expensive, and too heavy a tool for fPAKE. Other, more efficient transformations such as LEGO [50] and authenticated garbling [59] exist as well, but those rely heavily on pre-processing, which cannot be used in fPAKE since it requires advance interaction between the parties. Mohassel et al. [48] and Xxxxx et al. [34] suggest an efficient transformation known as “dual execution”: each party plays each role (garbler and evaluator) once, and then the two perform a comparison step on their outputs in a secure fashion. Dual execution incurs only a factor of 2 overhead over semi-honest gar- bled circuits. However, it does not achieve fully malicious security. It guarantees correctness, but reduces the privacy guarantee by allowing a malicious garbler to learn one bit of information of her choice. Specifically, if a malicious garbler garbles a wrong circuit, she can use the comparison step to learn one bit about the output of this wrong circuit on the other party’s input. This one extra bit of information could be crucially important, violating the privacy of the evaluator’s input in a significant way. We introduce a tradeoff between correctness and privacy for boolean func- tions. For one of the two possible outputs (without loss of generality, ‘0’), we restore full privacy at the cost of correctness. The new privacy guarantee is that if the correct output is ‘0’, then a malicious adversary cannot learn anything 8 There are techniques [44] that improve this number in the amortized case when many computations are done — however, this does not fit our setting. beyond this output, but if the correct output is ‘1’, th...
