A recent work of Hemenway et al. (CRYPTO '16) modifies Yao's construction and shows that the resulting scheme is adaptively secure. This is done by encrypting the garbled circuit from Yao's construction with a special type of ``somewhere equivocal encryption'' and giving the key together with the garbled input. The efficiency of the scheme and the security loss of the reduction is captured by a certain pebbling game over the circuit.
In this work we prove that Yao's construction itself is already adaptively secure, where the security loss can be captured by the same pebbling game. For example, we show that for circuits of depth $d$, the security loss of our reduction is $2^{O(d)}$, meaning that Yao's construction is adaptively secure for NC1 circuits without requiring complexity leveraging.
Our technique is inspired by the ``nested hybrids'' of Fuchsbauer et al. (Asiacrypt '14, CRYPTO '15) and relies on a careful sequence of hybrids where each hybrid involves some limited guessing about the adversary's adaptive choices. Although it doesn't match the parameters achieved by Hemenway et al. in their full generality, the main advantage of our work is to prove the security of Yao's construction as is, without any additional encryption layer.
Category / Keywords: cryptographic protocols / Garbled Circuits, Adaptive Security, Secure Computation, nested hybrids Original Publication (in the same form): IACR-TCC-2016 Date: received 23 Aug 2016, last revised 25 Aug 2016 Contact author: zahra at ccs neu edu Available format(s): PDF | BibTeX Citation Version: 20160825:185412 (All versions of this report) Short URL: ia.cr/2016/814 Discussion forum: Show discussion | Start new discussion