In this paper they introduce a way to balance the complexity and required levels for the homomorphic application of a linear transformation. I see that this is implemented here but as a predetermined value rather than something that is automatically calculated with the method described in the paper. Will such a thing ever get implemented or am I totally misreading the paper?
OpenFHE also uses hoisting and double hoisting, which are not considered in the cited paper. Hence, the complexity tradeoff may be quite different. Moreover, in some cases the goal is to reduce the number of evaluation (rotation) keys rather than achieve the best computation complexity. It is up to the user of OpenFHE to decide what is more important for their use case. This is why OpenFHE does not compute the level budget automatically.
1 Like
Thank you for the enlightening answer. The hoisting and double hoisting you mention are from the paper “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys,” is that correct?
Yes, these techniques are described in the cited paper. However, hoisting was originally proposed in an earlier paper (Faster Homomorphic Linear Transformations in HElib)
1 Like