PrivCirNet: Efficient Private Inference via Block Circulant Transformation

We appreciate Reviewer mVR6's feedback and we will address each of the questions as follows.

[To weakness, lack of communication cost comparison]

First, 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.

Second, PrivCirNet focuses on optimizing HE computation complexity and does not specifically optimize the communication cost, as demonstrated clearly in the experimental results.

The 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.

[To Q1, why use BFV instead of CKKS?]

It 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.

Besides, 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].

[To Q2, why is the table layout inconsistent, i.e., table 1 and table 2?]

We 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.

[To Q3, why the accuracy of MobileNetV2 is higher after 50% compression?]

Neural 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].

[To Q4, why CirEncode mod $x^n-1$?]

CirEncode 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].

Here'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])$.

The 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.

We will add this discussion to the appendix in our final version.

[Concern Regarding Reviewer mVR6 Conduct]

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.

[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.

[a1] Li, Baiyu, and Daniele Micciancio. "On the security of homomorphic encryption on approximate numbers." EUROCRYPT, 2021.

[a2] Gentry, Craig. A fully homomorphic encryption scheme. Stanford university, 2009.

[a3] Esser, et al. "Learned step size quantization." ICLR 2020.

[a4] Li, Yanjing, et al. "Q-vit: Accurate and fully quantized low-bit vision transformer." NIPS 2022.

[a5] Yamamoto, Kohei. "Learnable companding quantization for accurate low-bit neural networks." CVPR 2021.

[a6] Li, Yuhang, et al. "Additive powers-of-two quantization: An efficient non-uniform discretization for neural networks." ICML 2020.

[a7] Han, Song, et al. "Learning both weights and connections for efficient neural network." NIPS 2015.

[a8] Zhang, Yuxin, et al. "Bi-directional masks for efficient n: M sparse training." ICML 2023.

[a9] Zhou, Aojun, et al. "Learning n: m fine-grained structured sparse neural networks from scratch." ICLR 2021.

[a10] Zhang, Yuxin, et al. "Learning best combination for efficient n: M sparsity." NIPS 2022.

Dear Reviewer mVR6,

We are writing to follow up on the rebuttal submission for our paper. We have carefully addressed all the concerns you raised in your initial review, providing additional data and clarifications to support our responses.

Given the significant impact of your review on the final decision, we believe our rebuttal must be fully considered. We kindly request your prompt feedback on our responses, as your input is essential to ensuring a fair and balanced evaluation of our work.

Please let us know if there are any additional points you would like us to address or if further clarification is required.

Thank you for your attention to this matter.

We appreciate your advice on improving the clarity of our paper. In the final version, we will explain in the appendix why our encoding scheme uses $\mod x^n-1$. As for the conversion protocol, we initially omitted the details since HE+MPC is a mainstream technique in hybrid HE-based frameworks, and nearly all related works utilize the same conversion protocol. However, we will now add an explanation of the hybrid HE+MPC scheme to the appendix. Thank you again for your attention and valuable suggestions.

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.

[To Weakness1 and Question2, misleading notation of GEMM]

We 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!

[To Weakness2 and Question5, the details of nonlinear layer evaluation]

For the details of the nonlinear layer evaluation, see the first part of the global response.

As for our C++ implementation of private inference, we are organizing the code and will release it upon acceptance.

[To Question1, the bottleneck of Bolt]

Thanks 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.

Additionally, 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].

[To Question3, how to apply Bolt to CNNs?]

Bolt'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.

However, 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.

We will add this illustration to our final version.

[To Question4, simply extending Bolt to circulant matrix multiplication]

In 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.

On 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.

There 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.

Consequently, 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.

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!

[r10,r22,r27] represent the 10th, 22th, and 27th references cited in our original submission.

[a1] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, "Extending Oblivious Transfers Efficiently," in CRYPTO, 2003, pp. 145–161.

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

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:

[Our implementation code of private inference]

Our 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.

[The implementation details for multi-party computation (MPC) and the performance improvement attributed to HE]

See the first part of the global response.

[To Question, Figure 9 marks the points with the highest compression]

In 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.

When 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."

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!

[r10, r52] represent the 10th and 52th references cited in our original submission.

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.

[To W1, concerns on novelty]

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.

While [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.

In 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:

• Adopts a hybrid HE+MPC framework, eliminating the computationally expensive discrete Fourier transform (DFT) on the ciphertext.
• Maximizes the potential of block circulant matrices by customizing the HE encoding algorithm, reducing computation latency proportional to the block size.

A comprehensive comparison between PrivCirNet and [r44,r45,r25] is summarized as follows:

[To W1, comparison under a large hidden dimension]

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.

[To W2, comparison with DeepReshape (TMLR'24, April 2024) ]

Thank 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.

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.

From 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!

[To W3, missing year in citations 27 and 38]

Thank you for pointing out the typo! We will correct this in our final version.

[To Q1, ViT training]

We 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.

[To Q2, why choose MobileNetV2?]

MobileNetV2 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.

[To Q3, Crypto-primitive used for nonlinear layers]

See the first part of the global response.

[To Q4, the overhead of finding optimal block size]

For 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.

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!

[r7,r25,r30,r32,r44,r45,r58] represent the 7th, 25th, 30th, 32th, 44th, 45th, 58th references cited in our original submission.

[a1] Jha et al., DeepReShape: Redesigning Neural Networks for Efficient Private Inference, TMLR 2024.

[a2] Radosavovic et al., Designing Network Design Spaces, CVPR 2020.

[a3] Woo et al., ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders, CVPR 2023.

[a4] Tan et al., Efficientnet: Rethinking model scaling for convolutional neural networks, ICML 2019.

Thank you very much for your support! We greatly appreciate the valuable advice and will incorporate all the relevant discussions and data into our final version. The varying accuracy degradation 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 depth-wise/group-wise convolution, providing significant compression potential using PrivCirNet. In contrast, standard convolution parameters account for only 64% and 78% of RegNet and MobileNetV2, respectively. As a result, RegNet and MobileNetV2 exhibit larger accuracy degradation at higher compression rates. Additionally, these networks demonstrate varying latency characteristics in nonlinear layers. Jointly optimizing linear and nonlinear layers is an interesting question, and we plan to explore this in our future work. We will include this discussion in our final version.

Thank you once again for your support and insightful feedback!