Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a privacy-preserving training scheme that consists of two parts: encryption strategies based on permutation-equivariance and (partially) permutation-equivariant learnable network.
The contributions of the paper are the two encryption strategies, names Random Shuffling and Mixing, together with the modifications of the existing transformer-based image classification and object detection to learn from encrypted images.
strength_and_weaknesses: Strength:
1. The overall paper is well-written and defined. It is easy enough to follow and reproduce.
2. Extensive experimental results to demonstrate the strength of the proposed method.

Weaknesses:
1. Limitation of the paper is not discussed. 
2. The change to the existing method so that it can learn from encrypted images is not significant. For example, the change from the existing YOLOS to the proposed PEYOLOS is the input x^p to x_s as in Eq. 12.


clarity,_quality,_novelty_and_reproducibility: The overall writing of the paper is good enough. 
The overall idea is somewhat novel, however, the network structure is a bit weak in terms of novelty. 
Other comments:
- In table 1, the authors should compare with DeiT-B on images encrypted by RS. 
- Are the results of COCO object detection compared with PEYOLOS trained on images encrypted by MI? This should be indicated in table 2 as in table 1 for clarity.
summary_of_the_review: In summary, the paper still has some valuable contributions in terms of encryption strategies. Thus, my recommendation rating for the paper is weak accept.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes RS and MI, two permutation-based image encryption algorithms designed to render images unrecognizable to humans, yet still enable image classification and object detection respectively, by downstream vision transformers. The first step of both encryption algorithms is to partition images in to N equally sized patches. Next, RS, short for “random shuffling”, removes the positional embedding of the patches and shuffles their order, leaving a “bag of words” style input. MI, short for “mixing-up”, partitions each of the N patches into M sub-patches and sets each sub-patch equal to the mean of the M sub-patches. The encrypted images are then fed to "permutation-equivariant" variations of ViT and YOLOS, referred to as PEViT and PEYOLOS for image classification and object detection respectively. Compared to ViT, PEViT replaces the conventional positional embedding with a novel reference-based positional embedding. Compared to YOLOS, PEYOLOS replaces the linear patch embedding with a two-layer non-linear patch embedding. Experimental evaluations on ImageNet and COCO demonstrate that the proposed methods achieve near SOA performance despite operating on encrypted inputs. 
strength_and_weaknesses: # Strengths

* The main idea of the paper of combining permutation-based image encryption algorithms with transformers is interesting and novel.

* Experimental evaluations on ImageNet and COCO demonstrate that the proposed methods achieve near SOA performance despite operating on encrypted inputs.  


# Weaknesses

* The paper fails to provide a concrete definition of privacy. For example, the paper claims that the “proposed paradigm can destroy human-recognizable contents”, but never specifies what is meant by this.

* Given that the stated aim of the proposed encryption algorithms is to “destroy human-recognizable contents”, humans should play some role in the evaluations. Where are the human studies? 

* The paper is missing ablation studies for the novel transformer architectures. Where are the experiments demonstrating the need for the proposed RPE in PEViT and the nonlinear embedding in PEYOLOS?
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The paper is well-organized and clearly written.

**Quality:** The paper is likely to have modest impact within a subfield of AI. 

**Novelty:** The paper contributes some new ideas.

**Reproducibility:** Key resources (e.g., proofs, code, data) are available and key details (e.g., proof sketches, experimental setup) are comprehensively described such that competent researchers will be able to easily reproduce the main results.
summary_of_the_review: The main idea, albeit simple, is interesting and novel and seems to produce good results. However, the evaluation is lacking in that privacy is not defined and is missing key ablation studies.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper proposes to "encrypt" images by using two techniques. First one (RS) is to cut each image into patches and then reshuffle the order of tiles. Second one (MI) is to mix up some of the patches.
Authors show that vision transformer without positional embeddings (PEViT) can successfully learn to recognize images encoded by RS method. And they also show a modification of object detector YOLO which can perform object detection on images encoded by MI method.
strength_and_weaknesses: Strength:
1) Paper is reasonably well-written and easy to understand.
2) It is an interesting observation that vision transformer does not need positional embedding for successful image recognition. Idea of RLE is also interesting.

