WeiDaiWD
commented
4 years ago We have planned to implement this method in future. It will speedup keyswitching related operations. It will not offer better noise reduction compared to the current method in SEAL. It should not affect the depth of circuit that each parameter set can support. It can possibly reduce keyswitching keys' sizes, but also benefits from multiple sets of keyswitching keys for different levels, which can be a trouble.
I am interested in implementing moduli chunking as I have an interest in speeding up the keyswitch operation.
I believe this would be a key step in moving to the regimes of N=2^17 and higher. Per slot, we get something close to linear rather than quadratic scaling in the number of levels with basically constant factor for the keyswitch inner loop, although ModUp still has quadratic scaling, and so needs to be monitored. This is still an overhead, but it is a more manageable overhead.
If we are talking about l = 60, we could be seeing speedups of 10-15x for some memory overhead (size of P). We may only experience a per slot slowdown of 2-3x compared to N=2^16 if we choose the right parameters (alpha/dnum).
This will allow us to evaluate very deep circuits and also support more levels/precision for bootstrapping. Hopefully, we can get bootstrapping to be carried out within 15-20 levels and have 40 after levels remaining.
(Although LT in bootstrapping reduces the number of slots we can actually use, by a factor of about 4; this is however of less concern since at least for me, I care about having more levels).
I am working on a new approximation to homomorphic modular reduction that could offer higher precision, and together with acceleration and parallelisation of the homomorphic operations whether on FPGA or GPU, we may be able to achieve practical bootstrapping, and, for one thing, evaluate deep learning models that require very deep circuits, such as LSTMs or Transformers. Each would require approximations to complicated functions like logistic function or softmax (which we could replace with spherical (or higher order polynomial) softmax).
The key concepts are as follows and have been taken from "better bootstrapping"(https://eprint.iacr.org/2019/688.pdf)
Then we compute ModDown wrt to P = product of p_i to complete flooring.
I plan to implement this for my own use first, but I would be keen to discuss the way to go around implementing this, especially for future merge. I believe the changes are limited to key generation, kskgen, and keyswitch.