Open j2kun opened 3 weeks ago
For reference, this is the original work on hoisting: https://eprint.iacr.org/2018/244.
I wonder to what extent CSE/canonicalization can give us (some of these) for "free"...
I wonder to what extent CSE/canonicalization can give us (some of these) for "free"...
I would assume at a low enough level it would, but only at the point that we element-wise-to-affine and unroll the loop that performs the digit decomposition and the automorphism, which is pretty low-level (but this is the poly level, so i think hardware accelerators would get that!). Otherwise, it relies on the fact that the automorphism and digit decomposition "commute" since the automorphism is a linear operator.
This would be a really useful optimization for the diagonal matrix-vector multiplication method, which needs to perform many rotations on the input vector
Not particularly about the SIMD Schemes -> Polynomial flow but for reference this is implemented in libraries other than HELib as well. Relevantly, OpenFHE includes APIs for the hoisted and optimized operations as EvalFastRotationPrecompute
and EvalFastRotation
. Here is the advanced-real-numbers.cpp example in OpenFHE.
I came across this tidbit when reading the Gazelle Paper [1]
This seems like a relevant optimization for us, particularly when we lower SIMD FHE schemes to polynomial.
[1]: Gazelle: A Low Latency Framework for Secure Neural Network Inference. Chiraag Juvekar, Vinod Vaikuntanathan, Anantha Chandrakasan. https://arxiv.org/abs/1801.05507