Is it necesary to introduce noise in building fully homomorphic encryption?

At present, almost all formally published FHE schemes are based on noisy approach. However, there are some noise-free FHE constructions posted at ePrint or arXiv. But all these noise-free FHE schemes have not been formally published, due to --- partially --- lack of provable security reductions. Gentry also published his position paper "Computing on the edge of chaos: Structure and randomness in encrypted computation" in ECCC. These progress urges me to think the above question.

  • $\begingroup$ All known FHE are based on noisy Somewhat HE. $\endgroup$
    – 111
    Jan 29 '17 at 11:44
  • 1
    $\begingroup$ Nuida's FHE framework is noise-free, although at present there is no provable secure instantiations. But lacking of successful noise-free constructions of FHE cannot stop us efforts in probing this problem. $\endgroup$ Jan 29 '17 at 13:01
  • $\begingroup$ A more suttble problem: What is the difference between noise and randomness? Say, we never think that Elgamal scheme and Pailler scheme are noise-based construction, although there are randomness involved in the encryption. $\endgroup$ Jan 29 '17 at 13:04
  • $\begingroup$ good point, didn't know that paper of Nuida. Also, it seems that, is not clear what kind of finite non-commutative groups to use. Noise in LWE based cryptosystems, is not random but follows gaussian distribution with small s. $\endgroup$
    – 111
    Jan 29 '17 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.