SLOTHE : Lazy Approximation of Non-Arithmetic Neural Network Functions over Encrypted Data

Machine Learning as a Service (MLaaS) introduces strong privacy concerns for both clients and model providers. Fully Homomorphic Encryption (FHE) offers a promising solution by enabling inference over encrypted data, but its limited expressiveness requires approximating non-arithmetic functions (NAFs) with polynomials, often leading to significant accuracy and performance trade-offs. Existing works adopt an eager approximation (EA) strategy, which statically replaces each NAF with a fixed polynomial, locking in computational errors and limiting optimization opportunities. We propose SLOTHE, a lazy approximation (LA) solution that recursively decomposes NAF codes into arithmetic and non-arithmetic sub-functions, selectively approximating only the non-arithmetic components when required. SLOTHE introduces a tunable cost model to balance accuracy and latency, and incorporates FHE-aware optimizations to eliminate redundant computation. Implemented using CKKS, SLOTHE achieves up to 42,378× lower maximum error than EA-based works, with improved inference accuracy and latency across BERT-based transformers. SLOTHE can also be adapted for MPC-based protocols, making it a flexible tool for secure neural network inference.