Are there any Homomorphic Encryption(HE) schemes that result in noisy answers ? By noisy i mean , the answers could be approximately near the actual answers by noise factor $\epsilon$.

For example , we could get $dec_{sk}(eval_{pk}({enc_{pk}(5) + enc_{pk}(10))) = 16}$ where as the real answer is 15. Here $enc,eval,dec$ are functions of an HE scheme and $sk,pk$ are private and public keys. The scheme could be Fully HE or Semi HE or Partial HE

  • $\begingroup$ Presumably you want to avoid assuming the existence of standard homomorphic encryption schemes, since otherwise there's a "Just Do It" construction. $\;$ $\endgroup$
    – user991
    Apr 8 '15 at 4:24
  • $\begingroup$ @RickyDemer sorry i did not get you, can u be more clear ? what is a "just do it" construction ? $\endgroup$
    – sashank
    Apr 8 '15 at 4:27
  • 2
    $\begingroup$ If there is a standard homomorphic encryption schemes then there is a noisy homomorphic encryption scheme. $\:$ That can be proven by showing how one can directly turn a standard homomorphic encryption scheme into a noisy homomorphic encryption scheme. $\:$ (I have given two other "Just Do It" constructions on this site.) $\;\;\;\;$ $\endgroup$
    – user991
    Apr 8 '15 at 4:32
  • $\begingroup$ @RickyDemer got it ! now the question left is whether there are natively noisy algorithms $\endgroup$
    – sashank
    Apr 8 '15 at 5:13
  • $\begingroup$ doesn't Regev scheme based on LWE verify this if you set the right parameters for the error distribution? $\endgroup$ Apr 8 '15 at 8:38

Yes, on the paper Homomorphic Encryption for Arithmetic of Approximate Numbers, Cheon et al. propose a scheme in which the error is not completely eliminated during decryption.

That is, if $c$ is an encryption of $m$, then $Dec(c) = m + e$, where $e$ is some small error.

Roughly speaking, that scheme simulates floating-point arithmetic, since this type of arithmetic also accumulate errors.

With that, the authors manage to perform operations that are hard to do with exact homomorphic encryption schemes. For example, in Algorithm 2 (page 15), they show how to compute homomorphically $\frac 1 m$ with $r$ bits of precision (with other schemes, that is only possible using bootstrapping...).


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.