# Sisyphus: A Cautionary Tale of Using Low-Degree Polynomial Activations in Privacy-Preserving Deep Learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 55 references that are in the map.
- First posted on arXiv 26 Jul 2021.

## Builds on (most cited first, 30 of 34)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://mlsanity.com/paper/1704.04861/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Self-Normalizing Neural Networks](https://mlsanity.com/paper/1706.02515/) (2017)
- [Empirical Evaluation of Rectified Activations in Convolutional Network](https://mlsanity.com/paper/1505.00853/) (2015)
- [Gazelle: A Low Latency Framework for Secure Neural Network Inference](https://mlsanity.com/paper/1801.05507/) (2018)
- [Mish: A Self Regularized Non-Monotonic Activation Function](https://mlsanity.com/paper/1908.08681/) (2019)
- [Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware](https://mlsanity.com/paper/1806.03287/) (2018)
- [Understanding and Improving Convolutional Neural Networks via Concatenated Rectified Linear Units](https://mlsanity.com/paper/1603.05201/) (2016)
- [CrypTFlow2: Practical 2-Party Secure Inference](https://mlsanity.com/paper/2010.06457/) (2020)
- [Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications](https://mlsanity.com/paper/1801.03239/) (2018)
- [Pad'e Activation Units: End-to-end Learning of Flexible Activation Functions in Deep Networks](https://mlsanity.com/paper/1907.06732/) (2019)
- [CryptoDL: Deep Neural Networks over Encrypted Data](https://mlsanity.com/paper/1711.05189/) (2017)
- [Dynamic ReLU](https://mlsanity.com/paper/2003.10027/) (2020)
- [XONN: XNOR-based Oblivious Deep Neural Network Inference](https://mlsanity.com/paper/1902.07342/) (2019)
- [DeepReDuce: ReLU Reduction for Fast Private Inference](https://mlsanity.com/paper/2103.01396/) (2021)
- [DeepSecure: Scalable Provably-Secure Deep Learning](https://mlsanity.com/paper/1705.08963/) (2017)
- [Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference](https://mlsanity.com/paper/1811.09953/) (2018)
- [Chiron: Privacy-preserving Machine Learning as a Service](https://mlsanity.com/paper/1803.05961/) (2018)
- [CryptoNAS: Private Inference on a ReLU Budget](https://mlsanity.com/paper/2006.08733/) (2020)
- [BLAZE: Blazing Fast Privacy-Preserving Machine Learning](https://mlsanity.com/paper/2005.09042/) (2020)
- [Precise Approximation of Convolutional Neural Networks for Homomorphically Encrypted Data](https://mlsanity.com/paper/2105.10879/) (2021)

## Built on by (most cited first, 14 of 14)

- [AutoReP: Automatic ReLU Replacement for Fast Private Network Inference](https://mlsanity.com/paper/2308.10134/) (2023)
- [QuadraLib: A Performant Quadratic Neural Network Library for Architecture Optimization and Design Exploration](https://mlsanity.com/paper/2204.01701/) (2022)
- [AESPA: Accuracy Preserving Low-degree Polynomial Activation for Fast Private Inference](https://mlsanity.com/paper/2201.06699/) (2022)
- [NeuJeans: Private Neural Network Inference with Joint Optimization of Convolution and FHE Bootstrapping](https://mlsanity.com/paper/2312.04356/) (2023)
- [Training Large Scale Polynomial CNNs for E2E Inference over Homomorphic Encryption](https://mlsanity.com/paper/2304.14836/) (2023)
- [Fast and Private Inference of Deep Neural Networks by Co-designing Activation Functions](https://mlsanity.com/paper/2306.08538/) (2023)
- [Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference](https://mlsanity.com/paper/2203.02833/) (2022)
- [Approximating ReLU on a Reduced Ring for Efficient MPC-based Private Inference](https://mlsanity.com/paper/2309.04875/) (2023)
- [Towards Fast and Scalable Private Inference](https://mlsanity.com/paper/2307.04077/) (2023)
- [Compact: Approximating Complex Activation Functions for Secure Computation](https://mlsanity.com/paper/2309.04664/) (2023)
- [Peregrine: One-Shot Fine-Tuning for FHE Inference of General Deep CNNs](https://mlsanity.com/paper/2511.18976/) (2025)
- [CrypTorch: PyTorch-based Auto-tuning Compiler for Machine Learning with Multi-party Computation](https://mlsanity.com/paper/2511.19711/) (2025)
- [Regularized PolyKervNets: Optimizing Expressiveness and Efficiency for Private Inference in Deep Neural Networks](https://mlsanity.com/paper/2312.15229/) (2023)
- [Private Vertical Federated Inference for Time-Series](https://mlsanity.com/paper/2605.08343/) (2026)

## Abstract (arXiv)

Privacy concerns in client-server machine learning have given rise to private inference (PI), where neural inference occurs directly on encrypted inputs. PI protects clients' personal data and the server's intellectual property. A common practice in PI is to use garbled circuits to compute nonlinear functions privately, namely ReLUs. However, garbled circuits suffer from high storage, bandwidth, and latency costs. To mitigate these issues, PI-friendly polynomial activation functions have been employed to replace ReLU. In this work, we ask: Is it feasible to substitute all ReLUs with low-degree polynomial activation functions for building deep, privacy-friendly neural networks? We explore this question by analyzing the challenges of substituting ReLUs with polynomials, starting with simple drop-and-replace solutions to novel, more involved replace-and-retrain strategies. We examine the limitations of each method and provide commentary on the use of polynomial activation functions for PI. We find all evaluated solutions suffer from the escaping activation problem: forward activation values inevitably begin to expand at an exponential rate away from stable regions of the polynomials, which leads to exploding values (NaNs) or poor approximations.