PrivCirNet: Efficient Private Inference via Block Circulant Transformation
Authors: Tianshi Xu
Lemeng Wu
Runsheng Wang
Meng Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Privacy-preserving deep learning
Homomorphic encryption
Circulant matrices
Primary area: privacy

Abstract: Homomorphic encryption (HE)-based deep neural network (DNN) inference protects data and model privacy but suffers from significant computation overhead. We observe transforming the DNN weights into circulant matrices converts general matrix-vector multiplications into HE-friendly 1-dimensional convolutions, drastically reducing the HE computation cost. Hence, in this paper, we propose PrivCirNet, a protocol/network co-optimization framework based on block circulant transformation. At the protocol level, PrivCirNet customizes the HE encoding algorithm that is fully compatible with the block circulant transformation and reduces the computation latency in proportion to the block size. At the network level, we propose a latency-aware formulation to search for the layer-wise block size assignment based on second-order information. PrivCirNet also leverages layer fusion to further reduce the inference cost. We compare PrivCirNet with the state-of-the-art HE-based framework Bolt (IEEE S\&P 2024) and HE-friendly pruning method SpENCNN (ICML 2023). For ResNet-18 and Vision Transformer (ViT) on Tiny ImageNet, PrivCirNet reduces latency by $5.0\times$ and $1.3\times$ with iso-accuracy over Bolt, respectively, and improves accuracy by $4.1$\% and $12$\% over SpENCNN, respectively. For MobileNetV2 on ImageNet, PrivCirNet achieves $1.7\times$ lower latency and $4.2$\% better accuracy over Bolt and SpENCNN, respectively. Our code and checkpoints are available on Git Hub.

PrivCirNet: Efficient Private Inference via Block Circulant Transformation
Tianshi Xu
Lemeng Wu Meta, Inc. Imwu@meta
Peking University
tianshixu@stu pku. edu. cn
Runsheng Wang Peking University wang@pku. edu.
Meng Li
Peking University meng 1i@pku edu.
Abstract
Homomorphic encryption (HE)-based deep neural network (DNN) inference pro- tects data and model privacy but suffers from significant computation overhead. We observe transforming the DNN weights into circulant matrices converts gen- eral matrix-vector multiplications into HE-friendly 1-dimensional convolutions, drastically reducing the HE computation cost. Hence, in this paper, propose PrivCinNet, protocol/network co-optimization framework based on block circu- lant transformation. At the protocol level, PrivCirNet customizes the HE encoding algorithm that is fully compatible with the block circulant transformation and re- duces the computation latency in proportion the block size. At the network level, we propose a latency-award aware formulation search for the layer-wise block size assignment based second-order information. PrivCirNet also leverages layer fusion to further reduce the inference cost. We compare PrivCirNet with the state- of-the-art HE-based framework Bolt (IEEE S&P 2024) and HE-friendly pruning method SpENCNN (ICML 2023). For ResNet- 18 and Vision Transformer (ViT) on Tiny IeageNet, PrivCirNet reduces latency by 5.0x and 1.3x with iso-accuracy over Bolt, respectively, and improves accuracy by 4.1% and 12% over SpENCNN, respectively. For MobileNetV2 latency and 4. 4.2% better accuracy over Bolt and SpENCNN, respectively. Our code and checkpoints are available on Git Hub.
ImageNet, PrivCirNet achieves 1.7x lower
Introduction
The past few years have witnessed the rapid evolution of deep learning (DL) as well as its increasing adoption in sensitive and private applications, including face authentication [1], medical diagnosis [2], code auto-completion [3], etc. Privacy emerges as a major concern and leads to a growing demand promising technology for privacy protection and attracts a lot of attention [8, 9, 10, 7]. By encrypting the data into ciphertexts, HE allows computation over the encrypted data directly and produces encrypted results, without leaking any knowledge of the data itself [8].
for privacy-pin preservnn DL. [4, 5, 6, 7]. Homomorphic encryption (HE) is proposed
To apply HE for private deep neural network (DNN) inference, there are two main approaches,
including the end-to-end HE-based schemes [8. 11, 12, 13, 14, 15, 16, 17, 18] and the hybrid HE/multi-pare parry computation (MsC)- schemes [7, 10, 19, 20, 21, 22, 23]. As shown in Figure (a), the hybrid HE/MPC scheme leverages HE and MPC protocols to evaluate the lincar
"Corresponding author: meng. @wi.gll@pkuceeo pku..edu.cn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

block
1
(H1)
Latong b)
convelation
IMP
NoniLincon Lieer
Dulpat
(4) Hybrid HE/MPC
seno (c) Latency breakdown of linear layers
framework
(b) Latency breakdown
(d) GEMY with a circulant weight matris
Figure I: (a) Illustration of Hybrid HE/MPC- private inference; (b) latency breakdown of linear layers and nonlinear layers based on Bolt's 's protocol; (c) latency breakdown of linear layers of the original model and SpENCNN with 50% sparsity; (d) GEMV with a circulant weight matrix.
and nonlinear layers separately, which usually demonstrates better accuracy due to its ability to realize accurate activation functions [24]. In contrast, the end-to-end scheme relies on polynomial approximation TFHE schemes for activation functions, which either suffer from low accuracy or low computation efficiency [25, 11]. Hence, we focus on the hybrid scheme in our paper.
While formal privacy protection can be achieved, HE-based DNN inference suffers from high computation cost and orders of magnitude latency overhead [7, 10]. Previous works have proposed HE encoding and DNN architectures. HE encoding translates
algorithm-level optimizations high-ding high-dimensional tensor operations of DNNs into I-dimensional polynomial operations of HE and directly impacts the computation efficiency. For example, Cheetah [10] and Falcon [26] propose efficient encoding algorithms for convolutions while Iron [24] and BubbleBee [22] optimize for general matrix multiplications (GEMMs). Neujeans [27] and Bolt [7] further introduce the baby giant-step (BSGS) algorithm to reduce the number of HE rotations and achieve state-of- state-of-the-are art (SOTA) performance. While significant speedup has been achieved, the overall latency of MobileNetV2 [28] and Vision Transformer (ViT) [29] still exceeds 60s and 170s with Bolt, respectively, as shown in Figure (b) and (c). Meanwhile, linear layers account for more than 75% of total latency due to HE multiplications and rotations, thus, becoming the main optimization target of PrivCirNet.
DNN model optimizations focus on developing HE-friendly architectures. [30, 31, 32, 33, 34, 35, 36] optimize the activation functions for communication and computation reduction, which is orthogonal to our work. [37, 38, 39] propose HE-ffiendly structured pruning to reduce both HE rotations and multiplications. However, as shown in Figure 1 (c), as these methods are not fully compatible with the SOTA protocols, their latency reduction remains limited, especially for HE rotations'.
To further reduce the computation cost of linear layers and bridge the latency gap, this paper, we propose PrivCirNet. Our key observation is that the circulani trunsformation of weight matrices enables to convert a general matrix-vector multiplication (GEMV) into HE-friendly I-dimensional convolution, simultaneously reducing the HE multiplications and rotations, shown in Figure 1 (d). While directly transforming the whole weight matrix into a circulant matrix incurs high accuracy degradation, propose block circulant transformation and answer the following two questions. First, existing HE encoding algorithms are not fully compatible with block circulant weight matrices, limiting the efficiency gain. How to co-design the encoding algorithm to fully unleash the potential is the first question. Meanwhile, as block circulant transformation introduces structure constraints to weight matrices and inevitably impacts the accuracy, how to determine the layer-wise block sizes for better accuracy/efficiency trade-off becomes the second question.
PrivCinNet features novel encoding algorithm optimized for block circulant weight matrices, dubbed CirEncode, that reduces the HE computation in proportion to block size. PrivCirNet also co-design a latency-aware optimization formulation for layer-wise block size assignment based on second-order information. PrivCinNet further leverages layer fusion to reduce the inference cost. With extensive experiments across different DNN architectures (i.e., MobileNetV2, ResNet-18 and ViT) and datasets (i.e, CIFAR, Tiny ImageNet, and ImageNet), we demonstrate PrivCirNet reduces the latency of Mob, ResNet- 18, and VIT by 1.7x, 5.0x and 1.3x compared with Bolt [7], respectively. Compared with SOTA HE-friendly pruning method SpENCNN [37], PrivCirNet achieves 4.2%, 4.1 1.1% and 12% better accuracy on Mob, ResNet- 18, and ViT, respectively, demonstrating great capability to accelerate private inference for both ConvNets and Transformers.
'The incompatibility is due to the BSGS algorithm and is explained in Appendix D in detail.

---

