I am new to Homomorphic Encryption.

The scenario is that the encrypted data will be sent from Alice to a trusted cloud machine for computing operations and then sent to Bob. Can HE (e.g. NTRU) be faster than using symmetric encryption and having to decrypt the data from Alice, do operations, and encrypt again to sent to Bob (e.g. AES)?

  • 4
    $\begingroup$ If you have a trusted party, you don't need homomorphic encryption. $\endgroup$ – CodesInChaos Aug 10 '16 at 8:32

As CodesInChaos mentioned in the comments: If you have a trusted party, you don't need homomorphic encryption.

More to the point of the question-- No.

A "reasonably optimized" (especially, like NTRU, fully) homomorphic encryption scheme should always be somewhat slower / less efficient than using plain symmetric-key encryption (and 'plaintext operations' outside of a ciphertext).

To see this is not just true, but should ALWAYS be true: Note that any FHE scheme is also a symmetric-key encryption scheme (ignore the homomorphism; let the scheme's public-key be kept secret as a private encryption key). Extra features can't come for free. The best you can hope for is 'not much overhead in practice,' but (F)HE will never be faster in general.

Bonus thought: Short, and hopefully more intuitive, "proof" that FHE.Eval is /always/ going to be more expensive than the SYM-1.Dec + basic operations + SYM-2.Enc option--

Note that the decryption operation in EVERY KNOWN fully homomorphic encryption scheme is close-to-linear time: With lattice cryptosystems, you're always performing inner product of a ciphertext-vector $c$ with a key-vector $s$ (then rounding) in order to decrypt. No matter how much computation you do, the encrypt/decrypt cost remains the same.

Further, assume each 'plaintext operation' of cost "C" has cost at least "C+1" when you perform it homomorphically. ("Only +1" is quite generous.) Since FHE should allow unbounded computation, just consider computing FHE.Eval longer and longer until the "C+1"-per-operation overhead offsets the small, one-time cost of encrypting/decrypting.

| improve this answer | |

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.