0
$\begingroup$

I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure.

Especially, they mentioned that we could change this algorithm to a more "general" one that would allow to check the membership for different subsets of integers $\bmod t$ in only one refresh procedure. However, I can't find an "efficient" approach to this problem (the one I have in mind needs more than one refresh).

Does any of you have some "hint" to guide me to the right direction?

P.S. They also mentioned a xor-for-almost-free procedure if the plaintext modulus is turned to $t=6$. I don't really understand that as - I believe - it perfectly works with $t = 4$ with the subset $S = {1;3}$. If I am wrong, please let me know.

Improve this question
$\endgroup$
1
$\begingroup$

There are to my knowledge two articles that develop further on generalized member test (or even function) extraction, I hope this may help you out:

https://link.springer.com/chapter/10.1007/978-3-319-22174-8_7 and https://eprint.iacr.org/2017/996.pdf

A small difference there is that the ring dimension is a prime rather than a power of 2, and this eliminates the symmetry constraint.

I think you are right about the XOR almost for free working also for $t=4$, though it may require to change other parameters to get the error bound right. As for the almost-free part, note that you could extract both the carry and the xor out of the same ciphertext, and the extraction part is much cheaper than the rest of the loop: you get both bit out for essentially one refresh.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you very much for these two links! Regarding the xor issue, wouldn't we get the same problem (about error treshold) with t=6? As you mentioned in your paper ''arbitrary large xor operations'', I feel like even with t=6 we should take care of the number of gates per refreshing procedure... $\endgroup$ – Binou Jan 16 '19 at 2:32
  • $\begingroup$ Yes, error would grow as $O(k)$ (or even $O(\sqrt k)$ assuming independence), but much less than for arbitrary gates where it grows as $O(2^k)$. $\endgroup$ – LeoDucas Jan 16 '19 at 6:14
  • $\begingroup$ I've got another question rising by reading the second link you gave. They changed your scheme (mostly by taking a prime $t$ and a dimension $N = p^k$ with $p > 2$ prime. I was wondering if you think it's possible (according to the "future work" part of your initial paper) to keep $N = 2^k$ and $t = 6$ for computing an $add-with-carry$ for example. Thank you for all your answers. $\endgroup$ – Binou Jan 21 '19 at 2:46
  • $\begingroup$ Yes, possible, but maybe not optimal in term of efficiency, because the next power of 2 is so far... $\endgroup$ – LeoDucas Jan 21 '19 at 8:39
  • $\begingroup$ May I ask another question, concerning a membership test in the refreshing procedure. I actually don't see how we could do it with a power of 2 conductor as, in this case, we won't be able to have an inner product of some vecteur test $t$ and our vector $Y^v$ that will give what we want (as our vector $Y^v$ has only one nonzero coefficient that is either 1 or -1 with a power of two conductor)... Am I missing something? $\endgroup$ – Binou Feb 7 '19 at 5:29

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.