2 Preliminaries
Notations. We represent matrices with upper-cast case letters (e.g., X) and vectors with lower-case letters (e.g., z). We also use lower-case letters with a "hat" symbol (e.g.. ④) to represent a polynomial, and æ[i] to denote the i-th coefficient of å. We @ to denote -eement-wise multiplication. Let [-] denote ceiling operations and [ri] denote the set {0....., 1} for E Æ+ where Z denotes the integer domain. We also denote the set of integer 1), whose degree n. is a power-of-two integer (e.g., 213 following Bolt [7].. We (d1, d2. dz) to denote the input, hidden, and output dimensions of GEMM, respectively. For convolution, we use (H, W. C*) to represent the input height, width, and number of input channels, and (Rt K) denote the kernel size and number of output channels.
x to represent polynomial multiplication and
polynomials with A. = /
2.1
Cryptographic Primitives
BFV HE Scheme. Following most hybrid HE/MPC schemes [7, 9, 10. 20], PrivCirNet leverages the lattice-based Brakerski-Fan- Far-Vercateeenn (BFV) HE scheme [40] and mainly involves the following HE operations. including ciphertext addition (denoted as HE-Add), ciphertext-plaintet multiplication (denoted as HE-Pmult), and ciphertext rotation (denoted as HE-Rot). While HE-Pmult and HE-Rot dominate the overall computation cost, each HE-Rot operation is usually an order of magnitude slower than HE-Pmult 41].
HE Encoding Methods. HE operates over polynomials with 1-dimensional coefficient vectors while DNNs compute over tensors. Encoding is the procedure to map a tensor to polynomial and directly determines the computation efficiency. Existing encoding methods can be classified into two categories: coefficient encoding [10, 24, 26, 22] and single instruction multiple data (SIMD) encoding [9, 6, 42, 27, 7]. Coefficient encoding can support convolutions efficiently with a single HE-Pmult [10]. In contrast, SIMD encoding only supports glement-wiss multiplications and requires multiple HE-Rot for convolutions [9]. For GEMMs, either coefficient encoding [22] or SIMD encoding [7] requires HE-Pmult and HE-Rot, while the SIMD encoding algorithm Bolt [7] achieves the SOTA computation efficiency.
The two encoding methods can be transformed to each other through the discrete Fourier transform (DFT) as shown in Lemma [27]. The main reason is that polynomial multiplication implements convolutions in the coefficient domain and is equivalent to element-wise multiplications in the frequency domain, leading Lemma [27]. While [27] only leverages such nested encoding for convolutions, we show how such schemes can be improved to support block circulant GEMMs and convolutions. We refer interested readers [27] for more detailed description.
Lemma 1. (DFT(w))sIND> x (DFT( = (DFT(w) @ (FT(=)) = (FT(( x (o)
2.2 Threat Model and Security Guarantee
PrivCirNet works in a general private inference scenario that involves two parties, i.e,, server and client. A server holds the proprietary DNN model and client owns private data [10, 24]. PrivCirNet enables the client to obtain the inference results while keeping the server's 's model weights and the client's data private. Consistent with previous works [7, 10, 24], we assume the DNN architecture (including the block sizes) is known to both sides and adopt an honest-but-curious security model in which both parties follow the specification of the protocol but also try learn more from than allowed. Following [7. 10]. PrivCirNet is built upon cryptographic primitives, including BFV and MPC protocols, and focuses on co-optimizing the DNN architecture and the HE encoding algorithm. The security can hence be guaranteed following [40, 43].
2.3 Related Works
To improve the efficiency of HE-based DNN inference, existing works mainly focus on optimizing
the HEB encoding algorithm [10, 24, 26, 9, 6, 42, 27, 7] and the DNN architectures [31, 30, 32, 33, 34, 35, 36, 38, 39, 37, 25]. In Table 1, we compare PrivCirNet with prior-art works qualitatively. As can be observed, PrivCirNet features network and encoding co-optimization to improve the efficiency of both GEMMs and convolutions.
3

---

Table Comparison with existing private inference works.
Mothod
HE Encoding Optimization
Turget Ops
Network Optimization
Encoding
Reduction R Pmult Reduction
[31,
ReL. ReLUIGEUU
ReLUIGELU Pruning
Cheetah [10]
Sparse
GEMV, Coev
Iron (24)
Sparse
GEMM
Neujeans [27]
Donse
Comy
Bolt [7]
Dense
GEMM
Token Pruming
39, 37]
Dense
GEMM. Conv
Weight Pruning
PrivCirNett (ours)
Donse
GEMM. Conv Block Circulant Transforaaioon
Table 2: Comparison between PrivCirNet and previous works that use circulant matrix.
Vanaable block
Method
Application
Entiaaizaaion methodd
Black sssignment
Eacoding
Network
GuCNN [44]
CaCor [45)
Convolation in plaintest
Forbenius
ComNeet
Falean [25)
Fanlatisral HF-bssol privaic inforence)
Ferhenius norms
x
Uriiam
Thressaaeer network
RisCaaNe
(ours)
Hylwid HE-MPC private inference
Loss-aware
/
Lalency-swane block sice uosignatent
ConNNets, Transeeees
Attempts have been made to use the circulant matrix to accelerate inference in plaintext [44, 45] and ciphertext [25] domains. However, two unresolved problems remain both domains: 1) how to initialize circulant matrices, and 2) determining block sizes for each layer. As result, it is hard for [44, 45, 25] be applied to more efficient networks, e.g., MobileNetV2, Transformers, etc. Additionally, in the ciphertext domain, [25] cannot fully leverage block circulant matrices, resulting in limited even increased latency. contrast, PrivCirNet maximizes the potential of block circulant matrices by customizing the HE encoding algorithm and proposing new initialization and block size assignment algorithms, achieving a superior accuracy-latency trade-off. We give a comprehensive comparison between PrivCirNet and [44, 45, 25] in Table 2. We leave more detailed review of existing works in Appendix
100
-23% L
Layer-wise block sizes Top- Ace. Latency
Lakenyy 0%)
77
-30%
1-1-1-1
66.13
42
16-16-16-1
64.51
25
50
16-16-1-16
64.16
19 s
16-1-16-16
63.23
16s
1-16-16-16
62.17
16s
Non-drauknt SIMD Coefficint Ideal
Figure 2: Directly using coefficient or SIMD encoding to block circulant GEMMs ((d1, d2,,,, (256, 192, 576, 2)) leads to limited efficiency improvement.
Table 3: Accuracy and latency impact of applying block eirculant transformation to different layers of MobileNetV2 on Tiny ImageNet. 32 layers are partitioned into groups
3 PrivCirNet Framework
3.1 Motivation
While the circulant transformation enables to convert GEMV into HE-friendly 1-dimensional convolution, directly transforming the whole weight into a circulant matrix introduces large accuracy degradation due to the high compression ratio. We propose to leverage block circulant transformation and to trade off accuracy with efficiency by controlling the block sizes. However, we observe the following challenges that need to be addressed.
Challenge 1: existing encoding algorithms are incompatible with block circulant weight matri- ces. The computation of a GEMM with a block circulant weight matrix can be naturally decomposed into two steps, i.e., a eirculant GEMV within each block and general GEMM across blocks. Within each block, a circulant GEMV can be converted to 1-dimensional convolution and be computed with single HE-Pmult through coefficient encoding. However, when processing the GEMM across blocks, coefficient encoding suffers from either high communication cost [10, 24] or extensive HE rotations [22]. contrast, while SIMD encoding can process the GEMM across blocks more effi- ciently [7]. it still requires HE rotations to process the convolution within each block. As shown in

---

11
2
2
(1 -ar--tee +
xhxx
encode
+(-2+x+
==
7 ar"
4s Fro 12
Y W
CirEnode within a circulant block
A
Plaintest
Server preprocessinn
Ciient online
Server online
Plaintest aferDFT
1
Cipleettnnt
Miki
DXFT
15,
12
[R:10 1922
RUJ0 9h
Notations
CirEncade across circulant blocks
Figure 4: An example of CirEncode for block circulant GEMM where (di, d2, da, b) (4,8,
Figure 2, with existing encoding algorithms, block circulant transformation only introduces limited efficiency improvement. Therefore, it is important to design the encoding algorithm to fully unleash the efficiency potential of the block circulant transformation.
Challenge 2: accuracy and latency impact of block circulant transformation varies across layers. We apply the block circulant weight transformation with different block sizes to different layers of a MobileNetV2 on Tiny ImageNet. As shown in Table 3, the accuracy and latency impact on the MobileNetV2 varies significantly. Hence, better explore the Pareto optimal of efficiency and accuracy, layer-wise block size assignment becomes important.
PrivCirNe Overview. In this paper, we introduce Priv- CirNet, which features a joint optimization of the block circulant network and the private inference protocol. Fig-
(b) Network or 0 Optimization
Sec. 3.3
Lakenty aware blocks size assegmment
ure 3 provides an overview of PrivCirNet. We first propose CirEncode for the GEMMs with block circulant weights in Section 3.2. Then, we develop latency- optimization algorithm to determine the block sizes for each layer based on second-order information in Section 3.3. We also pro- pose network- protooool co-fusion methods further boost the inference efficiency in Section 3.4.
Protocol
Network pmotooo
co-fuscon
CirExcode
Sec. 3.4
Sec. 3.2
(a) Protocol Optimization
Figure 3: Overview of PrivCirNet.
3.2 CirEncode: nested encoding for block circulant GEMMs
High-level idea. Consider GEMM Y WX,, where Y Zdaxd1, W E Zdgxd2 X 2d2xd1 W a block circulant matrix with block size b. Then, CirEncode encodes the GEMM following two steps: for each block with W xb and X E Zbxd1, GEMVs and leverage the coefficient encoding to avoid HE-Rot as shown in Figure 4 (a); then, for across blocks, we regard it GEMM and leverage the SIMD encoding further reduce the HE-Rot as shown in Figure 4 (b). Thereby, CirEncode combines the advantages of both encoding schemes.
convert the computation into d1 parallel
Encoding within circulant block. We elaborately design the encoding rule for circulant GEMM. Formally, we define two encoding functions Fw bxb + An and X Zbxd] + An as follows:
= .w (W), where úi vi[idi] W [ 0), Vi [b]. [di]
f = (X),,, where &(id; + ] ji. Vi [b]. E [di]
where other coefficients of u are set to 0. ý ú x a directly gives the result of Y WX as described in Theorem 1 and we defer the proof to Appendix I.1.
Theorem 1. Given circulant matrix W E zbxb and an input matrix X E Zbxds where bdl I define two polynomials = Tw (W) and f (X)) Then, GEMM Y WX E zbxd1 can be evaluated by the polynomial multiplication ý = w åt, where Y(i,jl = glid + jl. Vi E [b]. E [d,]-
Compared with prior-art coefficient encoding algorithms for GEMM, e.g., Iron [24], CirEncode fea- tures two key advantages: 1) the encoding density, i.e., number of useful elements encoded per
CirEncooe mod xt which is different from [10], the explanation is in Appendix I.I.
5

---

Table 4: Theoretical complexity comparison of CirEncode with prior works. The data of GEMM is measured with dimension (d1, d2, d3) = (512, 768, 3072). and that of convolution is (H, W, R, (16, 16, 128, 128, 3). The polynomial degree 8192 and block size b 8.
Framework
GEMM
Convolution
HE-Ror
Ciiphertetts Ofdidd + 4g77))
HE-PoN
HE-Rot
Cigienents
Crypi [+]
(jd,dghs))) 1474%6
O
di)/n +
240
O(FWCR()))
OLHIII
208
Ki/++ K)
OUIVIC+ Kijel
Cheerah [10]
Oidydafa)a)
147456
Oddydgh + [dy/niidig
$120
O(HWCR())
1408
OLHWC/ [W/
134
Irun [24]
Ord
147456
960
OUWCCRR1a
12672
Oly F.
257
Oldydy ho (Pym))
Oldied it Ag77))
C(HWCK))) OIRI logg//1ay)))
O (C++ KT/a)
Bumblebre [22]
147456
6144
240
L408
236
16
Neujeans+DSGS (27)
Oldydafa/a)
147456
Ol dydolaaa))))
288
Oldiida + dal/e))
240
O(HWCK(N)
1024
Olv HWCK))
48
OLHIICC + Ki/at
16
Bah--SGS [?]
Ordndads/a)
147456
Oly (idoda/))))
528
(dd + 4a//e)
240
J(WCCKR)a; 11700
Dly HWCK 106
O'HWICR K)/)
100
GEMM with circulant weight mannx
Convolation with circulant weight kernel
CirEncade (ours)
Oidedget/(ndd)
Olyy M/diiissg// (nb)
Ofdttely 4 dal/o)
O(HWCK/ml)) 128
Oly' (KCC))
O(HIV Ki/e]
18482
240
16
polynomial, is much higher, minimizing the communication cost; 2) the input and output of a GEMM follow the same encoding rule described above, enabling layer fusion in Section 3.4.
Encoding across circulant blocks. Consider each circulant block as unit, the computation across blocks can be regarded as a GEMM with dimension (1, da ds) We apply the SIMD diagonal encoding pack different circulant blocks in parallel and DFT for each block to transform the coefficient encoding into the SIMD encoding format, as shown in Figure 4 (b). Similar to Lemma 1, the correctness given by Theorem and we defer the proof Appendix I.2.
Theorem 2. Given M circulant weight matrices Wo...., WM- E Zbxb and input matrices Xa,-.., M- Zbxdr, define polynomials Wm and 5. with cient packing in Theorem I. Then, Ym.. = Wm Xm can be evaluated simultaneously through the polynomial multiplication in SIMI) encoding:
[M] following the coeffi-
(DFT((0))..... (9'T((9-))))ca
DFT( =DDF( I.FT (w (
where represents concatenation of polynomial coefficients and [m] 9m [ūd] + j], Vi E [b].] [d1]. m E [M].
We further extend the BSGS algorithm [7] to CirEncode with details in Appendix B. We also design CirEncode for block circulant convolutions described in Appendix C.
Theoretical complexity analysis. Table 4 shows the theoretical complexity comparison of CirEn- code with prior-art encoding methods in the number of HE-Pmult, HE-Rot, and ciphertexts. CirEn- code computes a (d1, b, b) circulant GEMM with only O(bd//n) /n) HE-Pmult and RotRot. Therefore, compared to the SOTA scheme, i.c., Bolt and Neujeans, CirEncode reduces the number of HE-Pmult and HE-Rot by factor of b and vb, respectively, for both GEMM and convolution. A detailed proof of theoretical complexity is available in Appendix B.
3.3 Latency-aware block size assignment with loss-aware initialization
Previous works use uniform block size [44, 25] or manually set the block sizes [45] for each layer, resulting sub-optimal performance. We now propose novel latency-awar block size assignment algorithm based on recond-order information together with loss-aware initialization, which achieves superior Pareto front of latency and accuracy.
Loss-aware initialization for circulant matrices. Previously, circulant matrices were initialized by minimizing the Frobenius norm between the non-cireulant and circulant matrices [46, 45], i.e., min W W.ll?- where W' represents the weight matrix after the circulant transformation of layer i. While this method minimizes the min square error (MSE) of the weight matrix. it overlooks that the network accuracy has different sensitivity towards the MSE of different layers. Therefore, we propose to directly assess the final loss instead of MSE for the transformation with Taylor expansion:
TCT (D)
1 AW. HAW, + O (IAW.1").
Lw:(D) - Lw. (D) aw,
AW: + 2
(1)

---

(a) Initialize with Frobenius norm
(b) Initialize with Qr (ours)
Senstivity
1.55
1.0
actailivilics
some
b
Seneltisity
1.3
bei
b-5
0.7
blck sice
6.3
blok sice (b)
90
Black Size
Lisear Index
Lincar Layer Indes
Figure 5:
Layer-wise sensitivity and block size visualization for ViT on CIFAR-100.
where L is the task loss, D is the training dataset, H is the Hessian matrix and AW; = W - W The first term can be neglected as the model has already converged on the training dataset [47]. The Hessian matrix can be approximated using diagonal Fisher information matrix [48]. We then define the sensitivity layer as Q2
(( (OC(P) aw;
)) AW,
2
Q = AW, HAW, & AW, diag
(2)
Hence, we propose initializing the circulant matrix by minimizing Ω instead of the Frobenius norm, which can be solved analytically W
E
W
OL(D)
.Rdiag is the expectation of each
Ow.
ding
diagonal of matrix. An example is provided in Appendix E.
Latency-aware block size assignment. Given an I-layer network, we denote the block size of each layer {b1..-.,bz, where b; (2",.... ,..... ".0,...,kk-13 The search space contains kL possible architectures, which can be extremely large, e.g., 2 x 1022 for k: 5, T. 32, rendering exhaustive search impractical. Therefore, we propose to formulate the search problem as an integer lincar programming (ILP) problem, aiming to minimize the overall network sensitivity under the latency constraint [49, 50, 51]:
Objective:
min (be)
Σ 2
Subject to:
Σ LAT <
Latency Limit
Here, 22 is the i-th layer's sensitivity with block size b, LAT the associated latency in private inference. LAT can be pre-computed given the dimension of the layer.
Visualization analysis. We visualize the layer-wise sensitivity and the searched structure of different initialization methods in Figure 5, As we can observe in Figure 5 (a), the previous method fails to tell the different sensitivity of block size 4, 8, and 16 for most of the layers. In contrast, our method, depicted Figure (b), better captures the effects of varying block sizes on task loss.
3.4 Network- Prottocol Co-Fusion
Circulant ConvBN Fusion. During the inference, con- volution (conv) and batch normalization (bn) layers usually fused for lower latency. However, naïve fusion destroys the block circulant structure. Hence, propose a fusion method for circulant conv and bn. Consider the learnable scaling factor y E ge for bn layer. We combine the elements of y into groups of size b and set 7 E z such that 7/]
Inverted Residual block in MBV2
X1 L
Xyes
Ixl Cozs
(a) Circulant
Batch Norm
ConvBN Fusion
V
(b) IR Fusion
Et= 7B+J-6+ mod b)] Vi [C]. We use the same strat- egy for the learnable bias, running mean and variance, which maintains the circulant structure after fusion.
1xl Cozs
Batch Norm
Inverted Residual (IR) Fusion Protocol. In the hy- brid WE/MPCC-bsed DNN inference, the network is
Figure 6: Network- Co-Fusion.
7

---

topplitend (If))
Capitbed Ut1b
Coptiiied
Chokia
Checab
Nagjen
Negoen
IMI PridiiNia B/l
Bull
PriiCaNa
7
(181000900)
(2M
(294,544
(9.20.1)
(ResNet-18)
Figure 7: Latency comparison of different protocols for GEMMs and convolutions. PrivCirNet use circulant weight with block size
evaluated layer by layer. We identify the potential for layer fusion of consecutive linear lay- in MobileNetV2 [28]. Figure (b) shows where implement fusion, aiming compute convbn(Ires + (21)) all together. Thanks to the encoding consistency provided by CirEn- code, we can fuse layers with equal block size. Details of the fusion algorithm are in Appendix F.
4 Experiments
4.1 Experimental Setup
Implementation. PrivCirNet built on top of the SEAL library [52] in C++. We use the OpenChee- tah [10] to evaluate Cheetah [10] and Cryp'FFlow2 [6]. We also implement Falcon [26]. Neujeans [27] and Bolt [7] protocols. Following [10, 53, 54], we simulate LAA network setting via Linux Traffic Control, where the bandwidth is 384 MBps and the echo latency is 0.3ms. All the experiments are performed on a machine with 2.4 GHz Intel Xeon CPU. Following [7], we set n = 8192, security parameter À 128, plaintext bitwidth 41 and ciphertext bitwidth q 218, which is also the default setting in SEAL library [52].
Datasets and Models. We evaluate PrivCirNet on MobileNetV2 [28]. ResNet- 18 [55], and ViT [29] across four datasets: CIFAR-10. 10, CIFAR- 100, Tiny ImageNet and ImageNet." Detailed model architectures and training settings can be found in Appendix G.
Baselines. We compare PrivCirNet with prior-art HE-based DNN inference frameworks, including CrypTFlow2 [6]. Cheetah [10]. Falcon [26], Neujeans [27] and Bolt [7]. We also compare with SpENCNN [37] which the SOTA HE-friendly pruning method.
4.2 Micro-Benchmark on Single GEMM and Convolution
benchmark PrivCirNet on both GEMMs and convolutions with different block sizes. The layer dimensions are chosen from MobileNetV2, ResNet-18, and VIT. be observed that PrivCirNet supports both GEMMs and convolutions efficiently. Compared with Bolt and Cheetah, PrivCinNet (b8), i.e.. block size of 8, achieves 5 ~ 7x latency reduction. With PrivCirNet (b2), we can reduce latency by 1.7x on average.
Latency comparison. In Figure
The number of HE-Pmult and HE-Rot comparison. In Table 5, we show the number of HE- Rot and HE--Pmult comparisons with different protocols. The layer dimensions chosen from MobileNetV2, ResNet-18, and ViT. It can be observed that: 1) Compared with SOTA algorithms Bolt and Neujeans, PrivCirNet (b8) achieves average HE-Rot reduction and 8.5x HE-Pmult reduction. And PrivCinNet (b2) achieves on average 2.1x HE-Rot reduction and 1.9x HE-Pmult reduction which consistent with the theoretical complexity. PrivCirNet supports both GEMM and convolution efficiently. On the contrary, Neujeans performs worse in GEMM while Bolt performs worse in convolution.
4.3 End-to-End Inference Evaluation
In Figure and Figure 9, we benchmark PrivCirNet at the full network scale and plot the Pareto front of accuracy and latency of linear layers. We make the following observation:
Each of the models in the paper is capable of only classifying the ImageNet Ik categories.

---

Table 5: The number of HE-Rot HE-Pmullt comparisons of different protocols for GEMMs and convolutions with different dimensions.
Method
MobileNetV2
VIT
ResNet-18
Average
(1021.96,4))
(61,61_354)
(16,160,960)
(256,192,192)
(256.192,566)
(256.381.192)
(32,6113)
(16,128,3)
(8,256.3
Nesjams-+BSSS [27]
32/288
447 384
88/ 11024
90/1152
150/3456
120/ 2304
52/ 1024
48 1024
41/1134
727 1310
Bolt+BSGS [7]
21 288
33/381
55/960
60/1152
91/3156
78/2304
63/ 9216
106 11700
116/1608
1608
70/ 2504
PriCCrNett (b2)
9/144
21/192
37/480
36 66/576
60/ 1728
54/1152
56/
32/ 726
26/567
33/675
(b))
0/33
7/48
15/
144
18/432
18/288
12/135
10/155
(a) MBV2+CIFAR-10
(b) MIV2-CIFAR-100
(c) MBy2+TTy ImageNet
MBV2-ImageNet
Top-1 Arc, (%)
40.5
4.9%7
2.7%
Ball
No piu
Bell
13
Beak
Fakce
12.5
Copt
Opgiiiied
29
30
at
300
15
40
522
90:00
100
200
300 1051
Latency (A)
Latency (5)
Latency (9)
Latency (s)
Figure 8: Comparison with SpENCNN and other prior-art protocols on MobileNetV2.
(a) ResNet18-CIFAR-10
ResNeti8+Tinn ImageNett
(e) VIT-CIFAR-10
Viny ImageNett
Top-1 Acc. (%6)
57.5
550
12607
4,1%7
Bih
Bib
32.5
Bea
Nogizne
Pilca
Takon
Nedivatt
Tikon
Nogvatt
500
Negvatt
Takon
47.5
OrpilFkel
23
So
150
5566
110
152
369
Latency
Latency
Latency
Latency (6)
Figure 9: Comparison with SpENCNN and other prior-art protocols on ResNet- 18 and VIT.
Comparison with prior-art HE-based frameworks. PrivCirNet consistently outperforms prior-art frameworks, including Bolt, Neujeans, Falcon, etc, in both ConvNets and Transformers. Specifically, on Tiny ImageNet, compared with Bolt, PrivCirNet achieves 5.0x, 1.3x latency reduction with iso-accuracy on MobileNetV2, R8 and VIT, respectively. Compared to Cheetah, PrivCir- Net achieves 1.3 ~ 4.8x latency reduction with iso-accuracy across three models.
Comparison with prior-art structured pruning method SpENCNN. PrivCirNet achieves SOTA accuracy/latency Pareto front across different datasets and models. Especially in larger compres- sion ratios, SpENCNN suffers from huge accuracy loss. In comparison, PrivCirNet outperforms SpENCNN by 5.2% on MobileNetV2, 4.1% 1% on ResNet-18, and 12% on ViT on Tiny ImageNet.
Benchmark on ImageNet. We benchmark PrivCirNet on ImageNet with MobileNetV2 in Figure (d). PrivCirNet achieves 1.4x latency reduction compared with prior-art framework Neujeans and achieves 4.2% accuracy improvement over SpENCNN with lower latency.
4.4 Ablation Study
Effectiveness of latency-aware block size assign- ment. Table 6 shows the comparison of different block size assignment methods, including uniform block size, mixed block sizes with Frobenius norm initialization [46, 45], and mixed block sizes with loss-aware initialization. According to the results, we find that: 1) PrivCirNet achieves the highest ac- curacy across most datasets and models. 2) Priv- CirNet exhibits enhanced performance at higher compression ratios, emphasizing the importance of latency-aware block size assignment in networks with limited capacity.
Dotaee:: Tiny ImageNit
d:: Comm (MR)
Aoc (5)
Breeline MubileNwe22
45.90
250
*: 66.14
*Cr Tineformation (b>2)-
* 258
ClrEacoda 3.21
250
Labacy Nock
asdgrnment (Sec.
* 290
06.36
+CoarBN Pasion 1.4)
25.47|
t 216
st 66.30
+IIl Fosion (Sec. 3.0
24.33
*r 203
t 65.30
Lakency 60
Figure 10: Ablation study of our proposed optimizations in PrivCirNet on MobileNetV2.

---

Table 6: Accuracy comparison of different block size assignment methods. Latency limitation represents the proportion of latency relative to the original uncompressed model.
Top-1 Acc.
Latency Limitation
Method
MobileNetV2
VIT
CIFAR-10 10
CIFAR- 100
Tiny ImageNet CIFAR-TO
CIFAR-TO 100 Tiny ImugeNNtt
Uncompressed
100%
94.74
78.70
66.14
93.54
74.77
62.65
50%
94.81 (-0.23)
77.98 (40.00)
65.26
93.38 (-006) 74.41 (40.30)
61.87 (+0.08)
Uniform
25%
93.97 (-0.33)
76.30 (-1.41)
(12.7)
92.57 (-0.33)
72.00 (0.76)
58.11 (-0.85)
92.71 (-0.55)
73.89 (-0.96)
60.34 (-1,50)
90.98 (-0.46) 67.51 (-2.22)
(-2.0
50%
94.71 (-0.35)
78.28 (-0.30)
65.98 (-0.38)
93.40 (-0.44) 74.58 (-0.13)
61.33 (-0.46)
Probenius
25%
94.23 (40.07)
76.38 (-1.33)
63.76
92, 12.40 (-0.50)
72.00 (40.99)
58.00 (-0.96)
12.5%
92.65 (-0.61)
74.32 (40.33)
61.14
90.32 (-1.12) 68.02 (-1.71)
51.92
50%
95.04
78.58
66.36
93.44
74.71
61.79
Loss-aware
25%
94.30
77.71
64,83
92,90
72.76
58.96
(PrivCinNet)
12.5%
93,26
74.85
61.84
91.44
69.73
54.06
Effectiveness of different optimizations in PrivCirNet. We demonstrate the effectiveness of the proposed optimizations by adding them step by step on MobileNetV2 and Tiny ImageNet. As in Figure 10, observe that: 1) without CirEncode, circulant transformation harms the accuracy and cannot reduce latency due to incompatibility with existing encoding algorithms; 2) latency-aware block size assignment significantly improves the accuracy and even outperforms the uncompressed model; 3) the fusion methods reduce both the latency and communication with negligible accuracy loss.
Additional Results, We present extra experiments to show 1) latency breakdown, and 2) comparison on more networks in Appendix H.
5 Limitation and Future Work
PrivCirNet focuses on improving the HE computation ef- ficiency, which accounts for 75% total latency and is the bottleneck in the hybrid HE/MPC scheme. We can also extend PrivCirNet with activation function optimization methods, e.g.. ReLU pruning method SNL [30]. As shown in Table 7, we prune 50% ReLUs PrivCirNet (b2) with- out accuracy loss, achieving 2x latency reduction in non- linear layers. We regard more in-depth study of joint linear/nonlinear layer optimization as our future work.
Method (CIFAR 100)
Top 1 Aec.
Nonliee Jaencyy
Tond lueecy
Original RoNos.1 18
76.52
12.6.
73.72x
1033
(501 RelLU)
76.72
6.32s
39.44x
-NNL N0% ReLU)
76.27
5006
38.8x
Table 7: Extend PrivCirNet with non- linear layer optimization method SNL.
6 Conclusion
In this paper, we introduce PrivCirNet, a network/protocol co-optimization framework to enhance the efficiency of HE-based DNN inference. PrivCirNet leverages block cireulant transformation to reduce the HE computation. PrivCirNet features a novel encoding method, CirEncode, and a latency-awarr block size assignment algorithm. PrivCinNet significantly improves the network-level inference efficiency while maintaining a high accuracy. PrivCirNet achieves a latency reduction of 1.3 5.0x compared to Bolt in Mob,leNetV2, ResNet-18 and VIT. Moreover, when compared with SpENCNN, PrivCirNet attains up to 12% higher accuracy, demonstrating a high potential to accelerate private inference across both ConvNets and Transformers.
7 Acknowledgement
This work was partly supported by Beijing Municipal Science and Technology Program (No. Z241 100004224015), Ant Group, and the 111 Project (B18001).
10

