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.

  • 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 '15 at 21:07
  • $\begingroup$ Thank you for your reply. I was addressing the second, namely if you can minimize the number of ANDs ? $\endgroup$ – user2991856 Oct 28 '15 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 '15 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 '15 at 9:12

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

| improve this answer | |
  • 2
    $\begingroup$ A more recent one is Tinygarble. $\endgroup$ – Mikero Oct 29 '15 at 22:11

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.