# CryptoNAS: Private Inference on a ReLU Budget

arXiv: https://arxiv.org/abs/2006.08733 · HTML: https://mlsanity.com/paper/2006.08733/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 40)

- [DeepReDuce: ReLU Reduction for Fast Private Inference](https://mlsanity.com/paper/2103.01396/) (2021)
- [Selective Network Linearization for Efficient Private Inference](https://mlsanity.com/paper/2202.02340/) (2022)
- [AutoReP: Automatic ReLU Replacement for Fast Private Network Inference](https://mlsanity.com/paper/2308.10134/) (2023)
- [LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference](https://mlsanity.com/paper/2309.14331/) (2023)
- [MPCViT: Searching for Accurate and Efficient MPC-Friendly Vision Transformer with Heterogeneous Attention](https://mlsanity.com/paper/2211.13955/) (2022)
- [Learning to Linearize Deep Neural Networks for Secure and Efficient Private Inference](https://mlsanity.com/paper/2301.09254/) (2023)
- [Circa: Stochastic ReLUs for Private Deep Learning](https://mlsanity.com/paper/2106.08475/) (2021)
- [Sphynx: ReLU-Efficient Network Design for Private Inference](https://mlsanity.com/paper/2106.11755/) (2021)
- [AdaPI: Facilitating DNN Model Adaptivity for Efficient Private Inference in Edge Computing](https://mlsanity.com/paper/2407.05633/) (2024)
- [Layer Folding: Neural Network Depth Reduction using Activation Linearization](https://mlsanity.com/paper/2106.09309/) (2021)
- [Sisyphus: A Cautionary Tale of Using Low-Degree Polynomial Activations in Privacy-Preserving Deep Learning](https://mlsanity.com/paper/2107.12342/) (2021)
- [AESPA: Accuracy Preserving Low-degree Polynomial Activation for Fast Private Inference](https://mlsanity.com/paper/2201.06699/) (2022)
- [RRNet: Towards ReLU-Reduced Neural Network for Two-party Computation Based Private Inference](https://mlsanity.com/paper/2302.02292/) (2023)
- [CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference](https://mlsanity.com/paper/2209.11904/) (2022)
- [Private and Reliable Neural Network Inference](https://mlsanity.com/paper/2210.15614/) (2022)
- [zPROBE: Zero Peek Robustness Checks for Federated Learning](https://mlsanity.com/paper/2206.12100/) (2022)
- [MPC-Minimized Secure LLM Inference](https://mlsanity.com/paper/2408.03561/) (2024)
- [Training Large Scale Polynomial CNNs for E2E Inference over Homomorphic Encryption](https://mlsanity.com/paper/2304.14836/) (2023)
- [RL-DistPrivacy: Privacy-Aware Distributed Deep Inference for low latency IoT systems](https://mlsanity.com/paper/2208.13032/) (2022)
- [Making Models Shallow Again: Jointly Learning to Reduce Non-Linearity and Depth for Latency-Efficient Private Inference](https://mlsanity.com/paper/2304.13274/) (2023)
- [PriViT: Vision Transformers for Fast Private Inference](https://mlsanity.com/paper/2310.04604/) (2023)
- [Efficient ML Models for Practical Secure Inference](https://mlsanity.com/paper/2209.00411/) (2022)
- [PolyMPCNet: Towards ReLU-free Neural Architecture Search in Two-party Computation Based Private Inference](https://mlsanity.com/paper/2209.09424/) (2022)
- [Roulette: A Semantic Privacy-Preserving Device-Edge Collaborative Inference Framework for Deep Learning Classification Tasks](https://mlsanity.com/paper/2309.02820/) (2023)
- [Disparate Impact on Group Accuracy of Linearization for Private Inference](https://mlsanity.com/paper/2402.03629/) (2024)
- [TruncFormer: Private LLM Inference Using Only Truncations](https://mlsanity.com/paper/2412.01042/) (2024)
- [ATLAS: Automated Approximation of Transformers for Efficient Homomorphic Inference in One Hour](https://mlsanity.com/paper/2607.23478/) (2026)
- [Efficient Deep Learning Using Non-Volatile Memory Technology](https://mlsanity.com/paper/2206.13601/) (2022)
- [Securing Neural Networks with Knapsack Optimization](https://mlsanity.com/paper/2304.10442/) (2023)
- [Towards Fast and Scalable Private Inference](https://mlsanity.com/paper/2307.04077/) (2023)

## Abstract (arXiv)

Machine learning as a service has given raise to privacy concerns surrounding clients' data and providers' models and has catalyzed research in private inference (PI): methods to process inferences without disclosing inputs. Recently, researchers have adapted cryptographic techniques to show PI is possible, however all solutions increase inference latency beyond practical limits. This paper makes the observation that existing models are ill-suited for PI and proposes a novel NAS method, named CryptoNAS, for finding and tailoring models to the needs of PI. The key insight is that in PI operator latency cost are non-linear operations (e.g., ReLU) dominate latency, while linear layers become effectively free. We develop the idea of a ReLU budget as a proxy for inference latency and use CryptoNAS to build models that maximize accuracy within a given budget. CryptoNAS improves accuracy by 3.4% and latency by 2.4x over the state-of-the-art.