---

References
[1] Neda Azouji, Ashkan Sami, and Mohammad Taheri. Efficientmask-ner for face authentication in the era of covid-19 pandemic. Signal, Image and Video Processing, 16(7):191111999 2022.
[2] Georgios Kaissis, Alexander Ziller, Jonathan Passerat-Palmbach, Théo Ryffel, Dmitrii Usynin, Andrew Trask, Ionésio Lima Jr, Jason Mancuso, Friederike Jungmann, Marc-Matthias Steinborn et al. End-to-end privacy preserving deep learning on nulti-institutionall medical imaging. Nature Machine Intelligence, 36)):773-444 2021.
[3] Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoom. systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, pages 1-10, 2022.
[4] Woo-Seok Choi, Brandon Reagen, Yeon Wei, and David Brooks. Impala: Low-latency, communication-eficei private deep learning inference, May 2022.
[5] Kanav Gupta, Deepak Kumaraswamy, Nishanth Chandran, and Divya Gupta. Llama: A low latency math library for secure inference. Proceedings on Privacy Enhancing Technologies, 2022(4):274-29)) Sep 2022.
[6] Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow2: Practical 2-party secure inference. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 325-342, 2020.
[7] Q. Pang. J. Zhu, H. Möllering, W. Zheng, and T. Schneider. Bolt: and efficient inference for transformers. In 2024 IEEE Symposium on Security and Privacy (SP), pages 133-133, Los Alamitos, CA, USA, may 2024. IEEE Computer Society.
accurate
[8] Ran Gilad Bachhachc Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Wernsing. Cryptonets: Applying neural networks encrypted data with high throughput and accuracy. In International conference on machine learning, pages 201-210. PMLR, 2016.
[9] Chiraag Juvekar, Vinod Vaikuntanathan, and AnanthaP. Chandrakasan. GAZELLE: A low latency framework for secure neural network inference, Jan 2018.
[10] Zhicong Huang, Wen-jie Lu, Cheng Hong, and Jiansheng Ding, Cheetah: Lean and fast secure (Two-Party] } deep neural network inference. In 3/st USENIX Security Symposium (USENIX Security 22), pages 809 826.826.222 2022.
[11] Qian Lou and Lei Jiang. She: A fast and accurate deep neural network for encrypted data. Advances in neural information processing systems, 32, 2019.
[12] Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young-Sik Sik Kim, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access, 10:30039- 30054, 2022.
[13] Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon No, and Woosuk Choi. Low-complexity deep convolutional neural networks on fully homomorphic encryption using multiplexed parallel convolutions. In International Conference on Machine Learning, pages 12403-12422. PMLR, 2022.
[14] Jaiyoung Park, Donghwan Kim, Jongmin Kim, Sangpyo Kim, Wonkyung Jung, Jung Hee Cheon, and Jung Ho Ahn. Toward practical privacy-preserve convolutional neural networks exploiting fully homomorphic encryption. arXiv preprint 23.0:23000.6530. 2023.
[15] Dongwoo Kim and Cyril Guyot. Optimized privacy morphic eneryption. IEEE Transactions on Information Forensics and Security, 18:2175-2187, 2023.
privacy-preserving preserving enn inference with fully homo-
[16] Shengyu Fan, Zhiwei Wang, Weizhi Xu, Rui Hou, Dan Meng, and Mingzhe Zhang. Tensorfhe: Achieving practical computation on encrypted data using gpgpu. In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 922-934, IEEE, 2023,
11

