A Fully homomorphic encryption scheme needs to support an evaluate function that can do add and multiply operations on cipher text.

Can we do all kinds of complex operations on cipher text like search, sort etc using just add and multiply ?

  • $\begingroup$ I believe you would also need a not operation. $\endgroup$ – mikeazo Dec 27 '12 at 2:59
  • $\begingroup$ universal operations are add, xor or nand , nor , not sure why they defined it with "and" and "mult" $\endgroup$ – sashank Dec 27 '12 at 3:27
  • $\begingroup$ You ask about *add*/multiply, but the title says *AND*/multiply $\endgroup$ – AFS Dec 27 '12 at 3:44

If addition and multiplication are preserved, then we can evaluate arithmetic circuits over the encrypted data.

It seems that your confusion about the class of problems that we can compute stems from the fact that you are envisioning boolean circuits in which we perform operations on the bitwise representations of the input. This is not an FHE question per se, but rather a question regarding the difference between the computational models of boolean circuits vs. arithmetic circuits. To understand the problems that can be computed with this model of computation, take a look at this paper. A relevant portion:

The definition above shows an evident difference between arithmetic circuits and Boolean circuits.While Boolean circuits can perform operations on the "bit representation" of the input field elements,that are not necessarily the arithmetic operations, arithmetic circuits cannot. Nevertheless, most algorithms for algebraic problems fit naturally into the framework of arithmetic circuits.

In regards to why they defined FHE this way, it follows the definition of Ring Homomorphism. By definition, a ring homomorphism is a function between two rings that respects addition and multiplication.

In practice, recent research on FHE studies lattices since ideal lattices yield both additive and multiplicative homomophisms.

  • $\begingroup$ but then what good it would be for real use , if we solve FHE i.e only add and mult over cipher texts , unless we find ways of solving universal operations $\endgroup$ – sashank Dec 27 '12 at 5:57
  • $\begingroup$ I have quickly checked hcrypt's implementation , boolean XOR is equivalent to arithmetic Add , boolean AND is equivalent to arithmetic Mult, so they would be universal operations to realise any circuit , i got my answer , thanks anyway $\endgroup$ – sashank Dec 27 '12 at 8:17
  • $\begingroup$ @sashank Indeed if we limit ourselves to one bit then boolean XOR is equivalent to arithmetic add(mod 2) and boolean AND is equivalent to arithmetic mult. But think about what happens when we have to carry a bit. A boolean function has independence between bits while an arithmetic function does have dependence(it can carry) $\endgroup$ – AFS Dec 27 '12 at 8:46
  • $\begingroup$ i got the complexity ! thats why may be FHE schemes are highly inefficient $\endgroup$ – sashank Dec 27 '12 at 8:49
  • $\begingroup$ @AFS, I'm going to try to work my way through the paper you reference, but it would seem that an arithmetic circuit should be able to simulate a boolean circuit and compute anything that a boolean circuit can compute. Is that not the case? $\endgroup$ – mikeazo Jan 11 '13 at 19:13

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.