ULD-Net: Enabling Ultra-Low-Degree Fully Polynomial Networks for Homomorphically Encrypted Inference

Fully polynomial neural networks—models whose computations comprise only additions and multiplications—are attractive for privacy-preserving inference under homomorphic encryption (HE). Yet most prior systems obtain such models by post-hoc replacement of nonlinearities with high-degree or cascaded polynomials, which inflates HE cost and makes training numerically fragile and hard to scale. We introduce ULD-Net, a training methodology that enables ultra-low-degree (multiplicative depth $\leq 3$ for each operator) fully polynomial networks to be trained from scratch at ImageNet and transformer scale while maintaining high accuracy. The key is a polynomial-only normalization, PolyNorm, coupled with a principled choice of normalization axis that keeps activations in a well-conditioned range across deep stacks of polynomial layers. Together with a special set of polynomial-aware operator replacements, such as polynomial activation functions and linear attention, ULD-Net delivers stable optimization without resorting to high-degree approximations. Experimental results demonstrate that ULD-Net enables stable training of low-degree fully polynomial networks on large-scale model architectures and datasets. Applying ULD-Net to ViT-Small and ViT-Base achieves 76.70\% and 75.20\% top-1 accuracy on ImageNet, respectively, which are comparable to the original models and represent the first fully polynomial models successfully scaled to the ViT/ImageNet level. Additionally, ULD-Net outperforms several state-of-the-art open-source fully and partially polynomial approaches across diverse model architectures and datasets in both accuracy and HE inference latency.