Paper 2020/1502

Witness Encryption from Garbled Circuit and Multikey Fully Homomorphic Encryption Techniques

Kamil Kluczniak


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
witness encryptionfully homomorphic encryptiongarbled circuits
Contact author(s)
kamil kluczniak @ gmail com
2021-01-21: revised
2020-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kamil Kluczniak},
      title = {Witness Encryption from Garbled Circuit and Multikey Fully Homomorphic Encryption Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1502},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.