Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper follows the line of work that leverages holomorphic encryption (HE) operations on encrypted data for privacy-preserving inference on MLPs and CNNs. Authors propose changes to the representations of intermediate layers during CNN inference, which requires much fewer number of operations than previous works.
main_review: **Strengths**

The experimental results demonstrate that the proposed method is much more efficient than previous works.


**Weaknesses**

Disclaimer: The reviewer is not familiar with the literature of HE schemes for privacy-preserving inference, and has not checked the relevant literature closely.

Overall, the reviewer feels that the writing of this paper is not clear, and many details are missing or not easy to follow. For example, the main methods are supposed to be in Section 3.1, while this section only contains a primitive introduction to the convolution operation and its flattened version (which I would expect to reside in Section 2), and a remark which tells the number of operations for the proposed method. The two parts are a bit disconnected. Based on my understanding, the proposed method is to apply the HE operation (as in Section 2.4) on the flattened convolution operation, and this part should go before the remark part. But the corresponding description is completely missing from my point of view.

In section 3.2, the authors compared with two types of representations in LoLa: the sparse representation and the stacked representation. I roughly checked the LoLa paper (Brutzkus et al., 2019). Actually they have five types of representations, even including a "Convolution representation" which claims to "make convolution operations efficient". I didn't check the details of their "Convolution representation", but I would like to ask the authors what is the difference between their method and yours, and why you didn't involve a comparison in your paper? I would appreciate it if the authors can provide a clear explanation to this.

In experiments, the authors mentioned that "linear layers without activations between them are composed together". But activations are often quite important in all sorts of architectures. Is there any reason that impeded authors from using activations? Also, the last column of Table 1(a) (i.e., the "Input" column) look wrong to me. I would suggest that the authors carefully check the numbers.

Minors:

* Authors said "We choose to use a variant of this method ... ". So is the variant proposed by the authors? What is the relationship of this variant and Halevi & Shoup (2019) and GAZELLE (Juvekar et al., 2018)?
* In Section 3.1, $\mathbf{v}$ should be $\in \mathbb{R}^{d_{\mathrm out}^2\cdot c_{\mathrm{out}}}$
* In Section 3.1, the "Remark" should be replaced by "Proposition".
summary_of_the_review: Several important details and comparisons are missing in the paper, which largely weakens the contribution of the paper. Also, there are flaws in the statement, and the writing is not professional enough.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of privacy preserving inference on deep learning models using homomorphic encryption. HE is a special type of encryption that allows one to perform certain types of computations while the data is encrypted. However, the catch is HE based inferences can be significantly slower than the non-private counterparts. The paper claims to improve upon the existing state of the art HE based inference approaches significantly -- two orders of magnitude.
main_review: Pros:

1. The paper attempts to study a problem that is at the heart of privacy preserving machine learning, i.e., speeding up HE based inference on deep neural networks.
2. The paper is well written.

Cons:

1. The paper is rather straightforward rehashing of existing (which are themselves rather simplistic, in my opinion). For instance, they take a recent improvement by Halevi and Shoup for Matrix products and apply it to the previous work LoLa. 

2. The experimental section is quite weak and misleading. In the abstract it is claimed that the current work improves upon the existing work by two orders of magnitude. While this is true when compared by CryptoNets -- the more recent works already seem significantly better. 


summary_of_the_review: I think this is an important problem and the paper is reasonably well written. Unfortunately, it is a rather weak attempt. Essentially, it is a rehashing of existing ideas -- which are already uninspiring from an ML point of view. Further, as described above, the experimental section is rather misleading. For instance, there is no clear comparison of inference time with LoLa (does it improve the inference time at all?).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: To accelerate the privacy-preserving inference through convolution neural networks (CNNs) with homomorphic encryption (HE), the authors aim to reduce the number of homomorphic operations (HOPs) required for the algorithm to save the data needs to be transferred while preserving prediction accuracy.

Using a LOLA method as a baseline, the authors used Halevi-Shoup (HS) which requires much fewer rotations operations in general. In the experimental results, the HS method requires half of the operations in comparison to the LOLA method. By further simplifying the structure of the network, only about 20% of HOPs are required. These simplifications bring about 1% and 27% accuracy loss.

main_review: Overall, this paper addresses an important problem in privacy-preserving machine learning and the results show that the method is effective. However, the originality and the evaluation of the paper are not strong enough. The originality is incremental because the authors applied an existed approach, HS, to an existed structure, CRYPTONET. The evaluation is not sufficient because the experimental results are not well analyzed and interpreted. For example, only a limited part in table 2 is discussed in the text. More analysis about table 2 would improve the results section of the paper. In addition, the introduction to the HS method is a little short and the entire pipeline of the HS approach is not easy to follow. By focusing on the introduction to the HS method instead of the introduction of the baseline LOLA method, the authors can explain the HS method better.
summary_of_the_review: The paper is marginal acceptable because the paper is addressing an important question and the method is effective. However, the improvement of the method is not impressing or suppressing. The entire is not well finished. Thus, this paper is regarded as a border line paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper applies the state-of-the-art technique for matrix-vector multiplication in homomorphic encryption to encrypted inference for convolutional neural networks.

main_review: The technique is explained well and there is an-depth analysis of the resulting complexity with a comparison to prior work. The 2-3x improvement is considerable. Furthermore, the editorial quality is high.

Minor:
- p7: 56 rotation(s)

summary_of_the_review: The paper provides a well-argued application of the state of the art in homomorphic encryption.
review_title: null

Meta-review: This paper improves on the efficiency of prior work that uses homomorphic
encryption to perform privacy-preserving inference. There are two main
concerns raised by the reviewers. First, multiple reviewers (and I) found
this paper difficult to read. Multiple pieces of the problem are not
clearly presented especially with respect to the technical contributions.
This was fixed in part in the rebuttal but more could still be done here.
But more importantly, three reviewers raise concerns about the evaluation
methodology, especially with respect to comparisons to prior work. On top
of this, there are valid criticisms raised by the reviewers about if the
contribution here is that significant when compared to prior work. (This
is something that both more clear writing and more careful experiments
could hep address.) Taken together I do not believe this paper is yet ready
for publication.
Decision: Reject