exchanging plaintext values while encrypted from p=2 to p>2

[jimboz]

Is it possible in HElib to exchange plaintext values between ciphertexts from a plaintext space of p=2 to one with a higher p (say 127) without decrypting first? Stated in another way, could the plaintext value of a ciphertext under p=2 be somehow converted to a higher plaintext space of p>2 and still recover the correct value?

This to me would be quite a useful capability, for instance, to first perform binary calculations (under GF(2)) and then (after conversion) perform calculations under a higher p without having to decrypt first.

Thank you.

[shaih]

No, this is not possible, except perhaps in the narrow case where the larger plaintext space is mod-2^r for some r.

In theory it should be doable to switch between different plaintext spaces using bootstrapping. But actually implementing it will take a lot more research. One issue is that the algebra of mod-2 and mod-p plaintext spaces is quite different, so things like the number of plaintext slots will change.

For the special case of switching from mod-2 to mod-2^r, in principle all you need is to square your ciphertexts, and then it will maintain its value but enlarge the plaintext space from 2^e to 2^{e+1}. However (a) I am not sure that HElib now has the interface for actually recognizing the larger plaintext space (I will check this soon), and (b) you will need to use the larger plaintext space when creating key-switching matrices during key generation. (Specifically, you will need to initialize the FHEcontext object with the larger 'r' parameter.)

[jimboz]

Thank you kindly Shai for your detailed response.

I suspected this might be the case given, as you say, the FHE contexts/slots would be different between p=2 and p>2, and HElib manages the two cases quite differently. I was also aware that the plaintext space is normally increased during recryption, so it was worthwhile getting confirmation from you and understanding HElib's requirements for enabling the specialised case of switching from mod-2 to mod-2^r. Any further tips you may have on this in due course would be appreciated.

Thanks again.

[boev]

I have asked myself the same question: can I do calculations in binary and use the results ( which are ciphertexts representing encryptions of 0 or 1) in multiplications with Integers (encrypted numbers with plaintext 2^32). I do not understand the proposed solution where squaring lifts 2^1 to 2^r. First, if I had to initialize my Context with higher r (r=32), then I would lose all the benefits of staying in binary (fast computations/smaller coeff/mod-2-arithmetic are all gone). Second, won't squaring add to my noise as I need to do it a couple of times? This means that L needs to increase, which hurts performance. So it's even worse than just calculating all integer from the start. Long story short: as I understand it, this is currently not efficiently possible without decryption and re-encrypting using different context.

[shaih]

That's a fair summary. Changing plaintext spaces can be useful in special situations (e.g., it is used inside bootstrapping), but with current techniques it is not something that has much of a general-purpose applicability.

[jimboz]

Could you please expand on that last statement which confused me: '...but with current techniques it is not something that has much of a general-purpose applicability.' I thought changing plaintext spaces without decryption has huge potential, which is why I originally posted the question. Being able to mix binary logic (comparisons, equality) together with fast multiplication and addition over word-based plaintext spaces (rather than using slow binary methods) has significant general purpose application. Currently, it is only an either/or proposition. The potential is also discussed as a challenge in a paper you co-authored: https://eprint.iacr.org/2018/202.

[boev]

Yes, of course it has great performance potential to do binary and then integer, even more general - do every calculation in the smallest plaintext space possible. The Problem is that your context needs to be initialized in such a way that it needs to support the biggest plaintext space you would use, which eliminates the boost in performance, the mod-calculations. So for me "...but with current techniques it is not something that has much of a general-purpose applicability." means that with current implementation and embedding one can't really perform such plaintext switching. Such step could be incorporated in a 'special' bootstrapping procedure, but currently this also is not the case and in general bootstrapping is slow and undesirable in the first place. I have used following two strategies to do calculations: Strategy 1: binary all the way -> just use bit-by-bit encryption and do + and * in binary mode. It is a bit painful, but it works. Strategy 2: Do binary inside integer -> you do stay in 0 and 1 with careful calculations e.g. not relying on mod-2.

[jimboz]

Thanks boev..that makes sense and thanks for the strategy tips.