1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mikeazo Feb 10 '17 at 20:41
  • $\begingroup$ 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. $\endgroup$ – sava Feb 10 '17 at 20:50
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – sava Feb 10 '17 at 21:04

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.