Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: This work deals with the new matrix encoding method, called Volley Revolver, for efficient matrix multiplication on homomorphic encryption scheme. To efficiently use the data structure and the homomorphic operation in CKKS scheme for matrix multiplication, they adequately transpose and concatenate one of the input matrices and use RowShifter and SumColVec operation. The matrix multiplication and convolution operation are efficiently designed for CKKS scheme, and the simulation is conducted with HEAAN library and MNIST dataset.
strengths_and_weaknesses: Strengths
- The authors deal with matrix multiplication and convolution with the general dimensions of matrices.
- The ideas are well conveyed with specific matrix formulas to ease the understanding.

Weaknesses
- No simulation comparison with state-of-the-art matrix multiplication or convolution with CKKS scheme. As far as I know, the matrix multiplication and convolution in CKKS scheme is well researched in homomorphic encryption academic area, and thus this proposed technique can be compared with many prior works regarding matrix multiplication. They only show the classification accuracy and the latency with their proposed model without any comparison, so I cannot be assured that the proposed technique is superior to the state-of-the-art techniques.
- Reference is too weak. There are far more works regarding matrix multiplication and convolution in HE, but they only refer to only a small subset of these works.
- They refers to the work of Jiang et al. [9] and they claimed that the technique in this work "might" be difficult to be applied in practical application for CNN with over two convolutional layers. However, the authors do not suggest why it is difficult. The authors should have dealt with the limitation of the prior works thoroughly before proposing their technique. I cannot be assured that the prior techniques are really inadequate for CNN with over two convolutional layers.
- Overall, the authors failed to prove that their proposed technique is superior to the state-of-the-art techniques, and thus the authors should justify their contribution more strongly if they want to be accepted in the NeurIPS conference.
questions: - Why Jiang et al.'s work is difficult to be applied in CNN with over two convolutional layers?
- Please show the comparison with the state-of-the-art prior techniques.
limitations: They did not deal with the limitation of this work, and I think there is no potential negative societal impact.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This work provides the method, named Volley Revolver, of encoding encrypted matrix to perform matrix multiplication efficiently in the HE scheme. Volley Revolver provides an encoding method that packs multiple encrypted data in a single ciphertext, which makes matrix multiplication efficient.
strengths_and_weaknesses: Strengths:

The authors described the details of the proposed method with proper figures which are easy to understand.

---

Weaknesses:

The authors use the word *efficient* a lot, but its meaning should be described more definitely. From my understanding, the meaning of "efficient" refers that multiple image data can be encoded in a single ciphertext. If this is the authors' main contribution, please emphasize this point in Abstract, Introduction, Related Works, and Conclusions. 

Moreover, there is no quantitative discussion about the efficiency of the proposed method. Previous works are mentioned, but I cannot find the exact improvement compared to the previous works. Are there any other previous works about matrix encoding for matrix multiplication or convolution operation? If so, the authors should refer those works. If not, please mention it. And please show the performance which indicates the improvement from the previous works (e.g., runtime, the number of multiplications). Without these discussions, I think the proposed method is hard to be considered as an efficient method.
questions: Is the proposed method applicable for encrypted image data with multiple channels? Most of the colored image dataset such as CIFAR-10 are formed with three channels.
limitations: The limitation is mentioned in the introduction (lines 40--41).
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper proposes a new matrix multiplication method (called "volly revolver") suitable for homomorphic encryption. They present an efficient way of adding intermediate steps of the Convolution operation and simulate the operation on the packed ciphertext.
strengths_and_weaknesses: In applying homomorphic encryption to neural networks, it is necessary to perform matrix operations efficiently. In this process, homomorphic encryption requires an efficient method because the movement of the encrypted message is done through rotation, which has much computational cost. 
This paper does not reflect the latest research results. See, for example, C. Juvekar, et al., “GAZELLE: a low latency framework for secure neural network inference,” Proceedings of the 27th USENIX Conference on Security Symposium, August 2018, pp. 1651–1668, which covers how to perform matrix operations for homomorphic operations efficiently.

