PHE/FHE add and compare attack I am aware of this attack that applies to PHE (partially homomorphic encryption) given the attacker has access to a trusted oracle that can Convert (i.e decrypt and re-encrypt) between AHE (additive, e.g. Paillier) and DET (deterministic) schemes.

Pseudocode:

1. Get ciphertexts E(0) in DET and E(­1) in AHE
2. i = 0
3. Convert E(x) to DET encryption
4. Compare E(x) to E(0)
5. If equal, print i and exit
6. Convert E(x) to AHE encryption
7. Add E(x) and E(­1) using homomorphic property
8. i = i + 1
9. Goto 3


My question is how is this attack avoided in FHE (fully homomorphic encryption) which allows arbitrary computations (e.g adding and comparing) on ciphertexts.
My question is how is this attack avoided in FHE (fully homomorphic encryption) which allows arbitrary computations (e.g adding and comparing) on ciphertexts.


We don't give attackers access to such Oracles.  Such an Oracle would allow an attacker to decrypt (as you've noted), and so cannot be computed without help of the private key (or so we hope, otherwise the encryption method is broken).  So, unless the attacker gets some help from someone with the private key, he cannot perform this attack (and, if the attacker does get insider help, that insider could just decrypt the text, and hand the decrypted text to the attacker).

Note that this is not specific to homomorphic encryption; for any public key encryption method, an Oracle that will determinize a ciphertext will allow the attacker to test values (by the attacker determinizing the challenge ciphertext, make a guess as to the plaintext, encrypting it, determinizing that encryption, and seeing if it matches the challenge ciphertext).