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