google
Investigate double-hoisting for BSGS matrix vector product
The Orion paper mentions that they use double-hoisting for all their BSGS matrix vector products. One hoisting is the repeated rotations of the same vector, which can only be used to compute all the baby step rotations of the input vector. The double hoisting technique extends the technique to also be applied to the giant steps. This is described as coming Bossuat et al's paper https://link.springer.com/chapter/10.1007/978-3-030-77870-5_21
The first level, proposed by Halevi et al. [18], applies to the inner-loop rotations (line 8 of Algorithm 5). This renders the computation devoted to Decompose
independent of the value n1, so the complexity is reduced to
(n2 + n1) · (MultSum + ModDown + Permute) + (n2 + 1) · Decompose.
The second level, which we propose, introduces an additional hoisting for
the inner-loop rotations, as the ModDown step is a coefficient-wise operation.
Similarly to the Decompose step, this operation commutes with the Permute step
and the ciphertext-plaintext multiplications (line 8 of Algorithm 5). Therefore,
we need to apply it only once after the entire inner-loop of n1 rotations. Applying
the same reasoning for the ModDown step of the outer-loop rotations we can
reduce the number of key-switch operations from n1 + n2 to n2 + 1:
Coincidence? https://openfhe.discourse.group/t/how-to-implement-double-hoisting/2162
That's hilarious. I didn't realize that there was an EvalLinearTransform API in OpenFHE. It doesn't have a great docstring but from the implementation that looks like a rotate_and_reduce operation. I'm amused we recreated that API at the tensor_ext level by accident.
So maybe I can experiment with disabling the rotate_and_reduce kernel implementation and adding a pattern to lower it to that openfhe operation.
LOL, I've known for quite a while that tricyclically encoded matrix multiplications were compatible with Double Hoisting, but didn't exactly know how to implement it in OpenFHE. Thanks to Yuriy's pointers, I was able to apply it to our tricyclic matrix multiplications. No wonder that at Crypto, Yuriy told me that it was "trivial" to implement.
