Adaptive security of practical garbling schemes

A garbling scheme enables one to garble a circuit C and an input x in a way that C(x) can be evaluated, but nothing else is revealed. Since the first construction by Yao, tremendous practical efficiency improvements for selectively secure garbling schemes –where the adversary is forced to choose both input and circuit to be garbled at the same time– were proposed. However, in the more realistic setting of adaptive security where an adversary can choose the input adaptively based on the garbled circuit little is known about practical efficiency improvements. In this work, we initiate the study of practical garbling schemes that are both more efficient than Yao’s construction and adaptively secure. We provide insights into characteristics of these schemes and highlight the limitations of current techniques for proving adaptive security in this regime. Furthermore, we present an adaptively secure garbling scheme that garbles XOR gates with 2 and AND gates with 3 ciphertexts per gate, thus providing the first practical garbling scheme for NC1 circuits with adaptive security based on PRFs whose garbled circuit size is smaller than that of Yao’s construction.