---

[17] Jongmin Kim, Gwangho Lee, Sangpyo Kim, Gina Sohn. Minsoo Rhu, John Kim, and Jung Ho Ahn. Ark: Fully homomorphic encryption accelerator with runtime data generation and inter- operation key reuse. In 2022 55th IEEF/ACM International Symposium on Microarchitecture (MICRO), pages 1237-1254. IEEE, 2022.
[18] George Onoufriou, Paul Mayfield, and Georgios Leontidis, Fully homomorphically encrypted deep learning as service. Machine Learning and Knowledge Extruction, 314)8819-834, 2021.
[19] Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. Oblivious neural network predictions via minionn transformations. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Oct 2017.
[20] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and RalucaAda Popa. Delphi: A cryptographic inference service for neural networks, Jan 2020.
[21] Karthik Garimella, Zahra Ghodsi, NandanKumar Jha, Siddharth Garg, and Brandon Reagen. Characterizing and optimizing end-to-end systems for private inference, Jul 2022.
[22] Wen-jie Lu, Zhicong Huang, Zhen Gu, Jingyu Li, Jian Liu, Kui Ren, Cheng Hong, Tao Wei, and WenGuang Chen. Bumblebee: Secure two-party inference framework for large transformers. Cryptology ePrint Archive, 2023.
[23] Donghwan Kim, Jaiyoung Park, Jongmin Kim, Sangpyo Kim, and Jung Ho Ahn. Hyphen: A hybrid packing method and optimizations for homomorphic mncryttion-based neural networks. arXiv preprint urXiv:2302.024000 2023.
[24] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang. Iron: Private inference transformers. In Advances in Neural Information Processing Systems, 2022.
[25] Qian Lou, Wen-jie Lu, Cheng Hong, and Lei Jiang. Falcon: Fast spectral inference on encrypted data. Advances in Neural Information Processing Systems, 33:2364-253 2374, 2020.
[26] Tianshi Xu, Meng Li, Runsheng Wang, and Ru Huang. Falcon: Accelerating homomorphi- cally encrypted convolutions for efficient private mobile network inference. arXiv preprint arXiv:2308. 13189, 2023.
[27] Jae Hyung Ju, Jaiyoung Park. Jongmin Kim, Donghwan Kim, and Jung Ho Ahn. Neujeans: Private neural network inference with joint optimization of convolution and bootstrapping. The ACM Conference on Computer and Communications Security (CCS), 2024.
[28] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chier Chichh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510-4520, 2018
[29] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.119299 2020.
[30] Minsu Cho, Ameya Joshi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Selective network linearization for efficient private inference. In International Conference on Machine Learning, pages 3947-3961. PMLR, 2022.
[31] Nandan Kumar Jha, Zahra Ghodsi, Siddharth Garg, and Brandon Reagen. Deepreduce: Relu reduction for fast private inference. In International Conference on Machine Learning, pages 4839-4849. PMLR, 2021.
[32] Souvik Kundu, Shunlin Lu, Yuke Zhang, Jacqueline Liu, and Peter A Beerel. Learning to linearize deep neural networks for secure and efficient private inference. arXiv preprint 2.Xiv:2301.09254 2023.
[33] Minsu Cho, Zahra Ghodsi, Brandon Reagen, Siddharth Garg, and Chinmay Hegde. Sphynx: deep neural network design for private inference. IEEE Security & Privacy, 20(5):22-344 22:4, 2022.
12

---

[34] Hongwu Peng, Shaoyi Huang. Tong Zhou, Yukui Luo, Chenghong Wang, Zigeng Wang, Jiahui Zhao, Xi Xie, Ang Li, Tony Geng, et al. Autorep: Automatic relu replacement for fast private network inference. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5178-5188, 2023.
[35] Wenxuan Zeng. Meng Li, Wenjie Xiong, Wenjie Lu, Jin Tan, Runsheng Wang, and Ru Huang. Mpevit: Searching for mpe-friendly vision transformer with heterogeneous attention. arXiv preprint arXiv:22 13955,, 2022.
[36] Souvik Kundu, Yuke Zhang, Dake Chen, and Peter A Beerel. Making models shallow again: Jointly learning to reduce non-linearity and depth for latency-efficient private inference. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 4685-4689, 2023.
[37] Ran Ran, Xinwei Luo, Wei Wang, Tao Liu, Gang Quan, Xiaolin Xu, Caiwen Ding, and Wujie Wen. Spencnn: orchestrating encoding and sparsity for fast homomorphically encrypted neural network inference. In International Conference on Machine Learning, pages 287 28718-28728. PMLR, 2023.
[38] Yifei Cai, Qiao Zhang, Rui Ning, Chunsheng Xin, and Hongyi Wu. Hunter: He-friendly structured pruning for efficient privacy-preserving deep learning. In Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, pages 931-945, 2022.
[39] Ehud Aharoni, Moran Baruch, Pradip Bose, Alper Buyuktosunoglu, Nir Drucker, Subhankar Pal, Tomer Pelleg, Kanthi Sarpatwar, Hayim Shaul, Omri Soceanu, et al. He-pex: Efficient machine learning under homomorphic encryption using pruning, permutation and expansion. arXiv preprint arXiv:2207.03388 2022.
[40] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, 2012.
[41] Ran Ran, Nuo Xu, Tao Liu, Wei Wang, Gang Quan, and Wujie Wen. Penguin: Parallel-packed homomorphic encryption for fast graph convolutional network inference. Advances in Neural Information Processing Systems, 36, 2024.
[42] Qiao Zhang, Chunsheng Xin, and Hongyi Wu. Gala: Greedy computation for linear algebra in privacy-preserved neural networks. arXiv preprint arXiv:2105.01827, 2021.
[43] Oded Goldreich. Secure multi-party computation. Manuscript. Preliminary version, 78(1 10):1- 108, 1998.
[44] Caiwen Ding, Siyu Liao, Yanzhi Wang, Zhe Li, Ning Liu, Youwei Zhuo, Chao Wang, Xuehai Qian, Yu Bai, Geng Yuan, et al. Cirenn: accelerating and compressing deep neural networks us- ing block-cireulant weight matrices. In Proceedings of the 50th Annual IEEF/ACM International Symposium Microarchitecture pages 395-408, 2017.
[45] Siyu Liao and Bo Yuan. Cireconv: A structured convolution with low complexity. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4287-4294, 2019.
[46] Moody Chu and Robert Plemmons. Real-valued, low rank, circulant approximation. SIAM Journal on Matrix Analysis and Appliccations, page 645-659, Jan 2003.
[47] Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang, Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang, and Shi Gu. Brecq: Pushing the limit of post-training quantization by block reconstruction. arXiv preprint 21X1v:2102.05426, 2021.
[48] Genevieve B Orr and Klaus-Robert Müller. Neural neiworks: tricks of the trade. Springer, 1998.
[49] Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Hawq: Hessian aware quantization of neural networks with mixed-precision. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 293-302, 2019.
13

---

[50] Zhen Dong, Zhewei Yao, Daiyaan Arfeen, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Hawq-v2: Hessian aware trigh-weighted quantization of neural networks. Advances in neural information processing systems, 33: 18:118118-888 185299, 2020.
[51] Zhewei Yao, Zhen Dong, Zhangcheng Zheng, Amir Gholami, Jiali Yu, Eric Tan, Leyuan Wang, Qijing Huang, Yida Wang, Michael Mahoney, et al. Hawq-v3: Dyadic neural network quantization. In International Conference Machine Learning, pages 11875-11886. PMLR, 2021.
[52] Microsoft SEAL (release 3.6). Microsoft Research, Redmond, WA.
wtt.hha...cc//icrrooff/SSALL November 2020.
[53] Liyan Shen, Ye Dong, Binxing Fang, Jinqiao Shi, Xuebin Wang, Shengli Pan, and Ruisheng Shi. Abnn 2. In Proceedings of the 59th ACM/IEEE Design Automation Conference, Aug 2022.
[54] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE symposium on security and privacy (SP), pages 19-38. IEEE, 2017.
[55] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[56] Wenxuan Zeng, Meng Li, Haichuan Yang, Wen-jie Lu, Runsheng Wang, and Ru Huang. Copriv: Network/protocol co-optimization for communication--ffiiiennn private inference. arXiv preprint arXiv:2311.01737, 2023.
[57] Dacheng Li, Rulin Shao, Hongyi Wang, Han Guo, Eric P Xing, and Hao Zhang. Mpcformer: fast, performant and private transformer inference with mpc. arXiv preprint arXiv:2211.0145. 2022.
[58] Ali Hassani, Steven Walton, Nikhil Shah, Abulikemu Abuduweili, Jiachen Li, and Humphrey Shi. Escaping the big data paradigm with compact transformers. arXiv preprint arXiv:2104.05704, 2021.
[59] Iiiaa Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Design- ing network design spaces. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10428-10436, 2020.
[60] Zhuang Liu, Hanzi Mao, Chao-Yuaa Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11976 1986, 2022.
[61] Nandan Kumar Jha and Brandon Reagen. Deepreshape: Redesigning neural networks for efficient private inference, arXiv preprint arXiv:2304.10593, 2023.
14

---

A Related Works
To improve the efficiency of HE-based DNN inference, existing works mainly focus on optimizing the
HE encoding algorithm [10, 24, 26, 9, 6, 42, 27, 7] and the DNN architectures [31, 30, 56, 32, 33, 34, 35, 38, 39, 37, 25]. HE encoding optimizations focus on improving the encoding density (i.e., useful elements per polynomial) to reduce communication [24, 26, 22] and HE computations [10, 7, 27].
For example, Cheetah [10] proposes an efficient rotation free encoding algorithm for convolutions and Falcon [26] further improve the communication efficiency for group- wiup-wise convolution. Iron [24] and BubbleBee [22] optimize the encoding algorithm for general matrix multiplications (GEMMs). Neujeans [27] and Bolt [7] further introduce the baby-step giant-step (BSGS) algorithm to reduce the number HE rotations.
DNN architecture optimizations focus on developing HE-friendly architectures to improve inference efficiency including HE-friendly activation approximation or pruning [31, 30, 56, 32, 33, 34], weight pruning [38, 39, 37], etc. [30, 31, 32, 33, 34] optimize the ReLU functions through pruning and approximation for communication and computation reduction. [35, 57] propose to prune and approxi- mate GeLU functions for efficient private transformer inference. [37, 38, 39] propose HE-ffrienly structured pruning to reduce both HE rotations and multiplications.
B Baby-step Giant-step (BSGS) Algorithm for CirEncode
Wn
W12
W13
W14
X1
W21
W22
W23
W24
X2
W
W3
W32
W33
W34
X3
W41
W42
W43
W44
X4
(a) GEMV
<<: RotRot
x
<<
W
<<
2
W3
f <<
3
R4
X
W
X₂
W₂2
X3
W
X₂
W
Y
X₂
W22
X3
W2
X,
W24
X;
W
Yg
O
+
O
+
X
W33
X4
W3+
X
W
X₂
W32
Yg
X
W
X,
W44
X₂
W
X₃
W45
Yg
(b) without ESGS, #Ro1=3
W
8
<<
R2
W
>>
8
<<< 1
W4 >>
2
X
W
X2
W12
X1
W
X2
Waz
Y
X2
W22
Xg
Wza
X2
W₂2
Xg
W4a
+
+
O
2
X
W33
X
Waa
Xg
W1a
X₂
W19
Y,
X
Wea
X1
W41
X
W24
X1
W21
Baby-step
Giant-step
(c) with BSGS, #Rot=2
Figure An example of GEMV using BSGS algorithm.
The BSGS algorithm is used for GEMV and GEMM reduce the number of HE rotations [7, 27]. We visualize the high-level idea of the BSGS algorithm in Figure 11. Instead of rotating each input polynomial once, the BSGS algorithm divides the rotations into two steps: baby-step and giant-step which can be formulated as
diag W
11841 @ < 11))
<< 1)ル
(4)
15

