# Securing Neural Networks with Knapsack Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 20 Apr 2023.

## Builds on (most cited first, 26 of 26)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Rethinking Atrous Convolution for Semantic Image Segmentation](https://mlsanity.com/paper/1706.05587/) (2017)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression](https://mlsanity.com/paper/1707.06342/) (2017)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [Gazelle: A Low Latency Framework for Secure Neural Network Inference](https://mlsanity.com/paper/1801.05507/) (2018)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [FALCON: Honest-Majority Maliciously Secure Framework for Private Deep Learning](https://mlsanity.com/paper/2004.02229/) (2020)
- [Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications](https://mlsanity.com/paper/1801.03239/) (2018)
- [CrypTFlow: Secure TensorFlow Inference](https://mlsanity.com/paper/1909.07814/) (2019)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [DeepReDuce: ReLU Reduction for Fast Private Inference](https://mlsanity.com/paper/2103.01396/) (2021)
- [Structural Pruning via Latency-Saliency Knapsack](https://mlsanity.com/paper/2210.06659/) (2022)
- [CryptoNAS: Private Inference on a ReLU Budget](https://mlsanity.com/paper/2006.08733/) (2020)
- [Selective Network Linearization for Efficient Private Inference](https://mlsanity.com/paper/2202.02340/) (2022)
- [Coreset-Based Neural Network Compression](https://mlsanity.com/paper/1807.09810/) (2018)
- [FALCON: A Fourier Transform Based Approach for Fast and Secure Convolutional Neural Network Predictions](https://mlsanity.com/paper/1811.08257/) (2018)
- [Knapsack Pruning with Inner Distillation](https://mlsanity.com/paper/2002.08258/) (2020)
- [Circa: Stochastic ReLUs for Private Deep Learning](https://mlsanity.com/paper/2106.08475/) (2021)
- [Blind Faith: Privacy-Preserving Machine Learning using Function Approximation](https://mlsanity.com/paper/2107.14338/) (2021)
- [Crypto-Oriented Neural Architecture Design](https://mlsanity.com/paper/1911.12322/) (2019)
- [Reducing ReLU Count for Privacy-Preserving CNN Speedup](https://mlsanity.com/paper/2101.11835/) (2021)

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

- [DeepShare: Sharing ReLU Across Channels and Layers for Efficient Private Inference](https://mlsanity.com/paper/2512.17398/) (2025)

## Abstract (arXiv)

MLaaS Service Providers (SPs) holding a Neural Network would like to keep the Neural Network weights secret. On the other hand, users wish to utilize the SPs' Neural Network for inference without revealing their data. Multi-Party Computation (MPC) offers a solution to achieve this. Computations in MPC involve communication, as the parties send data back and forth. Non-linear operations are usually the main bottleneck requiring the bulk of communication bandwidth. In this paper, we focus on ResNets, which serve as the backbone for many Computer Vision tasks, and we aim to reduce their non-linear components, specifically, the number of ReLUs. Our key insight is that spatially close pixels exhibit correlated ReLU responses. Building on this insight, we replace the per-pixel ReLU operation with a ReLU operation per patch. We term this approach 'Block-ReLU'. Since different layers in a Neural Network correspond to different feature hierarchies, it makes sense to allow patch-size flexibility for the various layers of the Neural Network. We devise an algorithm to choose the optimal set of patch sizes through a novel reduction of the problem to the Knapsack Problem. We demonstrate our approach in the semi-honest secure 3-party setting for four problems: Classifying ImageNet using ResNet50 backbone, classifying CIFAR100 using ResNet18 backbone, Semantic Segmentation of ADE20K using MobileNetV2 backbone, and Semantic Segmentation of Pascal VOC 2012 using ResNet50 backbone. Our approach achieves competitive performance compared to a handful of competitors. Our source code is publicly available: https://github.com/yg320/secure_inference.