3
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Can client have access to public key? $\endgroup$ – vivek Jun 14 '16 at 14:20
  • $\begingroup$ ofcourse yes , client has access to both public and private keys, edited the question $\endgroup$ – sashank Jun 14 '16 at 14:22
  • $\begingroup$ Client can encrypt 0. Then do xor operation with these ciphertext. xoring same value results in null as 1 xor 1 is zero $\endgroup$ – vivek Jun 14 '16 at 14:26
  • $\begingroup$ Is XOR supported homomorphically ? not sure if it would work $\endgroup$ – sashank Jun 14 '16 at 14:36
  • $\begingroup$ Addition is xor in binary $\endgroup$ – vivek Jun 14 '16 at 14:48
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting , any reference to your paper ? $\endgroup$ – sashank Jun 14 '16 at 15:15
  • $\begingroup$ Sure, here it is: eprint.iacr.org/2015/990.pdf (but I'm not conviced that it is that relevant to your question - I was just pointing a small subtlety). $\endgroup$ – Geoffroy Couteau Jun 14 '16 at 15:16
  • $\begingroup$ btw , will there be a solution if client wants to know if there is encryption(1) instead of (0) in the above question ? $\endgroup$ – sashank Jun 15 '16 at 2:21
  • $\begingroup$ It will not change anything: if it could change anything, the server would just have to homomorphically add 1 to all the ciphertexts, and the client would run this algorithm to recover the information he is looking for. $\endgroup$ – Geoffroy Couteau Jun 15 '16 at 9:34
  • 1
    $\begingroup$ I think we mention somewhere in the intro (related work section) that it's not related to proxy re-encryption: in proxy re-encryption, you keep the same scheme and change the public key; here, you get as output an encryption with a completely different scheme. For what I know of proxy re-encryption, it cannot be used to answer this switching problem that we addressed. $\endgroup$ – Geoffroy Couteau Jun 16 '16 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.