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$
$\endgroup$
3
-
$\begingroup$ I believe you would also need a not operation. $\endgroup$– mikeazoDec 27, 2012 at 2:59
-
$\begingroup$ universal operations are add, xor or nand , nor , not sure why they defined it with "and" and "mult" $\endgroup$– sashankDec 27, 2012 at 3:27
-
$\begingroup$ You ask about *add*/multiply, but the title says *AND*/multiply $\endgroup$– AFSDec 27, 2012 at 3:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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$– sashankDec 27, 2012 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$– sashankDec 27, 2012 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$– AFSDec 27, 2012 at 8:46
-
$\begingroup$ i got the complexity ! thats why may be FHE schemes are highly inefficient $\endgroup$– sashankDec 27, 2012 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$– mikeazoJan 11, 2013 at 19:13