Suppose I want to use LTV scheme from this paper https://eprint.iacr.org/2013/094.pdf to compute homomorphically a function. But the multiplication operation is more expensive than the additive one. So, if multiplication is the counterpart of an AND gate and addition is the counterpart of an OR gate, why not implement an AND gate as a combination of OR and NOT gates and MAYBE the resulting operation will be faster. But how should I image a NOT gate for the LTV scheme ? Or maybe the problem I formulate is simpler : how to toggle a bit homomorphically for this scheme? How to toggle a bit homomorphically for othe schemes (like BGV) ?

  • $\begingroup$ Be very careful, MULT is AND gate (and ADD is OR gate) only for bit level operations. Homomorphism is not defined for NOT gates in general to simulate AND using OR and NOT. At bit level NOT gate is additive inverse $\endgroup$
    – sashank
    Oct 28 '15 at 12:37
  • $\begingroup$ Can someone explain the approach suggested by this paper eprint.iacr.org/2014/816.pdf "Bootstrapping in less than a second"? They designed a fast and efficient NAND gate and I suppose they use it to build AND and OR gates. But it is very possible my insight about it is not the correct one. So any clarification would be highly appreciated. They also build a library which can be found here : github.com/lducas/FHEW. $\endgroup$ Oct 28 '15 at 13:19
  • $\begingroup$ please create a separate question for this $\endgroup$
    – sashank
    Oct 28 '15 at 14:20
  • $\begingroup$ I did so, thank you for your suggestion. Here I just wanted to ask if it is possible to do something similar for LTV scheme. $\endgroup$ Oct 28 '15 at 14:33
  • 1
    $\begingroup$ OR is not an addition. The addition is XOR. In order to ensure that true and true returns true, you need to have something like $A + B + AB$. Which also contains a multiplication. NOT gates are easy: Just use XOR and the constant 1 $\endgroup$
    – tylo
    Oct 28 '15 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.