Multi-Key / Spooky Fully Homomorphic Encryption

By Daniel Wichs (Northeastern) Abstract: A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict constraints on efficiency, but the input must be garbled very efficiently on-line, in time which is much smaller than the circuit size |C|. Yao's garbling scheme only achieves this under one-way functions in the selective security setting. It has remained as an open problem to achieve the stronger notion of adaptive security where the adversary can choose the input x adaptively after seeing the garbled circuit. In this work, we modify Yao's scheme in a way that maintains all of its desirable features, while allowing us to prove adaptive security in various parameter regimes under one-way functions. As our main instantiation, we get a scheme where the size of the garbled input is only proportional to the width of the circuit, which is related to the space complexity of the computation, but independent of the circuit's depth. More broadly, we develop a connection between adaptive security in our framework and a certain type of pebble complexity} As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.