Designing CNNs for Secure Inference

TrustML Workshop @ UBC

Vishnu Boddeti

June 23, 2023

VishnuBoddeti

Progress In Machine Learning

Speech Processing

Image Analysis

Natural Language Processing

Physical Sciences

Key Driver Data, Compute, Algorithms
Widespread deployment in the real-world.

Privacy and Security Requirements in AI

...consent should be given for all purposes...

Privacy Preserving Machine Learning

Mechanism: neural network inference on encrypted data

Homomorphic Encryption: The Holy Grail?

Cryptographic scheme needs to allow computations directly on the encrypted data.

Solution: Homomorphic Encryption
Attractive Property: Conjectured to be post-quantum secure for appropriate choice of encryption parameters.

Fully Homomorphic Encryption (FHE)

It is a public-key encryption system. Represents numbers over cyclotomic polynomial rings.

Operations Supported by FHE

Addition: $\bm{c} \oplus \bm{c}^\prime \cong \bm{m} + \bm{m}^\prime$
Multiplication: $\bm{c}\otimes \bm{c}^\prime \cong \bm{m} \odot \bm{m}^\prime$

Supports only $L$ sequential multiplications
Bootstrapping refreshes multiplicative depth of 0-level ciphertext.

Rotation: $\mathrm{Rot}(\bm{c}, l) \cong \mathrm{Rot}(\bm{m}, l)$

Constraints Imposed by FHE

Non-linear activation functions, like ReLU, are not supported.
Needs boostrapping for evaluating deep neural networks

FHE Characteristics: Asymmetric Complexity

Primary Bottleneck: Bootstrapping

Evaluating a deep neural network necessitates bootstrapping
Bootstrapping dominates latency ($\mathbf{>70\%}$ of execution time)

CNNs under FHE

Operations	Support
Conv2D	✓
BatchNorm2D	✓
AvgPool	✓
Linear	✓
ReLU	❌
Bootstrapping	✓

Polynomial Approximation of ReLU

Low-Degree: Levels $\Downarrow$, precision $\Downarrow$

Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference

High-Degree: Levels $\Uparrow$, precision $\Uparrow$

Precise Approximation of Convolutional Neural Networks for Homomorphically Encrypted Data

Existing Work: Polynomial Approximation of ReLU + Bootstrapping

Homomorphic evaluation architecture of ResNets

Experimental results on CIFAR datasets

High-degree polynomials $\rightarrow$ Levels $\Uparrow \rightarrow$ Bootstrapping $\Uparrow \rightarrow$ Latency $\Uparrow$

High-degree polynomials $\rightarrow$ Approximation Precision $\Uparrow \rightarrow$ Accuracy $\Uparrow$

Low-Complexity Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions, ICML 2022

Limitations of Existing Work

Manually Designed FHE Evaluation Architecture

Precise approximation of ReLU function.
Same ReLU approximation is used for all layers.
Every ResBlock has bootstrapping layer.
Evaluation architecture specialized for ResNets.

Our Key Insight

Approximate the
end-to-end function represented by the network
instead of the activation function.

Our Approach

Jointly replace all ReLU layers with polynomials to approximate end-to-end network.

Conflict between Latency and Accuracy

Latency

Low-degree Polynomials $\rightarrow$ Level Consumption $\Downarrow \rightarrow$ Bootstrapping $\Downarrow \rightarrow$ Latency $\Downarrow$

Accuracy

High-degree Polynomials $\rightarrow$ Approximation Precision $\Uparrow \rightarrow$ Accuracy $\Uparrow$

Bi-Level Multi-Objective Framework

✅ Layerwise Polynomials ✅ Diverse Solutions ✅ Better Trade-off Fronts

Framework Overview

Full Search Algorithm

MOCoEv: Multi-Objective CoEvolutionary algorithm searches for layerwise polynomials
R-CCDE: Regularized Cooperative Coevolution Differentiable Evolution optimizes coefficients
PAT: Polynomial-Aware Training can avoid gradient exploding due to polynomials

✅ Forward: Evaluate Polynomials ✅ Backward: Evaluate ReLU

Flexible Homomorphic Encryption Architecture

Evolving Composite Polynomials

EvoReLU: a composite polynomial

$\mathrm{EvoReLU}(x)=x\cdot(0.5+p^d(x))$ by using $\mathrm{ReLU}(x)=x\cdot(0.5+0.5\cdot\mathrm{sgn}(x))$
Composite polynomial $p^d(x)=(p_K^{d_K}\circ\cdots\circ p_2^{d_2}\circ p_1^{d_1})(x)$
Sub-polynomial $p_k(x)=(1/\beta_k)\sum_{i=1}^{d_k} \alpha_i T_i(x)$, $T_i(x)$ is Chebyshev basis
Search for number of sub-polynomials $K$, degrees $\{d_k\}_{k=1}^{d_K}$ and coefficients $\{\bm{\alpha}_k, \beta_k\}_{k=1}^K$

Search Variables

Variable	Options
# polynomials $(K)$	6
poly degree $()d_k$	{0,1,3,5,7}
coefficients $(\Lambda)$	$\mathbb{R}$

Search Space

High-dimensional multi-objective optimization
Extremely large search space

Backbone	# EvoReLU	# Sub-polynomial	Search Space Size
ResNet-20	19	114	$10^{79}$
ResNet-32	31	186	$10^{130}$
ResNet-44	43	258	$10^{180}$
ResNet-56	55	330	$10^{230}$

AutoFHE: Bi-Level Multi-Objective Search

AutoFHE: Better Trade-off

AutoFHE: Better Trade-off under RNS-CKKS FHE

AutoFHE: Automated Adaption of CNNs for Efficient Evaluation over FHE, Cryptology ePrint Archive 2023.
FHE-MP-CNN: Low-Complexity Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions, ICML 2022

AutoFHE: Layerwise Polynomials

Summary

Neural networks need to be redesigned for operating on encrypted data.
Manual design of architecture is difficult, sub-optimal and time-consuming.
Multi-Objective optimization is an attractive and effective solution in practice.