Yet another way to squeeze more SIMD into BKS HSS: tensor encodings, authenticated automorphisms, and a near-maximal pack.
3 comments
The part I’d worry about is the automorphism key set, since once you start tensoring the ring structure the number of rotations you need can creep up fast and eat the SIMD win in memory. Near-maximal packing looks nice on paper, but if the key material or relin cost scales with the tensor dimensions it can get cramped pretty quickly.
> packs $N^{1-o(1)}$ slots
That asymptotic sounds nice, but in an HSS setting the thing that usually matters is the key material and rotations, and here you still pay $O(kN^{1/(2k)})$ automorphisms plus a pile of constant multiplies. For anything I’d actually want to run, “near-maximal” is probably just a fancy way of saying the constants got shoved out of sight.
I kept thinking of this against the usual CKKS batching story, and the win here is that you’re squeezing more structure out of the encoding itself instead of just hoping the slots line up nicely. The tradeoff is the same annoying one as always, more machinery around automorphisms and the key set, so it feels better for throughput-heavy HSS than for anything where you care about small setup or a short evaluation key.