Paper 2020/1502

Witness Encryption from Garbled Circuit and Multikey Fully Homomorphic Encryption Techniques

Kamil Kluczniak

Abstract

In a witness encryption scheme, to decrypt a ciphertext associated with an NP statement, the decrypter takes as input a witness testifying that the statement is in the language. When the statement is not in the language, then the message is hidden. Thus far, the only provably secure constructions assume the existence of indistinguishability obfuscation (iO) and multilinear maps (MMaps). We make progress towards building polynomially efficient witness encryption for NP without resorting to iO or MMaps. In particular, we give a witness encryption scheme from Yao's garbled circuit technique and a new type of fully homomorphic encryption (FHE) that we call annihilating. Interestingly, we require a version of the annihilating FHE that is circularly insecure, i.e., allows testing the presence of a key cycle. We prove our witness encryption's security from a novel assumption about our annihilating FHE. We formulate the assumption as an interplay between an annihilating FHE and ideal ciphers. We show a candidate (leveled) annihilating FHE built from a multikey variant of the BGV/BFV fully homomorphic cryptosystems.