---

d2
d3
b
b
d1
d
d1
d
22
X
b
W
d2
(B - 1) + d (G 1) n1 dd'1 b
#Rot
n
Figure 12: Illustration of our BSGS algorithm for block circulant GEMM with tiling.
Here, G, B are the number of giant-step and baby-step, respectively. The total number of rotations reduced to G 2. In GEMM with dimension (dj, d2, ds). tiling needed split matrices into smaller blocks whose maximum size is HE polynomial degree n. Moreover, when extend BSGS to CirEncode, the dimension of GEMM becomes (d1, de dg and the polynomial degree becomes h. We do not encode the dj dimension into each circulant block, instead, we treat the computation cross blocks as GEMM and use the BSGS algorithm to determine the tiling size of the dj dimension. Therefore, how tile and choose B, G' is crucial minimize the number of rotations. We propose to formulate this optimization problem as a nonlinear programming problem as
6 &
# Rot = d2d2
d1ds
min
(B - 1)
(G 1) 72
s.t.
B =
d' b
(5)
d/ S di
d3 d2
d < min(
b
We give illustration of BSGS algorithm in Figure 12. The tile sizes of input and weight (di, d) and (d, d), respectively. The constraints in Equation 5 are derived from tile containing at most n elements and tile size cannot exceed the size of the matrix. This problem has small solution space. With B, G & min( 41 dz), The solution space is most min( 5 )2 allowing to directly solve it using a search algorithm with the complexity of O(minn() da da ))). Our experiments show that the search algorithm can find the optimal solution within milliscconds for all cases.
5
Complexity analysis of # Rot. We proof in Equation 6 that the complexity of #Rot with our BSGS algorithm is O(v dzds/ (nb)).
d1d2
didg (G 1) (B 1)-1)
# Rot
n
n
d1
v /2dg G) - 1)
n
> dB 1) da
(6)
0 Rot) 0 dl dddgdd
O di /dzdgn/bdy)
O( = /diddda// (nb))
16

---

(21, W. (IW.B.RR) (4.4,233
Bx 7x
+
Bxt 2x 4art
5x
fx 3xf
"x"""
22
4g
(5x"
62 72" Reif)e!
Wid
exoodd
0 mnd (x -1)
M
-32
-55
122
90
20 12x 20
12x 4x* 362 68c 60x
20r 60x 112x
36p 64g44
-M
-43
86
90
20g 12x27 20g
12:
60x 60x 20x 60x 112x 96x
44,2 36x + 64g 40x21
Figure 24),
toy example of CirEncode within a circulant convolution where (H, W,W, R)
Here we omit the last constraint Equation for simplicity.
Complexity analysis of # Mul. The complexity of Mul is given by Equation 7.
d2
d3 bdq
O(# Mul) 0 = =O(d)d2ds/(nb)
n
Boundary cases. When dj min( L/ ()² 6. the tile size of input will be dj min( 44 4x) although it's not often the case. In addition, the second constraint in Equation 5 should actually be [d 2 d n. H2s means the next nearest power of 2. This is because NTT requires the input size to be a power of 2. Consequently, consider all these boundary conditions in the search algorithm in practice.
C CirEncode for Convolutions
In this section, extend CirEncode convolutions. We denote the input, weight and output of a block circulant convolution operation as X E xC*HXW W E 2xxxxXxX = W @ X E z (CL----))x(----- R++), Here @ represents the convolution operation. We assume stride=1 for simplicity. W is block circulant matrix with respect to the first two dimensions with block size b.
Encoding within circulant block. For each circulant block, we define two encoding functions + An and TwW bxxbx Rx - An as follows:
T bx bbxBx XxW
xX) s.t. HIHH + jW + A = X A), e [6]. E [H, k E [W] = (W) s.I. wIH + (W + 1)(R - jW = W [i. 0. k), i e [b,. E [R), [R]
where other coefficients of u are set to 0. Multiplication of polynomials ÿ = w a directly gives the result of Y = W @ X as described in Theorem We defer the proof to Appendix I.3.
Theorem 3. Assuming HWb S n, given a circulant convolution kernel W E 2bbxx and input tensor X E Hxxxxx Define two polynomials u = -Tw (W) and i xX).). The polynomial
multiplication result ④ it directly maps to the result of = W @ X
where [i, iW + (W () 1) + +W + kk.
We show toy example of CirEncode for circulant convolution in Figure 13.
Encoding across circulant blocks. Consider each circulant block with input dimension (b, H. W) and weight dimension (b, 6, R, Rt as a basic unit. The computation across circulant blocks can be regarded as a GEMV with dimension (1, C F). Then we leverage SIMD diagonal encoding which the same the block circulant GEMM.
BSGS algorithm for block circulant convolution. Similar to block circulant matrix multiplication, the BSGS algorithm for block circulant convolution can be formulated an non-linear programming
17

---

b
X
b
W
C
K bd
#ot
(B - 1) +
(G
bd
HWbd n
Figure 14: Illustration of our BSGS algorithm for block circulant convolution with tiling.
problem
HWC
HWK K (G- ()-1) 1)
min Rot
(B 1) 1)+
n
s.t. B = d
(8)
HW
C K 5 5
& min
We give illustration in Figure 14 where the tile sizes of input and weight are (1, and (d, d), respectively. This problem has small solution space. With B, G S min( ). The solution space is most (min( C K
5 )) allowing to directly solve it using search algorithm with complexity of O(minn(( Ç. ))) Our experiments show that the search algorithm can find the optimal solution within milliseconds for all cases.
Complexity analysis of # Rot. We proof in Equation 9 that the complexity of Rot in block circulant convolution with our BSGS algorithm is (v W/WCC//Wm
HWC 1)+ +
HWK
# Rot
(G-1)
n
HW 2 VCK(B- ()(G-) 1)
- C(B - - -1)
O Rot) = 0 HW
VCKd)
n
-0 HW CCKn,
n V HWD
HWCK nb
Here we omit the last constraint in Equation 8 for simplicity.
Complexity analysis of # Mul. The complexity of Mul given by Equation 10.
C
K HWb
O Mul) = 0
b b
(10)
(nb))
D Why does structured pruning fail in BSGS algorithm?
HE-friendly structured pruning [38, 37] reduces the number of rotations by pruning the diagonals of weight matrices. However, this technique is not feasible in the BSGS algorithm. Figure 15
demonstrates the limitations of structured pruning in BSGS. To illustrate, consider a GEMM where
18

---

Wo
2
8 <<
1
6
22
X1
X
W1
<
93
i <<
1
64
g
W11
W1
<2
X1
X2
x
2 << 1
W21
W22
<2
X << 1
B 1 + For all rows of weight all
or
all
are 0
G +
For all columns of weight
all in the same group are 0
Figure 15: Illustration of the limitation of structured pruning in BSGS algorithm.
input and weight matrices are tiled into smaller blocks, such as X1, X2 and W11, W12, W21, W22- First focusing the multiplication between X, and W11, note that in BSGS, rotations split into baby-step and giant-step. Assuming B = 2, G 4, there are four groups, each containing two ciphertexts (i, & < 1), and eight weight polynomials wo, ..., 17 which are the eight diagonals of the weight matrix W11- Each group requires one baby-step rotation to achieve ă < and one giant-step rotation. Pruning diagonals to reduce rotations in BSGS challenging. For instance, to reduce baby-step rotation, all diagonals in the same position across different groups, such as W0,, 133, W5, W7, must be pruned. Additionally, considering tiling. X1 must multiply with all weight matrices the first row, i.c., W11, W12. Thus, to decrease a single baby-step rotation, diagonals in the same position across all groups for all first-row weight matrices must be pruned. similar challenge exists for giant-step rotations; to reduce one giant-step rotation, entire groups like wp, úh, in all first-column of the weight matrices must be pruned. Consequently, it difficult for existing structured pruning methods to meet these constraints, leading to the limitation of reducing the number of rotations.
E An example of our loss-awe aware initialization for circulant matrices
We give example of our circulant transformation initialization in Equation 11. The input matrix W is matrix and the values of and
aC(D) 3W
are artificial for simplicity.
1
OL(D)
1
2
W =
4
OW
3
|W' WI12 W'
2
3
min
1212
2 2
1=1243.52
2x22 12452
2.92
3.38
min = W
22:432
3 3 52
2-2a 44+3"
3.38
2.92
dbag
2"
1245
(11)
F Inverted Residual Fusion Algorithm
The key idea of the inverted residual fusion is to compute consecutive linear layers once with one round communication. The algorithm is described in Algorithm I where (-) (-) are the secret
19

---

shares held by the client and the server. B. B, X represent homomorphic addition, subtraction, and multiplication, respectively.
Algorithm 1: Inverted Residual Fusion Algorithm
Input: Client holds (X and Server holds (X 1) Enc(X, (nes)) Wi and W2-
Output: Client and Server get (Y2) (Y2) respectively. where
Y2 ConvBN(W (W, 2, X + ConvBN X1)).
Client encodes and encrypts [X1] 1) as Enc( (X, )0) and sends it to Server.
Server computes Enc (Y W1 R [Eno{ [X 1)) R 1)%
3 Server computes Enc X rea Y Enc rea) EY
Server computes Enc YY W2 X Enc(X +)).
5 Server samples random noise which has the same shape as Y2. Server then computes R.
Enc(Y² R) Enc(Y,
Server sends Enc R) Client and sets (Y2) R.
Client decrypts Enc( Y R) to get (Y 2) c Y2- R.
G Details of Experimental Setup
G.1 Network Architectures
We evaluate PrivCirNet on MobileNetV2 [28], ResNet-18 [55], and VIT [58]. The detailed archi- tectures across different datasets in Table should be noted that for ViT, we use ViT-lite architectures from [58].
G.2 Training Details
All baseline methods and PrivCirNet are trained using identical hyper-parameters including data augmentation, number of epochs, and others. These hyper-parameters are detailed in the 'configs' folder within our codebase. We also leverage self knowledge distillation to guide the training of the circulant networks and the pruned networks.
G.3 Computational Resources in Experiments
For CIFAR and Tiny ImageNet datasets, we train all models single NVIDIA RTX4090 GPU and a single NVIDIA A6000 GPU. For ImageNet, we train all models on 8 NVIDIA A 100 GPUs. The epochs are 300 and the total training time is around day for CIFAR and Tiny ImageNet well as ImageNet datasets.
H Additional Experimental Results
H.1 Latency breakdown of PrivCirNet
In Figure 16, we present the latency breakdown of PrivCirNet (b8) applied to MobileNetV2 and ViT CIFAR-10. It is observed that PrivCinNetsignificantyy reduces the latency associated with HE rotations and multiplications, shifting the bottleneck to nonlinear layers. Furthermore, in ViT, the
Table 8: PrivCirNet evaluation benchmarks.
Model
Layers
Params (M)
MACs
Dataset
MohileNetV2
CONV, FC, AP, 35 ReLU
2.24
0..993
CIFAR/Tiny ImageNet
MobileNetV2
CONV, FC, AP, 35 ReLU
3.5
0.32
ImageNet
ResNet-18
CONV, FC, AP, 35 ReLU
11.17
0.558
CIFAR/Tiny ImageNet
Hidden Dim=256, Number blocks=7
3.72
0.24
CIFAR
Hidden 1im=192, Numher blocks=9
2.77
0.69
Tiny ImageNet
20

---

(a) MobileNetV2
(b) Vision Transformer
Rot: 244
2.14
4.32
0.87
Total (A ttention layer)
# Mul: 2523
# Rot: 1228 (784) Mul: 22176 (14560)
.99
5.03
12.11
3.49
50.4
33.96
31.67
Non-linear
HE Multiplication
HE Rotation
HE Communication Others
Figure 16: Latency (s) breakdown of PrivCirNet (b8) on MobileNetV2 and VIT on CIFAR-I0.
(a) ResNetl8+CIFAR-000
(e) VIT+CIFAR-ION
79
1.8x
78
Top-1 Acc. (%)
77
7.9%
PrivCinNet (ours)
PrivCirNNtt (ours)
NeejeassN
70-
SpENCNN -olt
76-
Boll
3,9%1
Neujeans
Neujeans
75-
Falcon
Falcon
Cheetah
Cheetah
74
CrypTFlow2 (IIE)
Cryp (HE)
64
20
60
90
110
150
200
240
Latency (s)
Latency (s)
Figure 17: Comparison with SpENCNN and other prior-art protocols on ResNet-18 18 and ViT on CIFAR-100.
(a) RegNettCIIAAR R-10
(b) RegNee+CIIAR
(c) ComNNeXt:Tiny ImageNet
(d) ConvNeXt +ImageNet
10.35
(%)
99:35
16.5
36.
64.55
75
19
36.
94.0
43
Latency 20034)
118 3620
I Latency
Larency
Latency (8)
Figure 18: Comparison with Bolt on RegNet and ConvNeXt.
self-attention layers account for a large proportion of the total HE operations. Since these layers lack weight matrices, they cannot benefit from block circulant transformations.
H.2 Results on more networks
Results of ResNet-18 18 and VIT on CIFAR-100 Figure 17, we show the results of ResNet- 18 and ViT on CIFAR-100. We compare PrivCirNet with SOTA HE-based DNN inference frameworks and HE-friendly structured pruning method SpENCNN. We find that: 1) PrivCinNet achieves 1.8x latency reduction on ResNet-18 and 1.4x latency reduction VIT compared with SOTA frameworks Cheetah and Bolt with iso-accuracy. 2) Compared with SPENCNN, PrivCirNet achieves 3.9% and 7.9% higher accuracy on ResNet-18 and ViT with lower latency, respectively. 3) Bolt performs worse than Cheetah in ResNet-18 18 because Bolt needs to transform convolution into GEMM which increases hidden dimension by x convolutions, By contrast, PrivCinNet support both convolution and GEMM efficiently.
21

