Paper 2026/1569

Tensor Encodings for SIMD HSS

Abstract

We study SIMD packing for the lattice-based homomorphic secret sharing scheme of Boyle-Kohl-Scholl (BKS) over dimension-$N$ cyclotomic rings. A trace construction with alternating tensor encodings matches the $\Theta(\sqrt N)$ packing of SIMD-HSS by Kim et al. (ePrint 2026/485). Its addition-closed mode uses $O(\log N)$ authenticated automorphisms, two BKS multiplications, and two constant multiplications; an alternating fast path roughly halves these costs. A second construction uses a three-term-progression-free slot set $A$: homomorphic traces isolate the product coefficients at $2a$ for $a\in A$, and a halving automorphism returns them to $a$. For fixed $k$ and conductor primes, with balanced prime-power factors, this packs $N^{1-o(1)}$ slots with one BKS multiplication, $O(kN^{1/(2k)})$ authenticated automorphisms, and $O(kN^{1/k})$ constant multiplications. Both constructions support standard (non-entropic) secrets. Two-party executions at 162 and 495 slots confirm the algebra and exact call counts.