This paper is not properly compared with homomorphic matrix multiplication results in other papers. There is a limit to directly applying to real CNNs considering only matrix operation without considering the flow of computation in the entire network. The tests conducted only in MNEST appear to be too outdated compared to the recent results of CIFAR-10/100 or ImageNet.
questions: The paper deals only with matrix multiplication, but it is unclear what advantages there are from multiplication alone. Recent works have already reported a faster computation run-time than reported in the paper. Therefore, a simulation comparison with the latest results is necessary to clarify the advantage of the proposed method in the paper, but there is currently none.

CNN operation does not end with just one matrix operation, but it leads to another operation. In this process, the message size is reduced, and the message packed in the ciphertext needs to be reconstructed for efficient operations. Considering the whole network, convolution operation (and matrix multiplication) should be considered. Otherwise, it can be rather disadvantageous due to additional packing requirements and a corresponding new data rotation for the followed processes.

(215-216 lines) said that "Our method based on Volley Revolver can build convolutional neural networks as deep as it needs." However, they do not 

Although this paper targets gray images, other studies handle color images such as CIFAR-10/100 and ImageNet well. Obviously, the proposed method in this paper can also be used for color images, applying three channels independently. However, the amount of computation should be three times larger.

At 78-79 lines, the method in this paper is only applicable to datasets with a smaller number of pixels than the available slots of ciphertext, which is also a limitation of the proposed method. In the case of ImageNet, it is not possible to fit one image even in 2^15 slots, so another efficient method is needed.

On page 4, is the extended form of B included in the single ciphertext? Then, when the extended area is considered, the actually applicable sample size is likely to be further reduced.

It also does not consider how stride two or higher is applicable.
limitations: The social impact or limitations of the paper are not specifically described.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper presents methods for matrix multiplication and 2D convolution in lattice-based homomorphic encryption that allows parallel multiplication of a number of cleartext values. The authors have implemented in an open source framework and provide a benchmark for a simple MNIST network.

strengths_and_weaknesses: I'm missing a differentation to the prior work by Dathrati et al. [1]. They propose a matrix multiplication that only uses one ciphertext multiplication as opposed to $2p$ in this work for $p$ being the number of columns in the output, and they report on inference of three versions of a LeNet network with similar accuracy in 2.5 seconds where this work achieves an inference time of 287 seconds for a batch of 32. Even prior art cited by the paper (CryptoNets) achieves 250 seconds on a batch of 4096. The authors claim that memory usage is an issue with CryptoNets but they don't comment on the memory usage of their solution.

I'm also missing the specification SumForConv in terms of basic operations. The underlying encryption scheme only allows element-wise operations and rotations so any other operations has to reduced to these.

Why do the authors encrypt $F$ (line 11 in Algorithm 1 and line 22 in Algorithm 2)? F only contains public information, so a public-private multiplication would be more efficient.

[1] https://dl.acm.org/doi/10.1145/3314221.3314628

questions: How did you implement SumForConv in terms of rotations and element-wise operations?

limitations: yes
review_title: null

Meta-review: metareview: The reviewers were unanimous in their recommendation to reject the paper. The authors' responded to the reviews but recognized the limitation of their submission, particularly in terms of missing comparisons to related work.

I want to take this opportunity to address the author who wrote in their rebuttal:

 *"I will see the papers that referred to Gazelle if I can restart my Ph.D. study again. I hope so."*

I sincerely hope you have the chance to restart your Ph.D. program and continue your research. The conference review process can be daunting -- yet it is an important step in pushing our field forward. In the case of your paper, the reviewers appreciated your ideas and the quality of the presentation, describing it as clear and easy to understand. What was missing was a more comprehensive comparison with related work -- a common misstep, even for seasoned researchers. Please **do not** let this discourage you from engaging in research. In fact, I hope this experience demonstrates the value of peer review, serves as a learning experience, and helps your write a better paper. 

I look forward to crossing paths with your work again.

confidence: Certain
Decision: Reject