Bootstrapping AutomorphismKey keys exceeds maximum protobuf size of 2GB

This issue was created from bootstrapping AutomorphismKey keys is Exceeded maximum protobuf size of 2GB · Issue #360 · openfheorg/openfhe-development · GitHub

yspolyakov commented 2 weeks ago

@604254229 Could you provide more information about the bug? What environment are you using? What computation are performing? What code are you running? Basically all the information that is needed to recreate the issue.

604254229 commented last week

@yspolyakov I am using Protobuf messages to store and transmit AutomorphismKey over the network, but when EvalBootstrapKeyGen is called, the size of AutomorphismKey grows significantly and exceeds the Protobuf serialization size limit. I would like to ask if there are any plans to optimize and reduce the size of the BootstrapKey in the OpenFHE project, or if there are any other suggestions for using bootstrapping serialization functionality

First, I want to confirm. Are you serializing each automorphism key separately or you are trying to serialize the full map (all keys) at once? You would need to use the former approach.

One automorphism key requires roughly 16 \ell d_{num} N\left(1 + \frac{1}{d_{num}}\right) bytes, where \ell is the number of RNS limbs (close to multiplicative depth), d_{num} is the number of digits in hybrid key switching (by default set to 3), and N is the ring dimension (using 2^{16} or 2^{17}). You can estimate the size of each key for your setting from this. It should not be higher than 1GB for all practically reasonable settings.

If you need more granular serialization, you could serialize each DCRTPoly separately (size is reduced by 2 \ell \left(1 + \frac{1}{d_{num}}\right)). You would need your custom serialization logic for this.

I agree with @ypolyakov, in addition , we try to generate only the rotation keys we really need. Generating keys for all slot rotations will lead to thousands of keys.

@ypolykov, do we have a code example for serializing the keys sepearately and then rebuilding the keymap on the other end? Sounds like a useful function to add, though it would imply organizing many serialized files.

Hello @ypolyakov, sorry if I bring this up.

I was just wondering where can I find some hints on the 16 \ell d_{num}N(1 + \frac{1}{d_{num}}) formula. I am struggling to find how an Automorphism Keys is built in CKKS in the HKS setting.

Thank you!

I suggest reading Appendix B of Revisiting Homomorphic Encryption Schemes for Finite Fields (see, for instance, the tables at the end).

1 Like