Paper 2025/805

Accelerating Multiparty Noise Generation Using Lookups

Abstract

We propose a novel method for using lookup tables (LUTs) in multiparty noise sampling which allows using smaller and/or fewer LUTs compared to previous work (Franzese et al., CCS'25, and Kii et al., PETS'25), leading to efficiency improvements of several orders of magnitude. This is primarily achieved by not evaluating the LUTs at uniformly random indices but rather using a non-uniform index distribution that can be sampled efficiently. Our method is largely distribution-agnostic, and we demonstrate its flexibility by approximating the discrete Laplace and Gaussian distributions (for a wide range of parameters) to a negligible statistical distance. Our concrete implementation, based on 3-party replicated secret sharing, achieves sub-kilobyte communication and millisecond-level computation. Amortized over 1000 discrete Laplace or Gaussian ($\sigma \leq 1000$) samples, we require just 619 bytes of communication (constituting over two orders of magnitude less communication than all previous work) and under 2 ms per party in the semi-honest setting, in all considered network configurations. With recently proposed batched multiplication checks, the malicious setting adds less than 1 byte and 5 ms per sample (amortized). Offering potential independent value, our open-source implementation also extends LUT communication trade-offs (Morita et al., USENIX'25), thus enabling more efficient evaluation of larger LUTs. Further, the merits of our sampling method are not contingent on the above MPC setting and we give analytical performance estimations for use with other MPC machinery, which indicate that it widely is a competitive alternative, especially for somewhat concentrated distributions.