  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.
