What if we were substitute the ANDs with XORs in some homomorphic encryption scheme like BGV(https://eprint.iacr.org/2011/277.pdf), LTV ( https://eprint.iacr.org/2013/094.pdf) ? It may be more efficient ? For example if we can substitute an AND with 6 XORs, we would achieve a better efficiency for some choice of the parameters.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Are you asking if we can create an FHE system with only XOR as the homomorphic operation? Or, as you asking if we could optimize an homomorphic calculation by minimizing the number of AND's used (even if it drastically increases the number of XORs used)? If the former, well, XOR is not a complete function (and in particular, you cannot create an AND by using only XORs). $\endgroup$– ponchoOct 28, 2015 at 21:07
-
$\begingroup$ Thank you for your reply. I was addressing the second, namely if you can minimize the number of ANDs ? $\endgroup$– Radu MardariOct 28, 2015 at 21:19
-
$\begingroup$ It occurs to me that if the question "how can we optimize a particular calculation to minimize the number of AND gates", the answer just might depend somewhat on what that particular calculation is. $\endgroup$– ponchoOct 29, 2015 at 3:12
-
1$\begingroup$ @user2991856: if the question is not about using only XOR gates, perhaps the title should be adjusted accordingly; like: What about using less AND gates in favor of XOR in homomorphic encryption? $\endgroup$– fgrieu ♦Oct 29, 2015 at 9:12
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
As poncho comments, a homomorphic encryption scheme that only supports the XOR operation would not be fully homomorphic, i.e., it would not allow evaluation of all functions. However, you can try to optimize the implementation of a function in order to minimize the number of AND's at the cost of extra XOR's. This is not only relevant for FHE but also in secure multi-party computation (MPC), where the XOR operation can also usually be computed much faster than AND.
Optimizing the circuit of a function to include less AND's, and possibly more XOR's, is a well known technique to make FHE and MPC applications run faster. In fact people have made special compilers to automate this process. An example of such a compiler in the MPC space can be found in this paper (although by now there are probably better ones around).
-
2