8
$\begingroup$
  1. Is that correct that Somewhat Homomorphic Encryption is more efficient that “Fully Homomorphic Encryption” (FHE) but less efficient than Partially Homomorphic Encryption (e.g Paillier encryption)?
  2. Is that correct that in Somewhat Homomorphic Encryption (e.g. used in Private Database Queries Using Somewhat Homomorphic Encryption (PDF)), the plaintext can be defined over a “known finite field”, so after homomorphic operations – when we decrypt – the plaintext is in that finite field?
$\endgroup$
8
$\begingroup$

PHE (partially homomorphic encryption) schemes are in general more efficient than SHE and FHE, mainly because they are homomorphic w.r.t to only one type of operation: addition or multiplication.

SHE is more general than PHE in the sense that it supports homomorphic operations with additions and multiplications. The drawback is that you can perform only a limited number hom. operations.

To answer your first question, a SHE scheme is also a PHE. This implies that PHE's are at least as efficient as SHE's.

FHE allows you to do an unbounded number of hom. operations by bootstrapping. This step can only be done (currently) by evaluating the decryption circuit inside a SHE scheme.

AFAIK, all plaintext / ciphertext operations are done within a known modulus. The only unknown thing should be the secret key. See a construction example here: DGHV Scheme.

$\endgroup$
  • $\begingroup$ thank you for the answer. Could you please compare performance of SHE and FHE? Thanks ! $\endgroup$ – user153465 Aug 31 '16 at 8:44
  • 2
    $\begingroup$ AFAIK, FHE schemes are typically SHE schemes where an expensive bootstrapping procedure solves the limitations of SHE. Thus as long as no bootstrapping is required, SHE and FHE is essentially the same, i.e., comparable in performance. Once bootstrapping kicks in FHE becomes much more expensive, but it is not really a fair comparison, because bootstrapping is required in FHE to do what cannot be done in SHE. $\endgroup$ – Guut Boy Aug 31 '16 at 9:19
  • $\begingroup$ @GuutBoy Thank you for the comment. Also, it's said "SHE supports a limited number of homomorphic operations". My question is: how many operations SHE supports? 5 or 10 operations? $\endgroup$ – user153465 Aug 31 '16 at 10:49
  • 1
    $\begingroup$ @user153465 that depends entirely on the concrete SHE scheme and the chosen parameters. $\endgroup$ – Guut Boy Aug 31 '16 at 10:51
  • 1
    $\begingroup$ To bootstrap, you also require a circular security assumption that is not really well studied. You need to give out an encryption of the secret key under itself. As for the number of operation you support, you can basically set the parameters to be able to support any bounded number of operation you want, but the more operation you want to do, the less efficient the scheme will be. Additions are basically free for known SHE, but multiplications can be really costly. $\endgroup$ – Florian Bourse Sep 2 '16 at 8:55

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.