Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on minimizing the computation cost of the ReLU operation. Prior work uses Garbled Circuits (GC) to process ReLUs, which is computationally expensive. This paper proposes a novel method to reduce computation by decomposing ReLU operation into a sign computation and multiplication. The multiplication can be implemented by Secret Sharing and the cost of sign computation through GC can be reduced by approximation. This paper also provides adequate empirical evaluations to show the proposed methods can reduce runtime.

main_review: The idea of decomposing ReLU into multiplication and sign computation is nice. I also like the idea of approximating the sign computation to reduce the computation cost. The authors also provide the theoretical analysis of the fault rates of the stochastic approximation. The experiment evaluation is adequate. The authors evaluate Circa on various deep learning models and the results show the Circa requires much less runtime. This paper is also well-written and organized. 

Minor comments and questions:
1.	In the experiments, could the authors elaborate on how those models are trained? Does training those models involves Circa or it is used only in evaluating the test accuracy?
2.	Line 163: Typo in ‘This multiplication is cheap and the ReLU optimized ReLU’.


limitations_and_societal_impact: Yes, they discuss them in Section 6.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes several techniques to improve the trade-off between accuracy and storage/runtime for ReLU operations in private inference. The proposed techniques include refactoring ReLUs as a sign function plus a cheap multiplication, and replacing the sign function with a truncated stochastic sign that has runtime and storage beneﬁts (by sacrificing accuracy). Experiments on several datasets and network architectures show that the method has a better trade-off between accuracy and storage/runtime than prior state-of-the-art.
main_review: I do not work in this area and I am not familiar with related work, so I am not able to judge the originality and significance. 

Despite my unfamiliarity with the field, the paper is quite easy to follow. The first two sections provide concise while adequate preliminaries for me to understand the contexts. The approach and evaluation sections are well-organized and the takeaways are clear. Overall, the paper is well-written.

I just have several minor questions/suggestions.
* Line 253-260: It mentions that Circa achieves higher speedup than Delphi (2.6x v.s. 1.2x), but it is unclear what is the accuracy loss of Circa compared with Delphi (1%)?
Line 269: Again, it mentioned that Circa achieves higher speedup than SAFENet (2.6x v.s. 1.9x), but what about the accuracies?
* Line 172: itself.We -> itself. We
* Section 4.2: increasing the spaces between paragraph titles and contents to make it easier to read.
limitations_and_societal_impact: The authors discussed the limitations and potential negative societal impact of their work adequately.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes Circa to reduce the communicational overhead of ReLU-based privacy-preserving machine learning using three modifications. First, the ReLU circuit is refactorized into two parts including multiplication and sign function, so that a GC-based ReLU is converted into a GC-based Sign function with a Beaver’s Triple’s based multiplication. Secondly, GC-based modular operation is removed from GC-based circuits at the cost of precision. Thirdly, quantization or truncation is used to further speedup GC-based circuits at the cost of precision (potential decryption errors). The authors show that inference accuracy won't be decreased a lot by this decreased precision due to the network’s error-tolerance ability. 
main_review: This paper provides a clear ablation study for each of three techniques including sign, stochastic sign, and truncation. For example, readers are easy to find a take-home message that truncation on GC-based circuits plays a very important role in the last performance. 

However, there are other comments for the paper. 

1. The mechanism of the stochastic sign function is not clear. I knew that this paper tries to replace equation 1 with equation 2 since equation 2 does not have the operation of mod $p$. But it is confusing for the condition in equation 2: if $<x>_s$ <= $p$ - $<x>_c$. This condition may have a conflict with the condition in equation 1. From my understanding, $<x>_c$ +$<x>_s$ =$x$ whose range is from 0 to $2p$.    In equation 1, if $x$ mod $p$ > $p/2$, the output is $-r$, otherwise the output is $1- r$. Since $x$ is from 0 to $2p$, the output is $-r$ if $ x$ $\in$ (0, p/2) $\cup$ (p, 3p/2).  However, in equation 2, if $x$  $\in$ (0, p), the output is $-r$ which is different from equation 1. It is not clear how the proposed work handles this conflict without a large error. The proof of the error probability is not clear.

2. Unconvincing claims and assumptions. In line 198, this paper claims “in practice, $|x| << p$  for typical choice of prime”. However, if the input $x$ is 15 bits, the weights are also 15 bits, and $p$ is 32 bits, the intermediate results $x$ may be near to the $p$, especially when a convolutional layer, normalization layer, or the average pooling layer are used together. It is not clear how the paper controls the $|x|$ to be far less than p. Also, the error probability of stochastic ReLU shows that $p$ should be larger to maintain the small error probability, therefore introducing an overhead about HE parameters selection. For example, schemes without stochastic ReLU could use smaller p, but once using the proposed stochastic ReLU, one must use larger p which potentially introduces larger ciphertext and latency. This paper does not discuss this overhead.  

3. Limited function and usage. The proposed work only supports the ReLU function. It is not clear how to use the proposed methods on the other non-linear operations like max-pool, sigmoid, and softmax function which are also very expensive based on GC. It is much more important to support these non-linear operations other than ReLU functions. 

4. Prior work. It is good to compare the truncation method with related work NASS [1] which also uses quantization on the network. 

I would like to see the paper's presentation in NeurIPS and will consider modifying my score if the authors clarify my concerns well. 

[1] Bian, S., Jiang, W., Lu, Q., Shi, Y., & Sato, T. (2020). NASS: Optimizing Secure Inference via Neural Architecture Search. ECAI.

limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose to improve the speed of modern Homomorphic encryption (HE) approaches which leverage GC for RELUs by moving as much computations as possible outside of the GC. The optimizations introduced in Circa (i.e truncation and removing the modulo addition) come at the cost of stochastic faults. This study demonstrates that modern deep networks are highly resilient to RELU fault behavior and that Circa (the proposed) approach can offer up to 3x faster predictions than Delphi, a state-of-the-art framework. 
main_review: Originality: 
This study offers a novel and interesting direction for improving the speed of HE approaches by allowing stochastic faults. It observes that deep networks are resilient to stochastic RELU faults, and this property enables strong speed optimizations without significantly compromising accuracy. 

Quality / Significance: 
The core claim of this paper, Circa can offer a significant speed boost without compromising accuracy, is well supported by the empirical results. This paper tackles a central and common challenge for HE, i.e estimating relus, and makes a meaningful step towards real time applications of HE. 

Clarity: 
This paper is clearly written.

limitations_and_societal_impact: The authors adequately note their paper's limitations (applicable for inference only and only applicable to RELU networks) and the possible negative social impact.
review_title: null

Meta-review: Thank you for your submission. The reviewers agree that this paper provides new techniques to reduce the computational overhead of ReLU-based private inference. During the discussion, the authors have addressed the questions raised by the reviewers. The authors should incorporate these clarifications during rebuttal into the next revision of the paper.
Decision: Accept (Poster)