Gazelle & Delphi

2021-10-18

​

Agenda

• Motivation & Background
• Gazelle
• Threat Model
• Architecture Design
• Major Techniques (PAHE)
• Evaluation

​

• Delphi
• Motivation
• Major Techniques
• Evaluation
• Discussion

Background - Secure Inference

3

Private Input

(the client)

Private Trained Model

(the server / service provider)

Background - CNN

4

Linear Layers:

• Convolution Layers
• Fully Connected Layers

Non-Linear Layers:

• Activation
• Max-Pooling

Gazelle - Threat Model

5

Semi-honest

• Adhere to protocol
• Attempt to learn other party’s sensitive data

client

server

Gazelle - Security Guarantees

6

Never able to hide the network architecture 100%

​

Hides:

• Client input
• Network weights
• Filter & Stride size of convolution

​

Doesn’t hide:

• Number of layers
• Size of each layer
• Client’s Input size

Gazelle - Inefficiencies from previous work

7

Use one scheme for both linear and non-linear layers

​

• 2PC (Garbled Circuit / Secret Sharing)
• Efficient Computation
• Expensive Communication cost

​

​

• Homomorphic Encryption
• Cheap Communication
• Large Computation on server

Gazelle - Inefficiencies from previous work

8

• Garbled Circuit / Secret Sharing
• Better when generated circuit size is small / linear to input

​

​

• Homomorphic Encryption
• Better when multiplicative depth is small
• Or large circuit size (eg. quadratic to input)

Non-Linear Layers

Linear Layers

Non-Linear Layers

Linear Layers

Gazelle - Key Ideas

Switch (customized) Schemes for Linear / Non-Linear Layers!

Gazelle - Key Ideas

• For linear layer: Packed Additively Homomorphic Encryption (PAHE)

​

• For non-linear layers: Garbled Circuit

​

• Use Secret Sharing to patch different layers together and switch accordingly

​

Gazelle - Protocol Overview

11

GC to PAHE

PAHE Enc

PAHE Eval (Kernel)

PAHE to GC

PAHE Dec

Conv/FC Layer (PAHE)

C_y

[ C_y ]

S_y

[ y ] = [ C_y ] + [ S_y ]

[ x ]

[ C_x ] = [x + r]

Eval GC

Send Labels

C_x

s_x = r

{ s_x }, { s_y },

C_y

s_y

RELU Layer (GC)

Client

Server

a: plaintext

[a]: ciphertext

{a}: GC label

Gazelle - PAHE Abstraction

12

• Fit plaintext into “slot” vectors, which hold the content plus some noise for security.
• Supported Operations:
• SIMDAdd: SIMD homomorphic addition
• SIMDScMult: SIMD homomorphic scalar multiplication (between a ciphertext and a plaintext)
• Perm (Automorphism): Plaintext slots permutation, mostly just rotation

​

Gazelle - PAHE Techniques - FC Layer

13

Fast Homomorphic Matrix Multiplication, the naive way

• Setup:
• plaintext weight matrix W, shape n₀ * n_i
• Input vector v, shape n_i
• Wants to evaluate W*v
• Each slot is length n, holding some plaintext vector (plus some noise for security)

​

Gazelle - PAHE Techniques - FC Layer

14

Fast Homomorphic Matrix Multiplication, the naive way

• Process
• For each row w_i of W, pad it to length n
• SIMDScMult: [w_i * v], gives component-wise product vector, need its sum
• Rotate by half and sum
• repeat for all n₀ rows
• Cost: n₀ * SIMDScMult + n₀logn rotations + n₀logn SIMD additions
• Shortcomings:
• Produces n₀ ciphertext for one component of result
• Leads to communication quadratic to input size

Gazelle - PAHE Techniques - FC Layer

15

Fast Homomorphic Matrix Multiplication, input packing

​

• A small trick: when n_i << n, rather than wasting a lot of space padding, packing n/n_i rows into one plaintext vector, and n/n_i copies of input vector into one ciphertext vector
• Perform rotations block by block
• Now number of rows change from n₀ to n₀ * n_i / n

Gazelle - PAHE Techniques - FC Layer

16

Fast Homomorphic Matrix Multiplication, the diagonal way

• Rationale: Arrange elements in a way such that after SIMDScMult, numbers need to added together never appear in same ciphertext, saving rotation
• Process
• Encode main diagonal a vector that will later SIMDScMult with input, encode every diagonal above or below SIMDScaMult with rotated input
• Cost: n_i * SIMDScMult + (n_i-1) rotations + (n_i-1) SIMD additions, and now the output produces a single ciphertext that has the entire output vector in packed form.
• Shortcoming:
• Noise grows for some amount compared to naive method, due to doing rotation before SIMDScMult, but still acceptable.

Gazelle - PAHE Techniques - FC Layer

17

Fast Homomorphic Matrix Multiplication, the hybrid way

• In reality, weight matrix W of shape n₀ * n_i is usually rectangular, with n_i >> n₀
• For diagonal method, rotation is in n_i , not desirable
• Combine both, pack the weights along these extended diagonals into plaintext vectors
• Now we have n₀ number of input vector rotation before scalar multiplication
• Benchmarks show it almost always outperforms simple naive / diagonal

Gazelle - PAHE Techniques - Conv Layer

18

• Techniques for convolution layer is similar to FC, except some adaptations specially for the operation of convolution

Gazelle - Evaluation

19

10~20x runtime speedup

​

10~100x less bandwidth

​

​

Gazelle - Evaluation

20

10~20x runtime speedup

​

10~100x less bandwidth

​

​

Delphi - Intro

Delphi - Intro

​

• achieves semi-honest simulation-based security

​

• supports arbitrary CNNs

​

• Efficiency:
• improves bandwidth (9x) and inference latency (22x)
• can utilize GPU/TPU for linear layers
• evaluated on realistic workloads (CIFAR-100, ResNet-32)

​

Delphi - Motivation

Delphi - Major Techniques

Delphi - Major Techniques

It would be great if we can replace some RELUs with quadratic activations, which are cheap in 2PC

Using quadratic activation affects accuracy

Delphi - Major Techniques

Use Network Architecture Search to figure out the right amount of RELUs to replace while maintaining certain accuracy threshold!

Delphi - Architecture

Delphi - Evaluation

Delphi - Evaluation

Clarifying Questions

​

• How does model training work in this setting? Does it just proceed in the non private approach.

​

• This might be out of scope of this paper, but are arithmetic circuits or boolean circuits better for matrix multiplication? I would assume that arithmetic circuits are better for multiplication. If my assumption is correct, why do the authors use boolean circuits for their kernels and non-linear layers?

​

Discussion Questions

​

• Could this system be used for non linear networks? (iex, l1 = f1(x), l2 = f2(l1), l3 = f3(l1,l2))

​

• The authors only consider semi-honest corruptions. Can their protocol be compiled into a malicious-secure protocol without incurring too many zero knowledge proofs (the GMW compiler would require one proof per message)?

​

• Why do the authors use a boolean circuit when evaluating the non-linear layer instead of using the proposed methods from SecureML (mpc friendly activation functions + arithmetic circuits). What are the trade-offs here?

​

• The paper mainly mentions the model with one client and one server. However, in many modern use cases, many users can share the same ML model by contributing their input data securely. How well does Gazelle apply to that setting?