SMOOTHIE: (Multi-)scalar Multiplication Optimisations On TFHE

The (Multi-)Scalar multiplication is a crucial operation in numerous FHE-related applications, and its performance has a significant impact on their overall efficiency. This paper presents SMOOTHIE: (Multi-)Scalar Multiplication Optimisations On TFHE, introducing new techniques to improve the performance of single- and multi-scalar multiplications in TFHE. We show that the bucket/Pippenger method, rooted in the elliptic curve field, can be successfully adapted to TFHE when combined with new optimisations that address their inherent differences. We propose a new negation with offset technique that eliminates direct carry propagation after ciphertext negation. Additionally, we introduce a bucket merging technique for the bucket aggregation step, which exploits TFHE properties to reduce bootstrap operations. Specifically, in the multi-scalar multiplication case, we implement a bucket doubling method that eliminates the need for precomputation on each input ciphertext. Our implementation is integrated in the TFHE-rs library and achieves up to $\times2.05$ speedup for single-scalar multiplication compared to the current state-of-the-art, with multi-scalar multiplication improvements up to $\times6.43$, depending on the vector sizes.