Paper 2017/903

On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-Interactive Arguments

Omer Paneth and Guy N. Rothblum


We define and study zero-testable homomorphic encryption (ZTHE) -- a semantically secure, somewhat homomorphic encryption scheme equipped with a weak zero test that can identify trivial zeros. These are ciphertexts that result from homomorphically evaluating an arithmetic circuit computing the zero polynomial over the integers. This is a relaxation of the (strong) zero test provided by the notion of graded encodings, which identifies all encodings of zero. We show that ZTHE can suffice for powerful applications. Based on any ZTHE scheme that satisfies the additional properties of correctness on adversarial ciphertexts and multi-key homomorphism, we construct publicly verifiable non-interactive arguments for delegating computation. Such arguments were previously constructed from indistinguishability obfuscation or based on so-called knowledge assumptions. The arguments we construct are adaptively sound, based on an efficiently falsifiable assumption, and only make black-box use of the underlying cryptographic primitives. We also show that a ZTHE scheme that is sufficient for our application can be constructed based on an efficiently-falsifiable assumption over so-called "clean" graded encodings.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
omerpa @ gmail com
2018-04-03: revised
2017-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Omer Paneth and Guy N.  Rothblum},
      title = {On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-Interactive Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2017/903},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.