---

(a) HybReNet (2x5x3x++CIFAL)
(b) HybReNet (5x5x3x)+ +CIFA
80.0
79.5
Top-1 Acc. (%)
Top-1 Acc. (%)
79.0
78.5
78.0
76
PrivCirNet (ours)
77.5
PrivCirNat (ours)
Boll
Boll
15
20
30
40
50
60
15
30
40
50
80
Latency (s)
Latency (s)
Figure 19: Result of applying PrivCinNeton DeepReshape.
Table Accuracy and latency results when combining PrivCirNet and DeepReshape (RcLU reduc- tion).
Linear layers' latency Nonlincar layers' latency
Method
Top-1 I Acc.
(s)
(s)
HybReNet (5x5x3x) + PrivCirNet (b2)
79.99
49.52
9.4
+DeepReshape (-53% ReL.U)
79.67
49.52
4.4
HybReNet (2x5x3x) + PrivCirNet (b2)
79.49
35.25
9.0
+DeepReshape (-50% ReLU)
79.03
35.25
4.5
+DeepReshape (-72% ReLU)
77.91
35.25
2.5
Results of RegNet and ConvNeXt In Figure 18, we show the results of RegNet [59] and Con- vNeXt [60] on CIFAR. We compare PrivCirNet with SOTA HE-based DNN inference framework Bolt.
Comparion with DeepReshape [61] DeepReshape optimizes ReLUs and FLOPs by designing series of more FLOPs-efficient networks, dubbed HybReNets while pruning the ReLU layers. DeepReshape achieves a better latency-ReLU trade-off than SENet [32], SNL [30]. etc. DeepReshape and PrivCirNet are orthogonal and can applied together further reduce the inference latency.
In Figure and Table 9, we show the application of PrivCirNet to HybReNets on CIFAR-100, which also yields promising results. We apply the ReLUU pruning method proposed in DeepReshape reduce the latency of nonlinear layers.
From the results, we can see that PrivCinNet is effective when combined with DeepReshape, achieving significant latency reduction in both linear and nonlinear layers.
Discussion the impact of selecting different baseline networks The varying accuracy degra- dation observed across different baseline networks (MobileNetV2, ResNet, HybReNet, RegNet, ConvNeXt) can be partly attributed to the differing proportions of parameters occupied by standard convolutional layers. For instance, in ConvNeXt, 98% of the parameters are derived from standard convolution, with less than 2% from sespth-wiseggroup-iiii pression potential using PrivCirNet. In contrast, standard convolution parameters account for only 64% and 78% of RegNet and Nob, respectively. As a result, RegNet and MobileNetV2 exhibit larger accuracy degradation at higher compression rates.
convolution, providing significant com-
22

---

