# Refreshing Procedure in FHEW: membership test

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.

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.
• 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)$. – LeoDucas Jan 16 '19 at 6:14
• 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. – Binou Jan 21 '19 at 2:46
• 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? – Binou Feb 7 '19 at 5:29