# 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.

• I'm assuming that should say E(i), not E(x). That said, how do you convert between Paillier and a deterministic scheme? I've never heard of that. – mikeazo Feb 10 '17 at 20:41
• I do mean E(x), which is the ciphertext attempting to break. i will be equal to the plaintext value of E(x) once the algorithm runs to completion. Converting here means decrypt and re-encrypt using a trusted entity. I made an edit to clarify. – sava Feb 10 '17 at 20:50

• Indeed this oracle is a trusted one and has access to the decryption keys. There are legitimate cases where allowing Converting from one scheme to another is useful (e.g. in this paper where this attack was taken from) albeit carefully choosing what schemes. – sava Feb 10 '17 at 21:04