I
Proofs
I.1 Proof of Theorem
For a given input matrix X and a circulant matrix W, we have
W E z W = W (b - i +) mod b), Vi E [b]. E [b]
(12)
e bxd [i, V [6]. E [d1]
The matrix multiplication result
WX bxd, Y[,,]]] Σ
mod j] (13) Wii 1 Σ w
k=
The polynomials & xx (X) Tw (W) after CirEncode are
A, 2 [id] و| x(i.j) [i [di] ù E An. v id1] = =
(14)
mod 6). Vi E [b],
The other slots of de are 0. The polynomial multiplication result ý directly gives the matrix multiplication result Y as
x i An
b-
gldd + +
wi(i k)d1lā(kdr + +
(15)
W (b (b-i+ mod 6j [k,
W = Y[AJJ]
Besides, we extend the definition of w[ de [bd] + :].
Explanation of CirEncode Modulo -= CirEncode performs Discrete Fourier Transform (DFT)
modulo -. on the plaintext. After the DFT, applies SIMD encoding enable element- multiplication. The correctness demonstrated by the equation DFT(() @ DFT()) = DFT (w x mod nn
1.2 Proof of Theorem 2
Given M circulant weight matrices Wo...., WAS A1 Zbxb and input matrices Xp.... .p...... XM- Zbxd1, define the polynomials ú., = (W m and &.. xx xx (Xm) with m E [M] following the
coefficient packing in Theorem 1. We have:
(DFT( DFT SIMD x (DFT( DFT (())((0)) O DF ... (()((M- o ()
(16)
(DFT x 2o)l... (10 x 2M-1)) Coeff
(DFT (FT((M-))))
Then perform inverse DFT and directly extract elements following Theorem 1 from 9m to
get Y.., Ym E [M]. The second and the third lines Equation 16 follow directly from Lemma while the last line is derived from Theorem 1. Through Equation 16, simultaneously evaluate M circulant GEMMS with CirEncode.
I.3 Proof of Theorem
For given input X and a circulant weight W of convolution, we have
W& E bxxxxRxR Wii = W [0, (b - +) mod b,: w [b j i) mod 6, :] Vi [6] [6] (17)
E zxxHx Xii.j,,)VVi [6], Vj [M], vk E [W]
23

---

The convolution result Y is
= W WXXE E
b- R---I--
(18)
ΣΣΣ
Wi Ajx(i + m, m,kk- + h]
1= m=0 h=0
The polynomials & - xx{(), Tw (W) after CirEncode are
E A. 2 WWW - jW + k] = x( k] An WHW + (W - ( 1) - = o.
(19)
The other slots of de are set 0. The polynomial multiplication result ÿ directly gives the convolution result Y as
E= An 5iil + (W + 1)(R + jW + + ΣΣΣ
1-1R-18-1
1=0 m=0 h=0
(w[(i - H) + (W + 1) 1) mW k|al//W + (j m)W + (k h)))
R-1R-1
ΣΣΣ mi,,m,,,,x(LL, + m, k + h]
Besides, we extend the definition of ui( H)H +...] 20 + DHW +.. (20)
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: /
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
Proofs of all theoretical results are available in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our code and checkpoints are available Git Hub.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [Yes]
Justification:
Our code and checkpoints are available on Git Hub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
mublic/guides Soaiidee/Codeuuuisssiiiiiii oeeioonooyyi ooiicylyyyy)oo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //tpps..cpppu...///// ctcccc/pp.. wwtpccccpppccc.eee.ce.......ceee gwtp////d////eee// httgg////o/oouuubiii
onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training details are available in our code on Git Hub.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We conduct experiments on multiple models and datasets, which require significant computational resources. In addition, our code has been released, making it easy reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
27

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information about our computing resources is available in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttpp:///nuris.... wttppppp.cccpppeeateeee httpppulcc/hhhcccuueeleeee..eeee ctwuidelelllllleeccccccc ines?
Question:
Answer: [Yes]
Justification: /
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: /
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: /
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: /
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: /
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: /
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "mO3AK9Blgs", "reviewer": "Reviewer_eRSG", "summary": "The authors have proposed a co-design method for making the Homomorphic encryption (HE) evaluation faster in private inference. Specifically, they used a new HE encoding mechanism to leverage the properties of the black-circulant matrix to reduce the HE rotations and ciphertext-plaintext multiplications.   The experiments are performed on various CNN models and ViT models with multiple datasets.", "questions": "1. For ViT experiments on CIFAR, did you use pre-trained ImageNet mode?\n\n2. Why MobileNetV2 is used for benchmarking? If FLOPs efficiency is the reason, it should also be evaluated on RegNet-x [4] and ConvNeXt [5] models, and if required, by substituting complex non-linearities with privacy-friendly counterparts (LN with BN and GELU with ReLU). \n\n3. Which Crypto-primitive is used for evaluating the nonlinear computations? \n\n4. What is the overhead of finding the optimal block size using second-order information? That is, how much time is required to find the optimal block size for each layer? How does this timing overhead increase with the network size, particularly in  wider networks (e.g., in HybReNets [3])\n\n[4] Radosavovic et al.,  Designing Network Design Spaces, CVPR 2020. \n\n[5] Woo et al., ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders, CVPR 2023.\n\n\n*I'm open to improving the score if the key concerns are addressed in the rebuttal*", "limitations": "Addressed in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Authors have tailored the SOTA HE algorithm, BSGS implemented in BOLT, to leverage the block-circulant matrix properties to further speed up the HE evaluation in private inference. They have implemented various crypto algorithms, which require a reasonable effort in C++. \n\n2. Thorogh experimentation, including ViT models on ImageNet, TinyImagNet, and CIFAR-10/100 datasets. \n\n3. The paper is well-structured and thoroughly written, making it easy to follow even for those who are not experts in this field.", "weaknesses": "$\\bullet$ **Limited Novelty** The idea of employing black-circulant matrices for faster convolution, both in plaintext [1] and ciphertext [2], is not new. The authors have just tailored them for the BGSG algorithm, by making the block-size variable. \n\nMoreover, the efficiency of the proposed encoding method, CirEncode, has been validated with a relatively smaller hidden size. For example, ViT with hidden dimensions 192 and 256. In contrast, the BERT-based model, used in BOLT, has a hidden dimension of 768. The efficacy of the encoding mechanism should be validated against 768 and/or 1024 hidden dimensions. \n\n$\\bullet$ **Compariosn against HybReNets** Authors have shown comparison with ResNet18 baseline in Figure 9. However, recently, there have been more efficient baselines for private inference have been devised such as HybReNets (e.g., HRN-5x5x3x and HRN-2x5x3x) [3]. These privacy-friendly baseline networks have a relatively higher number of channels in deeper layers, thus, the efficacy of the encoding mechanism should be validated with the networks with a higher number of channels. \n\n\n\n$\\bullet$ **Writing** \nThe year is missing in citations 27 and 38. \n\n \n[1] Ding et al., CirCNN: Accelerating and Compressing Deep Neural Networks Using Block-Circulant Weight Matrices, MICRO 2017. \n\n\n[2]  Lou et al., Falcon: Fast Spectral Inference on Encrypted Data, NeurIPS 2020.\n\n\n[3] Jha et al., DeepReShape: Redesigning Neural Networks for Efficient Private Inference, TMLR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer eRSG's constructive feedback, which has helped us improve our work! We have conducted all the additional experiments mentioned in the review and will be added to our final version. **The results are included in the PDF attached to the global response**, including comparisons with Bolt (S&P'24) under larger hidden dimensions (Table 1), the combination of PrivCirNet and DeepReshape (Tables 2 and 3), and results on RegNet and ConvNeXt (Table 4). Below, we address each of your concerns.\n***\n**[To W1, concerns on novelty]**\n\n**The contribution of PrivCirNet is not in proposing the circulant matrix, but in its application to SOTA networks to achieve better latency-accuracy trade-off in private inference.**\n\nWhile [r44,r45,r25] use block circulant matrices in plaintext and ciphertext, **there remain two unresolved problems in both domains:** (1) how to initialize circulant matrices, and (2) how to determine block sizes for each layer. As a result, it is hard for [r44, r45, r25] to apply block circulant matrices to more efficient networks, e.g., MobileNetV2, Transformers, etc. PrivCirNet addresses these problems with new algorithms, achieving a superior accuracy-latency trade-off.\n\nIn the ciphertext domain, [r25] cannot fully leverage block circulant matrices, resulting in limited or even increased latency. Compared with [r25],  PrivCirNet introduces several core innovations:\n\n- Adopts a hybrid HE+MPC framework, eliminating the computationally expensive discrete Fourier transform (DFT) on the ciphertext.\n- **Maximizes the potential of block circulant matrices by customizing the HE encoding algorithm**, reducing computation latency proportional to the block size.\n\nA comprehensive comparison between PrivCirNet and [r44,r45,r25] is summarized as follows:\n|Method|Application|Initialization method|Variable block size|Block size assignment|Customized Encoding Method|Network|\n|-|-|-|-|-|-|-|\n|CirCNN, CircConv [r44,r45]|Accelerate convolution in plaintext|Forbenius norm|√|Uniform/Manually set|/|ConvNets|\n|Falcon [r25]|Accelerate end-to-end HE-based private inference|Forbenius norm|×|Only uniform|×|Three-layer network|\n|PrivCirNet (ours)|Accelerate hybrid HE+MPC private inference|Loss-aware|√| Latency-aware block size assignment|√|ConvNets, Transformers|\n***\n**[To W1, comparison under a large hidden dimension]**\n\n**CirEncode is effective for any layer dimensions** as shown in Table 3 of our paper. **As shown in Table 1 in the PDF attached to the global response**, comparing with Bolt [r7] using BERT-base, PrivCirNet achieves $2.7\\sim 7.5\\times$ latency reduction under large hidden dimensions, consistent with our theoretical analysis and experimental results. \n\n***\n\n**[To W2, comparison with DeepReshape (TMLR'24, April 2024) ]**\n\nThank you for pointing out the work DeepReshape [a1], which helps to consolidate our work. DeepReshape optimizes both ReLUs and FLOPs by designing a series of more FLOPs-efficient networks, dubbed HybReNets while pruning the ReLU layers. DeepReshape achieves a better latency-ReLU trade-off compared with SENet [r32], SNL [r30], etc. We believe **DeepReshape and PrivCirNet are orthogonal** and can be applied together to further reduce the inference latency.\n\n**In Table 2 and Table 3 in the PDF attached to the global response**, we show the application of PrivCirNet to HybReNets [a1] on CIFAR-100, which also yields promising results. We apply the ReLU pruning method proposed in DeepReshape to further reduce the latency of nonlinear layers. \n\nFrom the results, we can see that PrivCirNet is effective when combined with DeepReshape, achieving significant latency reduction in both linear and nonlinear layers. We will include these experiments and cite DeepReshape in our final version. Thank you again for your valuable advice!\n***\n**[To W3, missing year in citations 27 and 38]**\n\nThank you for pointing out the typo! We will correct this in our final version. \n\n***\n\n**[To Q1, ViT training]**\n\nWe do not pretrain the model on ImageNet. We first train our ViT model from scratch on CIFAR following [r58], then apply circulant transformation and finetune the model. We will add this detail to our final version.\n***\n**[To Q2, why choose MobileNetV2?]**\n\nMobileNetV2 is a classic efficient network. The inverted residual block and its variants are widely used in efficient network design, including EfficientNet [a4], ConvNeXt [a3], etc. **PrivCirNet can be applied to any convolutions or fully connected layers.** **In Table 4 in the PDF attached to the global response**, we benchmark PrivCirNet on RegNet [a2] and ConvNeXt [a3]. The results are consistent with MobileNetV2.\n***\n**[To Q3, Crypto-primitive used for nonlinear layers]**\n\n**See the first part of the global response.**\n***\n**[To Q4, the overhead of finding optimal block size]**\n\nFor CIFAR and Tiny ImageNet, our block size assignment algorithm takes **less than 20 seconds** on a single RTX4090. For ImageNet, our algorithm randomly samples 100,000 images in the training dataset and takes **less than 5 minutes** on a single RTX4090. The time cost comes from running a backpropagation. We will add this description to our final version.\n***\n**We sincerely appreciate the valuable, detailed advice from reviewer eRSG. We take all your suggestions into account in our final version. If you feel that the above improvements help clear up your doubts and further improve our work, you can kindly consider a re-evaluation, thank you!**\n***\n[r7,r25,r30,r32,r44,r45,r58] represent the 7th, 25th, 30th, 32th, 44th, 45th, 58th references cited in our original submission.\n\n[a1] Jha et al., DeepReShape: Redesigning Neural Networks for Efficient Private Inference, TMLR 2024.\n\n[a2] Radosavovic et al., Designing Network Design Spaces, CVPR 2020.\n\n[a3] Woo et al., ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders, CVPR 2023.\n\n[a4] Tan et al., Efficientnet: Rethinking model scaling for convolutional neural networks, ICML 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pjlZpHqbI0", "reviewer": "Reviewer_eLA6", "summary": "The paper introduces PrivCirNet, a framework designed to enhance the efficiency of private DNN inference using homomorphic encryption (HE) and MPC schemes. The key contributions are as follows.\n1. By converting DNN weights into block circulant matrices, the framework transforms general matrix-vector multiplications into HE-friendly 1-dimensional convolutions, significantly reducing computational overhead.\n2. PrivCirNet customizes the HE encoding algorithm to fully leverage the block circulant transformation, reducing computation latency in proportion to the block size.\n3. The framework includes a latency-aware formulation to search for optimal layer-wise block size assignments using second-order information.\n4. PrivCirNet employs layer fusion techniques to further minimize inference costs.\n5. The framework demonstrates substantial improvements over state-of-the-art HE-based frameworks (e.g., Bolt) and HE-friendly pruning methods (e.g., SpENCNN) in terms of both latency and accuracy across various models (ResNet-18, Vision Transformer, MobileNetV2) and datasets (CIFAR-10, CIFAR-100, Tiny ImageNet, ImageNet).", "questions": "In Figure 9, the comparison of latency and accuracy is conducted against the worst-case scenarios of existing work. Is this comparison fair?", "limitations": "They did adequately.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The use of block circulant transformation for optimizing HE-based DNN inference at the HE/MPC hybrid approach is novel and innovative. The paper includes thorough evaluations and comparisons with existing methods, providing strong evidence of the proposed framework's effectiveness. The structure and presentation of the paper are clear, making the methodology and results easy to understand. Finally, the framework addresses a critical issue in privacy-preserving machine learning, offering substantial improvements in both efficiency and accuracy.", "weaknesses": "This paper does not provide the actual implementation code needed to reproduce the simulation results. Additionally, while the paper offers an explanation of homomorphic encryption (HE), it does not clearly present the implementation details for multi-party computation (MPC). The results report overall latency without distinguishing between the HE part and the MPC part, making it difficult to discern the extent of performance improvement specifically attributed to HE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support and the thorough comments, which have greatly helped us improve our work! We appreciate that the novelty, effectiveness, and importance of PrivCirNet are acknowledged. Below we list our responses to each of the comments:\n\n***\n\n\n**[Our implementation code of private inference]**\n\nOur C++ implementation of private inference is based on OpenCheetah [r10] and the SEAL library [r52]. We are organizing the code and will release our C++ implementation upon acceptance.\n\n***\n\n\n**[The implementation details for multi-party computation (MPC) and the performance improvement attributed to HE]**\n\n**See the first part of the global response.**\n\n***\n\n\n**[To Question, Figure 9 marks the points with the highest compression]**\n\nIn Figure 9, compared with HE-based frameworks, PrivCirNet achieves $1.3\\sim 2.2\\times$ latency reduction with iso-accuracy, which is also the accuracy of the uncompressed model. \n\nWhen compared with the structured pruning method SPENCNN, we marked the points with the highest compression ratios because **compression methods are more important for more compact models, and thus the accuracy improves the most at the point of minimum latency**. We will improve the description in the updated version. For example, \"Compared with SPENCNN in ViT and Tiny ImageNet, PrivCirNet achieves 1.3%, 2.8%, and 13% higher accuracy under iso-latency 370s, 310s, and 280s, respectively.\"\n\n***\n\n\n**Thanks again for the valuable comments which make our experiments more solid and robust. We will add all of these discussions to our final version. We hope you could kindly consider a re-evaluation if you find our responses effective. Thank you!**\n\n***\n\n[r10, r52] represent the 10th and 52th references cited in our original submission.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "msn6jNHMOe", "reviewer": "Reviewer_wNvj", "summary": "This paper proposes an optimization for linear layers of secure inference systems. The authors propose a linear layer evaluation protocol that can efficiently compute linear layers when the model weights are circulant (diagonally repeating). They also propose optimizations to determine the optimal block size to achieve a balanced tradeoff between accuracy and latency. The authors demonstrated the linear layer efficiency with extensive evaluations.", "questions": "Overall I think this paper is interesting. I have some concerns about some statements and comparisons with the prior work BOLT (S&P'24).\n\n- In the motivation section, you mentioned that the linear layers are the bottleneck of BOLT. But from BOLT's results, the nonlinear layers seem to occupy more than 70% of the runtime in the WAN setting. I think it should be made clear that the linear layers become the bottleneck when you consider very fast network settings.\n- It should be made clear that the proposed method is for circulant weight matrix only instead of general matrix multiplications, the notation of GEMM is very misleading, and I think it should be replaced.\n- BOLT is specifically designed and optimized for transformers, I'm wondering what adaptations have you made to BOLT for the models considered in the paper? It might be not fair to compare your protocol to BOLT as it's not specifically designed for CNNs.\n- In BOLT, you can also make the weight matrix circulant. In this case, the multiplications between weights and ciphertext inputs should be very fast as you just need to multiply a scalar to the ciphertext. Can the authors compare this simple adaptation? Also, it should be made clear when comparing with prior methods that the prior methods are for general matrix multiplications, but your proposal is not.\n- I'm wondering how the nonlinear layers are evaluated. Which crypto primitive are you using for that? Does your code include the MPC part?", "limitations": "See my concerns in the Question section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Improving the efficiency of secure inference systems is an important problem.\n- The idea of proposing HE-friendly linear layer evaluation for circulant weights is interesting.\n- The proposed method is sound with decent performance.", "weaknesses": "- Some of the statements are misleading and the presentation can be further improved to avoid misunderstandings.\n- The details of how nonlinear layers are evaluated are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support and professional, detailed feedback! We are also grateful to Reviewer wNvj for evaluating our work as \"an interesting paper\". See below for the answers to your questions and comments.\n\n***\n\n**[To Weakness1 and Question2, misleading notation of GEMM]**\n\nWe highly appreciate the helpful advice to avoid misleading readers. In our paper, we use \"GEMM\" to denote \"circulant matrix multiplication\" for PrivCirNet, which may mislead readers. We will update the statements to distinguish between \"GEMM\" and \"circulant matrix multiplication\" to mitigate any potential misunderstanding. Thanks again for your valuable suggestion!\n\n***\n\n**[To Weakness2 and Question5, the details of nonlinear layer evaluation]**\n\nFor the details of the nonlinear layer evaluation, **see the first part of the global response.**\n\nAs for our C++ implementation of private inference, we are organizing the code and will release it upon acceptance.\n\n***\n\n**[To Question1, the bottleneck of Bolt]**\n\nThanks for your professional advice! In Figure 1, we show that linear layers account for more than 75% of the total latency. We will add an explanation in our updated manuscript that the experiment was conducted at a bandwidth of 3Gbps.\n\nAdditionally, Bolt uses IKNP OT [a1] for nonlinear layers, which can be improved by using VOLE OT [a2] as implemented in OpenCheetah [r10], offering an order of magnitude smaller communication overhead. Then even with lower bandwidth, linear layers remain a significant bottleneck. Related content is also discussed in Bumblebee (NDSS'25) [r22].\n\n***\n\n**[To Question3, how to apply Bolt to CNNs?]**\n\nBolt's protocol is designed for matrix multiplication rather than convolution. To evaluate Bolt on CNNs, we transform convolution into matrix multiplication by $\\operatorname{img2col}$ algorithm. For example, given a weight kernel $W\\in \\mathbb{Z}^{K\\times C\\times R\\times R}$ and an input matrix $X\\in \\mathbb{Z}^{C\\times H\\times W}$, $\\operatorname{img2col}$ transforms $W,X$ to $W'\\in \\mathbb{Z}^{K\\times (C\\times R\\times R)}, X'\\in \\mathbb{Z}^{(C\\times R\\times R)\\times (H'\\times W')}$, where $H',W'$ are the output resolutions. We then use Bolt's matrix multiplication protocol to evaluate the convolution. \n\nHowever, this transformation increases the dimension and final latency. Hence, for CNNs with $3\\times 3$ kernels like ResNet-18, **we focus on the comparison with Cheetah (USENIX Security'22) [r10] and Neujeans (CCS'24) [r27]** which are SOTAs for CNNs. As shown in Figure 9 of our paper, PrivCirNet still achieves $1.4\\sim 2.2\\times $ latency reduction with iso-accuracy. \n\nWe will add this illustration to our final version.\n\n***\n\n**[To Question4, simply extending Bolt to circulant matrix multiplication]**\n\nIn PrivCirNet, we have tried to adapt the encoding method proposed in Bolt to block circulant matrix multiplication. As shown in Figure 2 of our paper, SIMD encoding like Bolt cannot effectively utilize circulant matrices. For example, assume $W=\\begin{bmatrix} 1 & 2 \\\\\\\\ 2 & 1 \\end{bmatrix}\\in \\mathbb{Z}^{2\\times 2}$ is a circulant matrix, and the input matrix is $X=[3,4]^T\\in \\mathbb{Z}^{2\\times 1}$. Although we only need to multiply $[3,4]$ with scalar $1$, in SIMD encoding we still need to conduct element-wise multiplication $[3,4]\\odot[1,1]$, leading to no benefits compared to GEMM. \n\nOn the other hand, coefficient encoding can utilize circulant matrix multiplication but introduce extra repeating elements when handling block-circulant matrix multiplication. To better explain, let's consider a toy example: $W=\\begin{bmatrix} -1 & 2 &1 & 3 \\\\\\\\ 2 & -1 & 3& 1 \\end{bmatrix}, X=\\begin{bmatrix} 5 & 4 & -2 & 3  \\end{bmatrix}^T$, with a block size $b=2$. We encode $W$ to $\\hat{w}=3+x+(2-x)x^3$. When encoding $X$, we need to repeat elements in $X$ to ensure all 2 permutations of $X$ appear in $\\hat{x}$, that is, $\\hat{x}=5+4x+5x^2+(-2+3x-2x^2)x^3$. Then $\\hat{y}=\\hat{w}\\times \\hat{x}=\\ldots+10x^4+3x^5+\\ldots$ contains the correct result of $WX$. The theoretical complexity of this approach is shown in the table below.\n\n|                  | # mul                       | # rot                      | # cts                                          | Encoding consistency |\n| ---------------- | --------------------------- | -------------------------- | ---------------------------------------------- | -------------------- |\n| Coefficient only | $O(d_1d_2d_3(2b-1)/(b^2n))$ | 0                          | $O(d_1d_2(2b-1)/(nb)+\\lceil d_1/n \\rceil d_3)$ | ×                    |\n| CirEncode        | $O(d_1d_2d_3/(bn))$         | $O(\\sqrt{d_1d_2d_3/(bn)})$ | $O(d_1(d_2+d_3)/n)$                            | √                    |\n\nThere are two drawbacks of this approach: (1) The number of ciphertexts needed to be transferred increases, resulting in significant communication costs. Additionally, the number of multiplication is higher than CirEncode. (2) The packing of input and output is **inconsistent**, hindering consecutive computation on the output.\n\nConsequently, CirEncode combines the advantages of both SIMD encoding and coefficient encoding schemes and maximizes the potential of the circulant matrices. We will add this important discussion to the appendix in our final version.\n\n***\n\n**Last, thanks so much for helping us improve this work through your professional perspective. If you have any additional questions or anything you would like to discuss in more detail, please feel free to let us know. If you find we have successfully addressed your worries, please kindly consider re-evaluating our work. Thanks a lot!**\n\n***\n\n[r10,r22,r27] represent the 10th, 22th, and 27th references cited in our original submission.\n\n[a1] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, \"Extending Oblivious Transfers Efficiently,\" in CRYPTO, 2003, pp. 145–161.\n\n[a2] Boyle, Elette, et al. \"Efficient two-round OT extension and silent non-interactive secure computation.\" CCS 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fSxEyLQRqK", "reviewer": "Reviewer_mVR6", "summary": "Proposing the use of cyclic blocks for matrix multiplication to accelerate privacy-preserving inference in neural networks.", "questions": "1. model parameters tend to be fractional, why choose bfv over the more fractional friendly ckks?\n2. why is the table layout inconsistent? For example, table 1 and table 2.\n3. again in table 4, why the accuracy of MobileNetV2 is higher after 50% compression of the proposed method than uncompressed? This is inconsistent with the intuition of information loss after compression.\n4. the polynomial modulus used in Figure 4 is x^16-1, but the usual BFV encryption has a polynomial modulus of x^N+1. isn't the article using the original BFV? From the appendix and the supplementary material submitted, I can find no correlation.", "limitations": "Better to solve the limitions.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "PrivCirNet features a novel encoding algorithm optimized for block circulant weight matrices, dubbed CirEncode, that reduces the HE computation in proportion to block size. PrivCirNet also co-design a latency-aware optimization formulation for layer-wise block size assignment based on second-order information.", "weaknesses": "The model proposed by the authors is interactive privacy-preserving neural network reasoning, which only provides comparisons of reasoning latency with comparison objects and lacks comparative experiments with communication traffic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer mVR6's feedback and we will address each of the questions as follows.\n\n***\n\n**[To weakness, lack of communication cost comparison]**\n\nFirst, we **do have a communication comparison for linear layers** in Table 3 (see \"# Ciphertexts\"). CirEncode minimizes the communication of HE ciphertexts. Through the analytical comparison, we make it clear that our method shares the same communication complexity as Neujeans (CCS'24) [r7] for CNNs and Bolt (S&P'24) [r27] for Transformers. \n\nSecond, **PrivCirNet focuses on optimizing HE computation complexity and does not specifically optimize the communication cost, as demonstrated clearly in the experimental results.**\n\nThe detailed communication cost of PrivCirNet is as follows and will be included in the appendix in our final version. The communication improvement comes from the layer fusion proposed in Section 3.4.\n\n|Model|Dataset|Linear layers' communication (MB)|Nonlinear layers' communication (MB)|\n|-|-|-|-|\n||| PrivCirNet / Bolt (S&P'24) / Neujeans (CCS'24) |The same for each baseline we implement|\n|MobileNetV2|ImageNet|505 / 635 / 526|100|\n|ResNet-18|Tiny ImageNet|114 / 246 / 121|50|\n|ViT|Tiny ImageNet|710 / 710 / 699|3159|\n\n***\n\n**[To Q1, why use BFV instead of CKKS?]**\n\nIt is common for neural networks to run on integers through quantization, such as the fixed point quantization adopted by CryptoNets (ICML'16) [r8]. In our paper, we follow the hybrid HE+MPC strategy as clearly explained in the introduction. **BFV is the mainstream scheme in hybrid HE+MPC frameworks and all baseline frameworks compared in our paper use the BFV scheme**, e.g., CryptoNets (ICML'16) [r8], Gazelle (USENIX security'18) [r9], Delphi (USENIX security'20) [r20], CrypTFlow2 (CCS'20) [r6], Cheetah (USENIX security'22) [r10], Iron (NeurIPS'22) [r24], Neujeans (CCS'24) [r27], Bolt (S&P'24) [r7], etc.\n\nBesides, **applying CKKS in a hybrid HE+MPC framework is vulnerable to attacks (EuroCrypt'21) [a1]**. When transforming from CKKS to secret sharing, its low-end noise may leak information, and there is currently no clear method to solve this problem [a1]. On the contrary, BFV can be safely transformed into secret sharing through *noise flooding* [a2].\n\n***\n\n**[To Q2, why is the table layout inconsistent, i.e., table 1 and table 2?]**\n\nWe use a text wrapping format in Table 1 to save space, which is **commonly used** in papers published in NeurIPS, e.g., \"Privacy Auditing with One (1) Training Run\" (NeurIPS 2023 Outstanding Paper). We will consider using a more beautiful layout in the final version.\n\n***\n\n**[To Q3, why the accuracy of MobileNetV2 is higher after 50% compression?]**\n\nNeural networks tend to be over-parameterized and network compression can serve as a regularization method that improves network performance. **This phenomenon has been widely observed in works concerning network compression**, such as quantization [a3-a6], pruning [a7-a10], and circulant transformation [r45]. \n\n***\n\n**[To Q4, why CirEncode mod $x^n-1$?]**\n\nCirEncode conducts (inverse) discrete Fourier transform (IDFT/DFT) (mod $x^n-1$) **in plaintext** **which is independent of BFV's operations in the ciphertext.** $\\mod x^n+1$ is a requirement for BFV's ciphertext polynomial multiplication. **Our DFT is done in plaintext before encryption and does not violate BFV requirements. This approach is also adopted in Neujeans (CCS'24) [r27].**\n\nHere's an example to illustrate this process: Assume $W=\\begin{bmatrix} 1 & 2 \\\\\\\\ 2 & 1 \\end{bmatrix}\\in \\mathbb{Z}^{2\\times 2}$ is a circulant matrix, input matrix $X=[3,4]^T\\in \\mathbb{Z}^{2\\times 1}$. We first encode these matrices into vectors: $\\hat{w}=[1,2], \\hat{x}=[3,4]$. Next, we conduct DFT to obtain $\\text{DFT}(\\hat{w})=[3,114688], \\text{DFT}(\\hat{x})=[7,114688]$. It's important to emphasize that $\\text{DFT}(\\hat{w}),\\text{DFT}(\\hat{x})$ are still **plaintext vectors/polynomials**. Then we apply BFV SIMD encoding to get the element-wise multiplication result: $\\text{DFT}(\\hat{w})\\odot \\text{DFT}(\\hat{x})$, where $\\odot$ represents element-wise multiplication. That is, we get $\\text{Encrypt}([3,114688]\\odot[7,114688])$. \n\nThe correctness is verified by $\\text{IDFT}([3,114688] \\odot [7,114688])=[11,10]=W\\cdot X$. Here, the modulus of DFT is $114689$, which needs to be consistent with the plaintext modulus in BFV HE.\n\nWe will add this discussion to the appendix in our final version.\n\n***\n\n**[Concern Regarding Reviewer mVR6 Conduct]**\n\n**Reviewer mVR6 did not raise any issues or weaknesses related to the substantive content of our paper, which made it very hard to support the strong reject decision. We request the reviewer to re-evaluate our paper based on our rebuttal materials.**\n\n***\n\n[r6,r7,r8,r9,r10,r20,r24,r27,r45] represent the 6th, 7th, 8th, 9th, 10th, 20th, 24th, 27th, and 45th references cited in our original submission.\n\n[a1] Li, Baiyu, and Daniele Micciancio. \"On the security of homomorphic encryption on approximate numbers.\" EUROCRYPT, 2021.\n\n[a2]  Gentry, Craig. *A fully homomorphic encryption scheme*. Stanford university, 2009.\n\n[a3] Esser, et al. \"Learned step size quantization.\" ICLR 2020.\n\n[a4] Li, Yanjing, et al. \"Q-vit: Accurate and fully quantized low-bit vision transformer.\" NIPS 2022.\n\n[a5] Yamamoto, Kohei. \"Learnable companding quantization for accurate low-bit neural networks.\" CVPR 2021.\n\n[a6] Li, Yuhang, et al. \"Additive powers-of-two quantization: An efficient non-uniform discretization for neural networks.\" ICML 2020.\n\n[a7] Han, Song, et al. \"Learning both weights and connections for efficient neural network.\" NIPS 2015.\n\n[a8] Zhang, Yuxin, et al. \"Bi-directional masks for efficient n: M sparse training.\" ICML 2023.\n\n[a9] Zhou, Aojun, et al. \"Learning n: m fine-grained structured sparse neural networks from scratch.\" ICLR 2021.\n\n[a10] Zhang, Yuxin, et al. \"Learning best combination for efficient n: M sparsity.\" NIPS 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**[1. Implementation details and latency for nonlinear layers]**

We utilize HE to evaluate linear layers and MPC to evaluate nonlinear layers. For nonlinear layers, we follow Cheetah [1] to evaluate the ReLU function (Section 4 in Cheetah) and Bolt [2] to evaluate GeLU, LayerNorm, and Softmax functions (Section 5 in Bolt). Additionally, we adopt VOLE-style Oblivious Transfer (OT) [3] for all the nonlinear layers, which enables us to further reduce the communication for GeLU, LayerNorm, and Softmax compared to Bolt.

**PrivCirNet focuses on optimizing the latency of linear layers which is the bottleneck**, the latency shown in Figures 8 and 9 of our paper represents the latency of linear layers. In Table 5 of our paper, we show the total latency of PrivCirNet, where the bottleneck is the latency of linear layers. Below we further show the latency breakdown of MPC (for nonlinear) and HE (for linear) parts across different models under the LAN setting.

We thank the reviewers for pointing this out and will add the explanation to the experimental results and these additional results to the appendix in our final version.

| Network     | Dataset       | Latency of Nonlinear Layers (s) | Latency of Linear Layers (Bolt) (s) | Latency of Linear Layers (Ours with block size 8) (s) |
| ----------- | ------------- | ------------------------------- | ----------------------------------- | ------------------------------------------- |
| MobileNetV2 | ImageNet      | 92.0                            | 137.8                               | 27.7                                        |
| ResNet-18   | Tiny ImageNet | 12.6                            | 156.4                               | 11.2                                        |
| ViT         | Tiny ImageNet | 190.6                           | 479.6                               | 254.8                                       |

***

[1] Huang, Zhicong, et al. "Cheetah: Lean and fast secure {Two-Party} deep neural network inference." USENIX Security 2022.

[2] Pang, Qi, et al. "BOLT: Privacy-Preserving, Accurate and Efficient Inference for Transformers." *IEEE S&P* (2024).

[3] Boyle, Elette, et al. "Efficient two-round OT extension and silent non-interactive secure computation." CCS 2019.

***

**[2. Additional experimental results]**

In response to the questions of Reviewer eRSG, we further conducted the following experiments, and the results are included in the attached PDF:

- Table 1: Comparison of Bolt and PrivCirNet for matrix multiplication with larger hidden dimensions in the BERT model. This experiment demonstrates that PrivCirNet achieves $2.7\sim 7.5\times $ latency reduction compared to Bolt under larger hidden dimensions, consistent with our theoretical analysis and experimental results.
- Table 2: Accuracy and latency results when applying PrivCirNet to HybReNets proposed in DeepReshape. The result demonstrates the effectiveness of applying PrivCirNet to HybReNets (DeepReshape).
- Table 3: Accuracy and latency results when combining PrivCirNet and DeepReshape (ReLU reduction). This experiment demonstrates that PrivCirNet and DeepReshape can be applied together to significantly reduce the latency of both linear and nonlinear layers.
- Table 4: Accuracy and latency results when applying PrivCirNet to RegNet and ConvNeXt on CIFAR-10. From the result, we can find that PrivCirNet achieves $2.0\sim 6.8\times$ latency reduction on RegNet and ConvNeXt, which is consistent with the result on MobileNetV2.

We believe these results demonstrate that PrivCirNet achieves consistent latency and accuracy benefits over different network architectures. We will also add these experimental results in our final version.

Meta-review: The work studies reducing the computation overhead over HE-based neural network inference. It proposes PrivCirNet, a protocol/network co-optimization framework based on block circulant transformation.

The final recommendation of the work is unanimously acceptance (6, 6, 6, 5).

Reducing communication overhead in HE is an important problem. 
The proposed method is novel and technically sound. 
The paper is well written. 
The effectiveness of the proposed method is evaluated with comprehensive experiments. 

For the final version, please incorporate the results and discussions in the rebuttal and also address the following remaining points from reviewers:

eRSG
> a brief discussion on the impact of selecting different baseline networks (MobileNetV2/ResNet/HybReNets/RegNets/ConvNeXt) on the accuracy degradation with various block sizes should be included in the draft. 


mVR6
> 1. Since your work is closely related to plaintext encoding, you should clearly explain the plaintext encoding in the BFV scheme to help readers better understand the entire scheme. 2. Since your scheme is a hybrid of HE and MPC, it would be better if you could provide a clearer explanation of the conversion between BFV and MPC.
Decision: Accept (poster)