Can't get Galois Keys for poly_mod_degree 2048

[kshehata]

Hi there! I'm trying to update write a version of PIR that uses the new SEAL (similar to SealPIR). To do so, it would be optimal if we could use a poly mod degree of 2048. Problem is that I can't seem to find any parameters that allow that. I'm using the BFVDefault values for the coefficient modulus and PlainModulus::Batching() with every value from 2 to 80 bits, but either there aren't enough qualifying primes, or I get "keyswitching is not supported by the context". Is this no longer supported?

[kimlaine]

SealPIR depends on an older version of SEAL that uses a different kind of key switching technique. The current approach requires you to have at least two primes in your coeff_modulus, one of which is used only for keys and doesn't add to the ciphertext modulus. Basically you have less noise budget for your ciphertexts. There are important reasons for doing this, however: relinearizations and rotations consume almost no noise budget now. We also use the extra prime to encrypt fresh ciphertexts at a higher level and modulus switch them down to lower their noise. In CKKS this matters because you get more accuracy from the start.

With n=2048 the coeff_modulus bound is very low so it's not easy to split that into a key prime and a ciphertext prime and still be able to do much meaningful computing. I wouldn't be surprised if SealPIR will require a switch to n=4096 to work with newer versions of SEAL.

[kshehata]

So basically, n=2048 is no longer supported for this? That's a shame, since for PIR that makes the minimum size for returned values much larger.

[WeiDaiWD]

When you create an EncryptionParameters with 2048 and a single prime (BFVDefault), you get "key switching is not supported. There are two ways to make it work.

1. Modify SEAL's code to roll back to the old behavior. (very complicated)
2. Provide two primes that have in total 54 bits and make the second prime as small as possible (12289 is the smallest prime that supports NTT or batching).

Comparing the second method with the old SEAL, you will have 2~4 times slower HE evaluation, less but non-negligible noise growth from keyswitching, less noise budget at the beginning, and unclear noise budget after computation. It might work if noise growth is well controlled, where the choice of a small PlainModulus helps. The slowdown of HE evaluation may be less since SEAL's performance has been improved.

On the other hand, using 4098 will likely only increase communication cost by 2 times compared to using 2048. SEAL's serialization methods use ZLIB for compression. Given that noise growth is less affected by poly_modulus_degree, you will have a similarly sized coeff_modulus with either 2048 or 4096 after HE computation. Compression then discards trailing zeros in each coefficient.

[s0l0ist]

Something to keep in mind performance suffers greatly when ZLIB is enabled in @kshehata's PIR implementation.

Having the ability to easily tune ZLIB's settings would be a huge advantage.

So while enabling compression decreases the serialized size, computational performance suffers too much to keep it enabled.

[kshehata]

I've managed to use Wei's approach 2 above by setting PlainModulus::Batching(2048, 16) and CoeffModulus::Create(poly_mod_degree, {40, 14}). With that I can now create encrypt and decrypt a CT. The decryptor shows 17 bits of invariant noise budget, but the moment I try to multiply a PT encryption of 1 (similar to PIR selection vector) all of the noise budget disappears. Any idea what's going on?

[WeiDaiWD]

@s0l0ist We'll spend some time on optimizing the slow compression. It is truly annoying.

@kshehata It basically means that noise growth in multiply_plain is larger or equal to 17 bits. Noise growth of multiply_plain is roughly 16 (plain modulus bit size) plus 5.5 (half of log 2048). You have to roll back SEAL's code then. I'm not sure whether we will add an option to turn on / off this behavior (special modulus) since the CKKS scheme benefits a lot from it. Once we do, it will be clearly stated in release note.

[kshehata]

That's likely to be more complicated than I can dedicate to this project. Let me know if you decide to implement that switch, otherwise we'll stick to 4096 for now, though it might make this application out of reach for practical applications.