3
$\begingroup$

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.

$\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$
    – poncho
    Oct 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$ Oct 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$
    – poncho
    Oct 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

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
1
  • 2
    $\begingroup$ A more recent one is Tinygarble. $\endgroup$
    – Mikero
    Oct 29, 2015 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.