identifying presence of encryption of zero in additive homomorphic encryption

Question

Lets say the server has corpus of ciphertext contains $enc(a),enc(b),enc(c), \dotsc enc(x)$. The encryption function is an additive homomorphic scheme (like Paillier). The server knows only the public key. The client holds both public and private keys.

Is there a way for client to identify if there is an encryption of $0$ in the corpus? i.e. is any of $a,b,c \dotsc x$ is a $0$. A trivial solution is for the client to iteratively retrieve each ciphertext and decrypt it to see if it is $0$. Can we do any better ? i.e. without iteratively retrieving each element or downloading the entire corpus of ciphertext ?

If it were a multiplicative homomorphic scheme, the server could multiply all the encryptions and give the result i.e. $enc(res) = enc(a)\times enc(b) \times \dotsc enc(x)$ , the client could just decrypt the result to see if the result is $0$ . i.e. $dec(enc(res)) = 0$ if at least one of $a,b,...,x = 0$.

Are there any such tricks possible in additive homomorphic scheme ?

Answer 1

I do not think what you want is possible with any simple solution - by simple, I mean computationally less expensive than downloading and decrypting all the ciphertexts. Basically, multiplicative homomorphism allows you to check some algebraic "OR": if there is a single 0, then the product of all the plaintexts will be 0.

Additive homomorphism, on the other hand, only allow you to check some algebraic "AND", id est, to check whether all the encrypted values are 0 or not (this is done simply by computing some linear combination of all the ciphertexts with uniformly random coefficients, and decrypting the result ony; if it's zero, then with overwhelming probability, all the ciphertexts encrypt 0). What you're looking for is an algebraic "OR" on additive encryption, which typically require a linear number of ciphertexts (so basically, it will not be really better than downloading and decrypting everything).

(By the way, you mentioned that with a multiplicative scheme, "the server could multiply all the encryptions and give the result". You should note that here, you assume a multiplicative scheme which can encrypt the zero value. The only such scheme I know off (appart from fully homomorphic encryption) is the one I constructed in a recent paper)

EDIT: now, it depends on your setting. If you assume each plaintext $m$ was encrypted as $E(m), E(R\times b)$ where $R$ is a random coin, and $b$ is a bit which is 0 if $m$ is non zero, and 1 else, then you have a solution: the server simply computes and sends a random linear combination of the E(R^b), and the client decrypt the single resulting ciphertext. If it encrypts a random value, there was a zero; else, there was no zero. However, this extended encryption scheme $E(m), E(R\times b)$ is not additively homomorphic anymore.