Weaknesses:
1) Authors claim "encryption" and "privacy protection", however they don't define what they mean by privacy and don't define their threat model. One of the adopted notions of privacy for ML models is differential privacy ( https://arxiv.org/abs/1607.00133 ). It's fine to define and use different notion of privacy, but it has to be well defined. It seems like, by privacy authors imply inability for a human observer to recognize what's on the image. However this is highly subjective, moreover proposed methods arguable don't even fulfill this goal (see below).
2) Lacking evaluation of reconstruction attack. I didn't find any numerical evaluation. Evaluation in experimental section is summarized by a quote: "As shown in Figure 1, the visual contents of encrypted images are nearly-completely protected from recognizing by human eyes". For the reference, figure 1 shows a few images before and after encoding. So it appear to me that authors claim that solving jigwas puzzle is a hard problem, showing few images before and after encoding and claim that this is the reason why their method protects privacy.
3) Authors over estimate complexity of solving a jigsaw puzzle. The experiments are done in a setting when RS method split image into 14x14 patches. Authors refer to a paper about automated jigsaw puzzle solver from 2015 and claim that it's a sufficiently hard problem.
Arguable, individual 14x14 jigsaw puzzle (196 pieces) could be easily solved by human in a few hours at most. Which means that any individual image encoded with RS method does not really "destroy human recognizable content".
For comparison, no human can manually decrypt a file, which is encrypted with AES ( https://en.wikipedia.org/wiki/Advanced_Encryption_Standard )

clarity,_quality,_novelty_and_reproducibility: Clarity:
- paper is well-written and easy to understand

Reproducibility:
- authors provide a source code in supplemental material, which should make it easy to reproduce the result. As a note, I haven't actually inspected or run the code.

Novelty:
- I think the fact that vision transformer does not really need positional embedding has some amount of novelty. However I'm not sure to what degree this topic is already explored in other papers, thus amount of novelty might be quite limited and do not justify for a conference paper. In particular [Shaw et al 2018] work which is referenced in the paper already exploring relative positional embedding, instead of absolute embedding.

Quality:
- As mentioned in the weaknesses section, privacy and encryption claims of the paper are essentially invalid.


summary_of_the_review: Strong reject.

Paper claim to propose an encryption scheme which protects privacy. However authors neither follow any common privacy definition (for example, differential privacy), nor they define their own notion of privacy. In addition, evaluation of encryption properties of the proposed methods is lacking.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper tackles privacy-preserving image classification and object detection (in the context of vision transformers) based on random shuffling and mixing-up on the patch scale.

strength_and_weaknesses: Strengths:

1. Topic is important.
2. Result is promising.

Weaknesses:

1. The primary issue is the lack of quantitative metrics to measure the degree of privacy preservation. Visual inspection of Figure 5 indicates that the main content has already been revealed. Although the authors emphasize that solving the jigsaw puzzle problem is NP-hard, in practice, we only need to find a not-so-good local optimal (e.g., in the mean squared error sense) that is sufficient to reveals the main semantics w.r.t. the task at hand.

2. If the reviewer understands correctly, after the MI encryption process, even the encrypters themselves cannot perfectly recover the original image (see Eq. (2)), which is unfavorable. We expect encryption and the corresponding decryption together to form a bijection.

3. For image classification, we tend to rely on permutation-equivariant and permutation-invariant operations as suggested by the authors. Then, what is the motivation to incorporate a reference-based positional embedding in Eq. (10)?

4. The math notation in Eq. (12) is less clear. Specifically, what is $\mathbf{x}_i^\mathrm{DET}$?
clarity,_quality,_novelty_and_reproducibility: Clarity: the paper is easy to follow; the adaptation of vision transformers is straightforward.

Quality and Novelty: Somewhat limited because the degree of privacy preservation cannot be measured and compared quantitatively. Also, the use MI as a non-invertible operation is arguable.

Reproducibility: the paper's results are easily reproducible provided the seeds of random shuffling are given.
summary_of_the_review: With a much more rigorous privacy-preserving analysis and the justification of the MI encryption, the paper has a chance to get in.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper claims to present a privacy-preserving image-recognition model that “encrypts” images via a jigsaw approach before training. Experiments show that a transformer trained on these “encrypted” images can still accurately recognize the content of the images.

The main shortcoming of this paper is that it does formalize the notion of privacy or encryption in any way. The paper does not specify a threat model, does not describe what notion of cryptographic security the “encryption” is supposed to provide, and does not specify what notion of statistical privacy the presented scheme guarantees. As a result, the claim that the proposed scheme is privacy-preserving is moot. 

Indeed, it seems quite unlikely that the scheme satisfies any traditional notions of cryptographic security or statistical privacy. This is underscored by the development of a successful attack against the scheme by one of the commenters. The authors’ defense that this attack may require an attacker to have non-polynomial amounts of compute suggests an implicit threat model that the authors should have made explicit in the paper. Moreover, the particular instantiation of the scheme tested in the paper is apparently insufficient to make it the attacker very difficult. The scheme would likely become harder to break if the authors used more, smaller patches but it is quite likely that then the recognition accuracy would also suffer, which would undermine the central claim of the paper.
justification_for_why_not_higher_score: This paper makes claims on security and privacy that need to be formalized for them to be confirmed. The presented scheme is unlikely to pass generally accepted definitions of security and privacy.
justification_for_why_not_lower_score: N/A.
Decision: Reject