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.
Category / Keywords: public-key cryptography / witness encryption, fully homomorphic encryption, garbled circuits Date: received 30 Nov 2020, last revised 20 Jan 2021 Contact author: kamil kluczniak at gmail com Available format(s): PDF | BibTeX Citation Version: 20210121:053649 (All versions of this report) Short URL: ia.cr/2020/1502