LUTless: Local Initial Approximation for Secure Power Function in Private Machine Learning

The proliferation of deep learning service in privacy-sensitive domains demands frameworks that balance efficiency with model performance. However, modern secure multiparty computation (MPC) protocols struggle with prohibitive communication costs when evaluating non-linear operators essential to state-of-the-art architectures-specifically, Gaussian Error Linear Units (GeLU)/ReLU, Softmax, and LayerNorm in Transformers and CNNs. These functions often requires iterative power computations <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(x) = x^{1/a}$</tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$a \in \mathcal {Z}_{\ne 0,1}$</tex-math></inline-formula>, force a critical trade-off: precision-driven methods like Look-Up Tables (LUTs) require <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(2^\lambda )$</tex-math></inline-formula> (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda$</tex-math></inline-formula> is bit-length) communication per approximation to preserve model accuracy, while efficiency-driven approaches using low-degree polynomials sacrifice accuracy on complex tasks due to unbounded approximation errors. To address these challenges, we propose LUTless, a novel method for secure power function that eliminates communication-intensive LUT operations while maintaining results accuracy by transferring communication load to local calculation during initial approximation. Our approach introduces double approximation technique that take advantage of the linear approximation of logarithm function and exponent approximation, successfully transfer heavy communication to local computation by reformulating power function. To meet the approximation requirements, we propose share flooding, a technique that pre-generates and securely masks shares to meet approximation requirements while preserving privacy. LUTless demonstrates broad applicability across machine learning tasks, including Transformer-based language models and CNNs. Evaluated on GLUE benchmark datasets for both encoder and decoder-based models, LUTless reduces communication by up to 3.9× and achieves 3.5× speedups while maintaining competitive accuracy compared to prior Transformer based inference works. For CNN inference, experiments with frameworks such as Cheetah and CrypTFlow2 demonstrate 2×<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim 6.9\times$</tex-math></inline-formula> speedup and 1.6×<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim 9.7\times$</tex-math></inline-formula> communication saving. Our results underscore the potential of LUTless to advance efficient and scalable privacy-preserving service across diverse applications.