Shuffled Transformers for Blind Training
Authors: Hengyuan Xu
Liyao Xiang
Hangyu Ye
Dixi Yao
Pengzhi Chu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Data privacy
split learning
Transformer
privacy-preserving

Abstract: Conventional split learning faces the challenge of preserving training data and model privacy as a part of the training is beyond the data owner's control. We tackle this problem by introducing blind training, i.e., training without being aware of the data or the model, realized by shuffled Transformers. This is attributed to our intriguing findings that the inputs and the model weights of the Transformer encoder blocks, the backbone of Transformer, can be shuffled without degrading the model performance. We not only have proven the shuffling invariance property in theory, but also designs a privacy-preserving split learning framework following the property, with little modification to the original Transformer architecture. We carry out verification of the properties through experiments, and also show our proposed framework successfully defends privacy attacks to split learning with superiority.

Under review as a conference paper at ICLR 2023
SHUFFLED TRANSFORMERS FOR BLIND TRAINING
Anonymous authors
Paper under double-blind review
ABSTRACT
Conventional split learning faces the challenge of preserving training data and model privacy as part of the training is beyond the data owner's control. We tackle this problem by introducing blind training, i.e., training without being aware of the data or the model, realized by shuffled Transformers. This is at- tributed to our intriguing findings that the inputs and the model weights of the Transformer encoder blocks, the backbone of Transformer, can be shuffled with- out degrading the model performance. We not only have proven the shuffling invariance property theory, but also design a privacy-preserving split learning framework following the property, with little modification to the original Trans- former architecture. We carry out verification of the properties through experi- ments, and also show proposed framework successfully defends privacy at- tacks to split learning with superiority.
INTRODUCTION
Recent years have witnessed remarkable growth in deep learning applications, as deep neural net- works (DNNs) have grown deeper and larger. It poses a dilemma for the thin edge device: on one hand, it lacks the computational power individually train the models; on the other, data privacy would be violated if it sends all data to an untrusted party, egg. the cloud, to process, A paradigm called split learning (Gupta & Raskar 2018) emerges be potential solution: without sharing its raw data, the edge transmits intermediate features to the cloud while offloading partial computation.
Typically, the private inputs are transformed into intermediate features by feeding through the first few layers of the DNN. The vanilla split learning still faces privacy leakages as adversary could infer the input from the feature (Erdogan et al. 2021 Isola al.) 2017). Hence many works have proposed to remove the sensitive information from the features, such as encryption (Lee et al., al, 2022), adversarial learning (Xiao et al. 2020), differential privacy (Dong et al. 2019). y. etc. However, these works mostly sacrifice accuracy or efficiency for privacy guarantee. More importantly, the privacy threat of the model weights trained on the cloud is left to be an open problem the trained weights reveal the privacy of the training data (Fredrikson et al. 2015) Carlini et al. 2020), and should be proprietary to the data owner, i.e., the edge.
2019 Zhang et al.
We propose novel blind training framework the Transformer (Steiner et al. 2021 a state-of- the-art DNN achieving impressive accuracy performance on a wide range of tasks. Blind training means that the cloud conducts its part of computation 'in blind' being unaware of the data or the model it trains, yet executing valid computation to assist the edge. The framework resembles the homomorphic encryption where the edge encrypts training data with its key, and feeds to the encrypted DNN hosted in the cloud. The cloud trains the DNN in ciphertext, without knowing the input or the model. Different from the cryptographic tool, our framework built all in plaintext, and thus avoiding the hassle of encryption.
The key is to exploit the shuffle invariance property of Transformers. We discovered that Trans- formers have an intriguing property that each input, being an image or sentence, can be randomly permuted within itself, to feed through the network, yet being equivalently trained to that without permutation. Despite that the previous work (Naseer et al.) 202I) has recognized Transformer is ignorant of position information without position embeddings, we non non-trivially found that even with position embeddings, Transformer is shuffling invariian,, proved by theories. By regarding the per- mutation order as a 'key,' the edge feeds shuffled training data to the cloud which performs natural training. Another interesting property found is that, by training on the shuffled data, we inher-

---

Under review as a conference paper at ICLR 2023
ently obtain Transformer encoder block with shuffled weights, which only yields valid results inputs permuted by the "key.' Hence the Transformer is "encrypted" to train on the shuffled data. More importantly, the shuffled model can be "decrypted" to obtain an equivalent plain network to which normal data can be fed.
Highlights of contributions Transformers (and other models with Transformer encoder blocks as backbone), and built privacy- preserving split learning framework on it. The framework provides shuffling-based privacy guar- antees for training data, testing data, as well as the model weights. A variety of experiments are implemented verify the properties, and demonstrate the superior performance of our scheme in terms of accuracy, privacy and efficiency.
discovered the intriguing shuffle invariance property of
BACKGROUND AND RELATED WORKS
Transformer- based models are the state-of-the-art deep neural net- works and have attracted great attention in both areas of computer vision and natural language processing. Models including trans-
Transformer Encoder Blocks
former encoder blocks as their backbone, such as Bert (Devlin et al.]
Patchee
00
2018), ViT (Dosovitskiy et al. 2020), TiT- (Yuan et al. (021),
MLP Head
(x,
VITGAN (Hroos et al. 2021). BEiT (Wang et al.) 2022) and CoCa
MLP
Yu et al. 2022). have been achieving exceeding performance in a great many tasks.
Label
Scaled Product
Transformer encoder blocks, as shown in Fig. mainly contain two eritical components: Multi-head Scaled-dot-prodies self-attention and a feed-forward network (MLP). Inputs are fed in the form of patches, which usually embedding vectors for words in Bert, or for fractions of images in ViT. The relative position of patches learned by position embeddings (Vaswani al. 2017), which are injected into the model. Recent studies have found that by re- moving the position embeddings, ViT merely loses 4% accuracy on ImageNet (Russakovsky et al., 2013). And the work further reports the shuffling invariance property of ViT through experiments.
Data
Patch Embedding
Lineer
Cinear
cimiar
Position Embedding
Patches
00.00
(p.
Figure 1: Transformer
Split learning. As deep neural networks are growing deeper and
Encoder Block
wider, is hardly fit for the edge which lacks the computational power but owns abundant data. Hence split learning (Gupta & Raskar 2018) proposes to let the cloud server shoulder partial com- putation without accessing the data. To achieve this, model is split into two parts, deployed on the edge and the cloud, respectively. The edge processes the first few layers and sends the interme- diate features to the cloud which holds the main body of the model. If the cloud does not own the corresponding labels, it returns the prediction to the edge for computing the loss. In the backward propagation, error gradients are passed between the edge and the cloud instead of the features.
Studies have revealed that the untrusted cloud can reconstruct the private data with the intermediate features (Erdogan et 2021 Isola et al. 2017). Additionally, split learning allows the cloud to directly touch the model weights, which is also threat to the privacy of training data at the edge.
Privacy- presevypn split learning. Many efforts have been made preserve data privacy in split learning but most have been devoted to inference data, rather than training data or model protection. Almost no lightweight protection scheme is feasible for trained model weights, which should be proprietary to the edge, and not be taken advantage of by the cloud. Traditional methods include cryptographic ones such as secure mulli-party computation and homomorphic encryption. But these methods typically involve significant overhead in encryption, decryption, computation, and commu- nication. Lee et al. 22022) implemented a polynomial approximation over nonlinear functions and encrypted the training process with FHE, but it demands 10 to 1000 times more computation power compared to plain split learning. The approximation computation also results in accuracy losses. Xiao et al. (2020) adversarially trained the edge sub-module to produce features not containing any private information, but sufficient to complete the learning task. However, the method only works when the learning converges and thus suffers potential leakage at the early stage of training. [Dogg
2

---

Under review as a conference paper at ICLR 2023
et al. (2019) inserted Gaussian noise to the features following the convention of differential privacy. Ryoo et al. (2018) adjusted the image resolution to seek a sweetspot in the tradeoff between utility and privacy. These works have sacrifice considerable model accuracy performance to meet the privacy requirement.
Matrix Multiplication Computation (MMC) is fundamental mathematical operation, and works (Lei et al.) 2014) [iuu et al. 2021) propose random permutation as an encryption scheme to the out- sourced MMC tasks. To enhance the security, the recent work (Liu et al. (021) introduces additive perturbation besides the multiplicative one; but their works are mostly theoretical and should be
viewed as complementary to ours. We investigate the privacy guarantee in a more challenging scene deep neural networks, and propose practical protection scheme.
PROBLEM FORMULATION
We formally formulate our problem in the setting of split learning. The edge holds private training data set Drrain = {X, Y}, where X are the private data and Y are the private labels. The edge aims training model with the assistance of the cloud, yet without revealing any private input or the model weights to the cloud. The cloud possesses powerful computing power but is curious about the private data of the edge and the model it trains. The edge selects a model and splits it into two parts, F and F', to deploy on the edge and the cloud, respectively. Referring to the loss function as method as M, the ultimate goal of the edge is to train F and
Ltask and the local F² jointly to
minimize F.F"
Liask (F((()))
without revealing X F' to the cloud or any other third party. Although the cloud does not directly access the input, it is possible to invert X from F(X) by the following attacks.
We assume the cloud server the learning task accordingly, but is curious about the private data. Depending on whether the edge model is accessible to the attacker, we divide the attacks into two categories:
buturiuu meaning that it obeys the protocol and performs
Black-box attacks. The attacker is able to obtain the auxiliary data set Xaur and the corresponding features under protection mechanism M as M (FF(Xuu training rounds. It trains inversion model G over (X Xauny F(Xaur)) to invert the raw input from features. The attack goal can be
which may be collected over multiple
minimize G
Lattack Lattacs(G(M[ (G(M(F) (M
Xauz).
The superscript e denotes the number of trained iterations for the features. The loss Tattack can be the mean square error (MSE) between the reconstructed input X Xanr and Xawa- At convergence, G works as a decoder to invert features into inputs. It should be noted that the attack we model here is different from the feature-space hijacking attack in split learning (Pasquini & Bernaschi (021). as the latter destroys model accuracy, inconsistent with the buteci-out- assumption we made.
White-box attacks. The attacker has full access to the edge model F and the protection mechanism M, and performs gradient descent over M (F()) and its guess M (FF(X) by
minimize Lattack (M M(F())))
(3)
4 INTRIGUING PROPERTIES OF TRANSFORMER ENCODER BLOCK
To tackle the privacy issue in split learning, it is important to perform transformations over F(X) for training or inference, meanwhile preventing the adversary from inverting X from F(X). ). In our work, we adopt permutation as the transformation method, and model it by row and column shuffle, which can be expressed by matrix multiplications, i.e., given a matrix Z E R2xd the row shuffle is represented by PR where PR (0, 1 10 is permutation matrix. Similarly, the column shuffle defined as PP where permutation matrix Pa E (0, 1]dxd, Further explanations can found in A Appendix A In this section, we will introduce key properties discovered on Transformer encoder
3

---

Under review as a conference paper at ICLR 2023
Train
Test
Train
Test
O
Os.
Pa.O
O.PO
PaOLPE
PsO
Wo
W
Wo O
P
Incmaec Resdd
X
Rai
Franyted
Pa.
Z.PC
PACELPE
Pm 2
Z.P²
PAZiFO
(a) Training the cloud model on Z or PRx Zi yields the same W.
(b) Training the cloud model P P.1))
{&x (P' returns W(P) = Pc W PC
Decryption
Re-encryption
PoWP
W
W
Po.
Pe PoWPE Pe
Pc W PC
(c) Decryption and re-encryption of trained model be implemented by matrix multiplication.
Figure 2: Properties of shuffled Transformers. White blocks denote initialized models, gray blocks mean the naturally trained models, and red ones indicates "encrypted' model Enc(p). represents the original outputs. R; suggests the order of row shuffle can vary for each input.
blocks, which serve the building blocks our privacy-preserving split learning framework showed later.
Fig. summarizes the properties found and each detailed proof is provided in Appendix Denoting the Transformer encoder as Enc, the input matrix of Enc as Z, and the row permutation matrix as PR. we have the following theorem:
Theorem 1. Transformer encoder blocks rox-permultation-qqiivaaaa
Enc Pn PREnc(ZZ)
As shown in Fig. 2a the row permutation PR can 'pass through' the encoder so that a reverse oper- ation can be performed at the output of the encoder to return the original output: P 'Ene( Zn Enc( Z). More interestingly, the gradients Transformer encoder blocks in the backward propaga- tion are invariant row shuffle:
Theorem 2. The gradients of Transformer encoder blocks w.r. the loss I are row-permutation- invariant:
Øl
OW
ow
In Eq. W generally refers to the weights learned naturally in the multi-head attention or the MLP of the Transformer encoder block. W(R) the corresponding weights learned on Pn Z. Hence indicating by Fig. 2a the learned weights the same with without shuffle Z. Rigorously speaking. it is not the same W learned since the weights are initialized differently: be considered the row shuffle is transparent to the Transformer encoder blocks, either in training or inference. Similarly, denoting Pe as the column permutation matrix, we have
Theorem 3. If the Transformer encoder permuted as Enc(p) PeEnceo' Enc(p) is row- chuun--huufle-quivvlle
Enc(ry (PRZP() PREnc P
(PRZP PPc Pe Enc(Z). More intriguingly, we Theorem 4. The gradients of Transformer encoder blocks Encipy w.r. the loss I is column- permutation-equivvlent
And the outputs can be reversed by P Enc P have
Øl
Øl p-1
Pc JW
OW(P)
4

---

Under review as a conference paper at ICLR 2023
By induction, prove that if one shuffles the normally trained Enc. it would obtain equivalent (PC trained on the shuffled data. Specifically, letting the weights of the normally trained Trans- former encoder block be W. the weights of the model trained on P are PcWPE as shown in Fig. 2b If the "encrypted" model Enc, is deployed in the cloud, the cloud would have no clue about the model weights the inputs, but train the model 'blindly" for the edge. Compared to cryptographic tools like fully homomorphic encryption (Lee al., 2022). our "encryption' method realizes similar idea but with far less computation overhead.
Similar to the 'encryption' process, 'decryption' is feasible by reverse shuffling, as in Fig. 2c Re- encryption is also viable by matrix multiplication, suggesting that Enc can be "encrypted" not only by training on shuffled data, but also by permuting the trained weights.
To up, the row shuffle is transparent to the Transformer encoder blocks. The now-and-columm- shuffle serves similar way to homomorphic eneryption, in that the weights of Enc, P) are not known, while EnC only capable of processing shuffled Z. Either by training shuffled data or by matrix multiplication, can the weights of (nc(p) be obtained. The entire process does not incur additional computational burden, sacrifice accuracy performance.
Forward
Edge
Cloud
Backward
Our Method
lass
Gradients Features
Private Label Data
Generall Head
Row Unshuffle
Column Unshuffle
(Private)
Transformer Encoder
Potential Attacker
(General) Patch Embedding
position smbedding
Random Row Shuffle
Column Shuffle
Erto Gradiente
Blocks
(optional)
Features
(Third Party or Cloud)
Figure 3: The structure of our preecc-pressrvingg split learning over shuffled Transformers.
5 METHODOLOGY
Inspired by the permutation invariance properties of Transformer encoder blocks, we present our method to preserve training data, inference data and model weights privacy in the split learning framework, followed by the privacy indication of shuffling.
5.1 SHUFFLED TRANSFORMERS
The overall scheme of our method is shown in Fig. We split typical Transformer-based model into three stubs: the part from input layer to patch embeddings residing at the edge, the transformer encoder blocks at the cloud, and the MLP and loss layer at the edge. Position embedding is op- tional and depends on practical situations. Being transmitted between the edge and cloud, the smashed data in the forward loop and backward loop referred as features and error gradients, respectively.
Our method rums at the edge, processing the smashed data transmitted back and forth between the edge and the cloud. We introduce four basic operations: row shuffle and unshuffle, column shuffle and unshuffle. All shuffling orders the features sent from the edge to the cloud. The features Z = F(X) are expressed by (p, d) (e.g., (197, 768)) matrix, where p denotes the number of patches and d the dimension of each patch. We left the batch size out of the modeling, as shuffling takes place within single input. We shuffle the patches to be sent and unshuffle the received features by
secret of the edge. We perform
and column shuffle to
Shuffle: Mz (Z) = PRZP-1 C Unshuffle: Mz (F(P) (Z))) P (M2(
(8)
(9)
where PR E {0, 13xP and Po E (0, 1]dxdd are row and column permutation matrices, respectively. The row and column shuffle jointly denoted mechanism Mz. Pi is chosen randomly per Z,
5

---

Under review as a conference paper at ICLR 2023
whereas Pg is chosen per model, ie., Pc is the same for all inputs. The model stub F(P) on the cloud is trained as the usual network, and the output of Transformer encoder block is sent to the edge for unshuffle by Eq. 9 The backward loop is no different from the normal backward propagation.
Privacy for model weights and training data. From Thm.
know that Transformer en-
coder blocks at the cloud trained on Mz has the following unique property. Letting F(P)
(Wi b(p) 7(P) } and F { b, 7 denote the {weight matrix, bias, layer normalization pa- rameter) of the cloud model trained on Mz(2 (Z) and the normal Z, respectively, we have:
W(r) P & Mw b(m) b Y(P)= =
(10)
Note that Eq. 10 demands the weight matrix to a square one, which requires minor modification
to the cloud model as we will elaborate later. is an interesting fact that if the model is trained on the shuffled patches Mz 2), the randomly initialized weight Wo learns to become W(P) instead of W, and thus the true model weights unknown to the cloud. Privacy for training data is preserved by Mz, as each input is randomly row-shuffled by PR and column-shufffed by Pc before being sent. Note that since partieular patch size is specified, all patch size would work but the finest granularity is recommended for privacy concerns. We will give the formal guarantee in Sec. 5.2
Protection of the inference data. According Thm. it is obvious that the shuflle (Eq. 8) and unshuffle (Eq. 9 procedures give legitimate testing results. Since the feature sent to the cloud is shuffled, the testing data privacy is preserved. In addition, only the entity who holds Pc would produce valid inference results on (m))
F(pp (Z) Invalid Result,
M2(
(11)
Re-encrypting the model is also available with our method. The edge may pre-train secret Trans- former body with a secret Pc, and later can obtain the unencrypted weights W = P WWep Pc, or re-encrypt the model to authorize other party to use it: W(P) Pc W Other parties who hold Por can further perform privacy-preserve
transfer learning or fine-tuning on the model.
Model structure modification. Our method requires all the weight matrices in the Transformer encoder blocks and the MLP layer to be square ones. For example, the multi-head attention in the classical ViT-Base (Dosovitskiy et al., 2020)) introduces non-square weight matrices, and its MLP has an input/output dimension of 768 but a hidden layer of dimension 3072. To implement shuffled transformers, each head has be square: weights of the linear projection layers of Q, K, V are reshaped to (768 x no..of-heads 768), so that each head has a shape of (768, 768). Instead of concatenating them, we calculate their average to keep the square shape of the weight matrices, which mildly increases the computational overhead but no accuracy decline. Or one can simply choose use single-head attention to replace the multi-head one, which also has limited impact to the model performance. The MLP layer is reshaped with 768-hidden units, which keeps the weight matrices square.
5.2 DEFINITION OF PRIVACY
The purpose of shuffling is prevent the attacker from reconstructing input X given the feature Mz (2). In this work, we consider recovering Z to be the same with reconstructing X, as a black- box white-box attacker can easily invert X from Z. To quantize the likelihood that adversary rebuilds Z from Mz we first define neighboring permutations as:
Definition 1. (Neighboring Permutations.) For feature matrix E RRpd all row-column permula- tion orders of Z constitute S. Any two permutations o, o' E S are neighboring permutations.
Our privacy definition based on shuffling is as follows.
Definition 2. (a (a-prriacyy) Given the private feature Z and permutation set S, a randomized shuf- fling mechanism M M + Z' E is o-private if for all Z, Z', and any neighbouring permu- tations o, a', we have
Pr[M(o(Z)) z'I (r (Z)) Z').
(12)
o- o-privacy suggests that shuffling mechanism M is agnostic of the relative order of patches. Thus any adversary is incapable of telling the original order from its neighboring permutations, given the

---

Under review as a conference paper at ICLR 2023
perturbed feature Z' This definition shares some similarities with do-privacy in (Meehan et al. 2021) but ours removes a in de -riivaacc as permutations are sampled from a uniform distribution rather than Mallows model. With the definition, are equally likely for an input, our Mz(Z) has the probability of plat to reveal the true Z, which is negligible. Similarly for weights shuffling, Mw (WW and Mw (PW P-!) (where P is a random permutation matrix) have the same probability to yield W', which has ar probability to be the true W. Hence the mechanism prevents any adversary from recovering the true weights. Hereby have
calculate that if all row-column permutations
I
Proposition Input shuffling Mz(+) o-private with being the set for all possible PR; Pc permulations.
Proposition 2. Weights shuffling (w(+) is a-private with S being the set for all possible Pc: Pc¹ permatations.
EXPERIMENTS AND EVALUATIONS
We first verify the properties of the shuffled Transformer by experiments, and show its defence capability against attacks.
Setup: Our implementation is built on Pytorch and Torchvision. We use Cifarl0 Krizhevsky et al. 2009) consisting of 60,000 natural images in 10 classes, and CelebA (Liu et al.
2013) containing 2,022,599 faces from 10,177 celebrities. On CelebA, adopt t timm model vit base p bit.bas..attchl....... 224 (ViT-Base) pre-trained on ImageNet to transfer to 40-binary-attriutee clas- sification task. We adopt single-head ViT-Base according to the modification stated in Sec. 5. with the following structure: 12 layers, image size=224, patch size=16, umbeeding.dimm7000 and one head. The model is referred to single-head ViT for CelebA later. A SGD optimizer is used with cosine scheduler, for which the (initial, final) learning rate are set to (0.05, 2 x 10-4) and (5 x 1.-2 10-9) for the MLP and the encoder blocks, respectively.
happ_idden_ddmmmee
On Cifar 10, we use a smaller ViT with the structure: 6 layers, image size=32, patch size=4, embed- ding dim=512, mlp hidden dim=512, 1 head in the row-column-shuffe, case and heads in others. The models are called the single-head and the multi-head ViT for Cifarl0, respectively. These ViTs are trained from scratch on Cifar10, and thus provides satisfying but inferior accuracy to the pre- trained one. An Adam optimizer and cosine scheduler with learning rate 10 are used.
Baselines: We compare our method with a set of existing
methods. Conventional cryptographic tools are not included for unbearable computational and communication costs. Base- lines include unprotected split learning (SL), adversarial learning (adv) (Xiao et al., 2020), methods based Transform containing adding Gaussian noise (0 4) (GN) (Dong et al. 2019) and Blur (Ryoo et al. 2018).
Metrics:
We evaluate model performance from the accuracy, privacy, and efficiency aspects. The average classification accuracy of 40 attributes, and the 10-class classification accuracy are reported for CelebA and Cifar10, respectively. Privacy is gauged by the attackers' capability in reconstruct- ing inputs. We select popular metrics such as Structural Similarity (SSIM), Peak Signal to Noise Ratio (PSNR) (Hore & Ziou| 2010), and F-SIM. For F-SIM, We feed the original and reconstructed inputs into third-party network and compare the cosine similarity between the features. The third- party network for CelebA is InceptionResNetVi of FaceNet (Schroff al.) (015)), pre-trained on VggFace2 (Cao et al. 2018), and that for C0 is ResNet18 88 pre-trained on ImageNet.
6.1 VERIFYING PROPERTIES
We experimentally verify the properties of shuffled Transformers by their accuracy performance.
To verify Thm. | and Thm. we train and test models with or without row-shuffled (RS) inputs. No model modification are needed for row shuffle and thus the original model structures used. Testing accuracies reported in Tab. T Despite being shuffled or not, the testing data reach approximately the same accuracy for each dataset, verifying the row shuffle is indeed transparent to the Transformer encoder blocks. The model trained row-shuffled
Row-perm har--eemutaaton-quuvllleeee

---

Under review as a conference paper at ICLR 2023
data has an equivalent performance to the model normally trained, verifying their training processes are equivalent. On CelebA, removing the position embedding from the model merely leads to an 0.506% accuracy drop compared to the unprotected SL (91.908%).
Table 1: Accuracies( %) on row-shuffled and row-column-shufite data, Shuffle methods of the testing data correspond to that of the training data.
Train
ViT Cifar10
VīT-Base CelebA
multi-head VIT Cifar10
single-head ViT CelebA
Test
w/ RS
w/o RS
w/ RS
w/o RS
w/ RCS
w/o RCS
w/ RCS
w/o RCS
w/ Shuffle
78.35
78.38
91.40
91.61 91.52
80.76
10.38 80.98
91.30
79.76
wfo Shuffle
79.08
78.40
91.62
7.50
71.50
91.51
To verify Thm. 3 and Thm. we train and test on natural or row-column-shuffled (RCS) data, and report the testing accuracies in Tab. | Particularly for CelebA, we pre-train the single-head ViT on RCS (natrual) ImageNet data, and transfer the weights of the 20th epoch to CelebA. 'Training with RCS' suggests both pre-training and fine-tuning are on RCS data. Note that due to the imbalanced data distribution, the average accuracy reported for the 40 attributes of CelebA around 66 73% for random guesses. And the benchmark of CelebA on pre-trained ImageNet is around 91 %. It is clear that if the model is trained on normal data but test on shuffled data, or vice versa, its performance is close to random guesses. Otherwise, the shuffled Transformer almost achieves no accuracy loss.
hww--colmmn-shuttte--eiivaaaali
Table 2: Accuracies(8) of decryypted/re-eeerypeed models.
Table 3: Accuracies(%) of CelebA models w/ and w/o Position Embedding (PE).
Encrypted
Decrypted
w/ PE
w/o PE
single-head VIT C0
79.55
79.01
unprotected SL
91.91
91.52
multi-head VIT Cifar10
80.96
80.67
RS
91.83
91.40
single-head VIT CelebA
91.51
91.30
We also verify decrypting and re-encrypting the weight matrices are feasible with Eq. 10] For each model, we 'encrypt' the naturally trained model by multiplying data. And we also 'decrypt' the
Decryption and Re-encryption:
random permutation matrix and have it tested on the shuffled data and test it on plain data. All the testing accuracies are
model trained on row-column-shufiie reported in Tab. and the results are almost no different from the benchmarks.
Position embeddings: Our method has no influence on network parameters on the edge, including positional embeddings (see Appendix B.6 and C.6 for more detail). As shown in Tab. shuffling has little impact to accuracy despite the position embeddings exist or not.
Further verification experiments on NLP tasks and tabular data can be found in Appendix C.3
6.2 DEFENCE AGAINST ATTACKS
We focus on the privacy performance of our method against attacks in Sec. 3 in comparison to the baselines. As we observe, position embeddings hurt training data privacy in our black-box attack since such an attack is very strong, and almost does not affect accuracy, we choose to remove position embedding in training.
Defence in inference. The train set of CelebA is adopted as Navr and the test set is used as the private inference data. All defence methods are applied to the same edge model F, a fixed patch embedding layer.
In inference, the black-box attacker can only acquire smashed data once, and thus we fix weights
of the edge model and train the attacker model to minimize the loss of Eq. 2 where = 1. We implement the attacker with an MAE decoder G. pre-trained on ImageNet with an additional position embedding layer at the head of the decoder and a Tanh activation layer at the rear. We report the inference accuracy and attack performance in Tab. 4 It is observed that adv and Blur fails to maintain privacy guarantce. GN successfully prevents the attacker from reconstructing the private inputs but degrades the accuracy considerably. Our methods achieve satisfying privacy performance across all metrics while sharing close accuracy to SI..
8

---

Under review as a conference paper at ICLR 2023
Table Accuracy and privacy on the inference data, CelebA, & means desirable direction.
Utility Accuracyt
Privacy in Black-Boo
Privacy in White-Bo
SSIM.
PSNR
F-SIM
SSIM
PSNRL
F-SIM +
unprotected SL
91.91% %
0.645
16.247
0.933
0.173
12.411
0.738
adv
91.82%
0.539
12.123
0.767
0.173
12.411
0.738
Blur
89. 89.84%
0.501
14.233
0.501
0.079
10.729
0.124
GN
82,40%
0.290
13.052
0.361
0.078
9.968
0.127
Our RS Our RCS
91.83%
0.243
10.395
0.299
0.315
10.519
0.139
91.58%
0.270
10.629
0.345
0.160
10.464
0.107
Original
Black:
Black:
Black:
Black: RCS
White: SL
White: RCS
e=10:
Figure 4: The visualization effect of input reconstruction on CelebA under black-box attacks (Black), white-box attacks (White) and attacks to training (e 10).
The white-box attack follows Eq. with 100,000 optimization iterations. As we can tell from Tab. the transform- based methods successfully defends against the white-box attack for introducing ran- domness, so our method, but their methods suffer great accuracy losses. This is also verified in visualization results of Fig. and further results on Cifar10 are left to Appendix C.5
Defence in training. We launch an adaptive black-box attack on features collected over 10 rounds (e = 10 Eq. The attack we launch is much stronger than practice, as we choose Xaur from the training set. In real-world, the adversary hardly obtains the training data. The final testing accuracy and privacy performance reported in Tab. [ It can be found that our RCS strong preserving the privacy of the training data without any loss of accuracy.
Memory Ovarhaadlen B
Training Loss
Table 5: Results of black-box attack on
RCS w/
MACC/M
RCS wro PE
CelebA to the training process.
Utility Accuracy
SSIM
PSNR.
Privacy
F.SIM
6070
10 Training Epoch
blur Our RS
89.84%
U.34
13.50
0.39
91.40%
0.27
10.81
0.39
Figure 5: The computational overhead, memory cost, and convergence curves on ImageNet of the normal split learning and method. PE stands for position embedding (ViT-Base).
Our RCS
89.92%
0.09
10.46
0.34
Efficiency. To see if our method incurs additional overhead to the normal split learning framework, evaluate its efficiency by MAC operation counts (Mace, recording the number of multiplication and addition operations) on the edge, the memory consumption, and the convergence curve of pre- training ImageNet. The ImageNet image of size 224 x 224 adopted with batch size 256. Results of Fig. can be concluded that our methods are almost as efficient as the normal SL.
7 CONCLUSION
We propose blind training method to realize privacy-preserving split learning, where the cloud trains over unknown data and model for the edge. The method founded on the shuffle invariance property discovered on Transformers, and other Transformer-basee models. Theoretical proofs, property verification, and real-world performance resisting attacks are provided. Our method suc- cessfully defends black-box, and white-box attacks without degrading accuracy and efficiency.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Qiong Cao, Li Shen, Weidi Xie, Omkar M Parkhi, and Andrew Zisserman. Vggface2: A dataset for recognising faces across pose and age. 2018 13th IEEE international conference on automatic face & gesture recognition (FG 2018), pp. 67-74. IEEE, 2018.
Nicholas Carlini, Chang Liu, Ülfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In Nadia Heninger and Patrick Traynor (eds.), 28th USENIX Security Symposium, USENIX Security 2019, Santa Clara, CA, USA, August 14- 16, 2019, pp. 267-2844 USENIX Association, 2019.
Jacob Devlin, Ming- Beig-Wei oe Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810004805. 2018.
Jinshuo Dong, Aaron Roth, and Weijie arXiv:1905.02383, 2019.
Su.
Gaussian differential privacy. arXiv preprint
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Ege Erdogan, Alptekin Kupeu, and A Ercument Cicek. Unsplit: Data-oblivious model in- version, model stealing, and label inference attacks against split learning. arXiv preprint arXiv:2108.09033, 2021.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC confer- ence on computer and communications security, pp. 1322-1333, 2015.
Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 116:1-8, 2018.
Shota Hirose, Naoki Wada, Jiro Katto, and Heming Sun. Vit-gan: Using vision transformer as dis- criminator with adaptive data augmentation. In 2021 3rd International Conference on Computer Communication and the Internet (ICCCI), pp. 185-189. IEEE, 2021.
Alain Hore and Djemel Ziou Image quality metrics: Psnr vs. ssim. In 2010 20th international conference on pattern recognition (ICPR), pp. 2366-2366 IEEE, 2010.
Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pp. 122--1134, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim Deryabin, Eu- nsang Lee, Junghyun Lee, Donghoon Yoo, Young-Si Kim, et al. Privacy-presenve machine learning with fully homomorphic encryption for deep neural network. IEEE Access, 10:30039- 30054, 2022.
Xinyu Lei, Xiaofeng Liao, Tingwen Huang, and Feno Heriniaina. Achieving security, robust cheat- ing resistance, and high-efficiency for outsourcing large matrix multiplication computation to malicious cloud. Information sciences, 280:205-217, 2014.
Ru Li, Shuaicheng Liu, Guangfu Wang, Guanghui Liu, and Bing Zeng. Jigsawgan: Auxiliary learning for solving jigsaw puzzles with generative adversarial networks. IEEE Transactions on Image Processing, 11:511-52,, 2021.
Chun Liu, Xuexian Hu, Xiaofeng Chen, Jianghong Wei, and Wenfen Liu. An efficient matrix multi- plication with enhanced privacy protection in cloud computing and its applications. arXiv preprint arXiv:2105.055 105.0555.. 2021.
10

---

Under review as a conference paper at ICLR 2023
Ziwei Liu, Ping Luo, Xiaogang Wang. and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730-3738, 2015.
Wantong Lu, Yantao Yu, Yongzhe Chang, Zhen Wang. Chenhui Li, and Bo Yuan. A dual input- aware factorization machine for ctr prediction. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 3139-3144 3145, 2021.
Casey Meehan, Amrita Roy Chowdhury, Kamalika Chaudhuri, and Somesh Jha. Privacy implica- tions of shuffling. In International Conference on Learning Representations (ICLR), 2021.
Muhammad Muzammal Naseer, Kanchana Ranasinghe, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, and Ming-Hsuan Yang. Intriguing properties of vision transformers. Advances in Neural Information Processing Systems, 34:23296-23308. 2021.
Giuseppe Ateniese Pasquini, Dario and Massimo Bernaschi. Unleashing the tiger: Inference attacks on split learning. In the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2113-2129. ACM, 2021.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision (IJCV), 115(3)2111-253 2015.
Michael Ryoo, Kiyoon Kim, and Hyun Yang. Extreme low resolution activity recognition with multi-siamese embedding learning. Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings the IEEE conference on computer vision and pattern recognition (CVPR), pp. 815-823, 2015.
Andreas Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer. How to train your vit? data, augmentation, and regularization in vision transformers. 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- tion processing systems, 30, 2017.
Wenhui Wang. Hangbo Bao, Li Dong, Johan Bjorck, Zhiliang Peng, Qiang Liu, Kriti Aggarwal, Owais Khan Mohammed, Saksham Singhal, Subhojit Som, al. Image foreign language: Beit pretraining for all vision and lision-language tasks. arXiv preprint arXiv:2208. 10442, 2022.
Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn, Manmohan Chandraker, and Ming-Hsuan Yang. Ad- versarial learning of privacy-preserving and task-oriented representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 12434-12441, 2020.
Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu. Coca: Contrastive captioners are image-text foundation models, 2022.
Li Yuan, Yumpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. imagenet. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 558 567.567,40 2021.
vit: Training vision transformers from scratch on
Yuheng Zhang, Ruoxi Jia, Hengzhi Pei, Wenxiao Wang, Bo Li, and Dawn Song. The secret re- vealer: Generative IEEE/CVF conference computer vision and pattern recognition (CVPR), pp. 253-261, 2020.
attacks against deep neural networks. In Proceedings of the
11

---

Under review as a conference paper at ICLR 2023
Algorithm Shuffling at the Edge
1: Initialization: Initialize the model. Load permutation matrix Pa of size (d, as the key and
get its inverse Pc
2: Start training
3: repeat
4: Start a new epoch
5: repeat
6:
Get batch of data X from data loader
7:
Get the patch embedding Z of size (batch_size p. d). if using row shuffle then
8:
9:
Get random permutation matrix Pn of size (p. p) and its inverse P Z torch. Pn. Z)
10:
11:
end
12:
if using column shuffle then
13:
Z torch. (Z, Pc!
14:
end if
15:
Send Z to the cloud and retrieve the output Y if using shuffle then
17:
Y matmul) P Y)
end if if using column shuffle then
19:
Y torch morch.matmul(Y. Pc)
21:
end if
Complete the usual backward propagation until done all batches
23:
until done all epochs
1
CLS
4
Transformer
CLS
Encoder
CLS
2
Figure 6: The row shuffle and unshuffle
A DETAILS ON SHUFFLING
Our shuffling scheme described in pseudo code in Alg. I and the illustration figure is given by Fig. It should be noted that the shuffling takes place not the dimension of 'batches' but the rest two dimensions. Taking ViT for example, each image representing p patches, and each patch denotes fraction of the image. Each fraction is embedded into a d-dimensional vector. For example, let of shape (3, 4) and the row shuffle matrix PR be
transformed into a (p, d) matrix
3
Z
5
6
7
8
PR
0
9
10
11
12
The row shuffle is:
5
7
8
PRZ
9
10
11
12
2
3
4
12

---

Under review as a conference paper at ICLR 2023
To further demonstrate the results of shuffling, visualize the row shuffle and row-column shuffle methods on CelebA pictures in Fig. 7b and 7c The column shuffle mixes up pixels from three channels and hence makes the images look like gray
The shuffle method is simple, easy-to-deploy, and effective. We show why works in the following section.
(a) Original CelebA pictures.
(h) Row (patch) shuffled pictures of CelchA. Each of Z denotes fraction of the image, and thus to shuffle rows is to shuffic the fractions.
(c) Row-column shuffled pictures of CelebA. Each element patch comes from pixel, and thus to shuffle the columns is to shuffle the pixels of three channels within the fraction.
Figure Visualization of Shuffling. Our method works on embedded features instead of images, but here we directly shuffle the image to visualize shuffling.
B PROOFS
We show the theorems Sec. hold for Transformer encoder blocks.
B. NOTATIONS AND LEMMAS
The Transformer encoder block is denoted Enc and the loss is f. The patch embedding of single input is expressed as Z of shape (p, d). The first layer in the self-attention contains three parallel linear layers projecting Z to Q, K, V
ZWT Q.
(13)
ZW T K = K.
(14)
ZWT = V.
(15)
Q, K, V are fed to the following attention operation
QKT
= Softmax
(16)
Vd
A SV,
(17)
where S and A are the softmax output, and the attention output, respectively.
The part following the attention layer the ML.P layer:
A AW
(18)
H al (1))
(19)
A HW!
(20)
13

---

Under review as a conference paper at ICLR 2023
where A1. Ag the outputs of the linear layers with weights W1. 22, respectively, and H is the output of the element- wise activation function a, being ReLu or Tanh.
Element-wise operators including shortcut, Hadamard product, matrix addition/subbraatiinn and other clement-wise functions are permutation-equee equivalent
Lemma 1. Element-wist operators are permutation-equiivle
(PiAP)) @ (P:BP:) (i @ B
(21)
On the left hand-side of the equation. aij in A and byj in B are permuted the same position before being performed the operation. On the right hand-side, azj and bij are performed the operation of which the results are permuted. The two are obviously equivalent. Importantly, Lemma 2. Softmax is permutation -etiriionnniivlnnttt... Softmax P; AP)) = (
(22)
This is because element is always normalized with the same group of elements, which are not changed in permutations. Thus Softmax is cenittatiionqquvllnentt
B.2 PROOF THEOREM
Proof. We prove the row-permutation equivalence of Transformer encoder blocks in forward prop- agation (Eq. 5). We denote the tow-permutation matrix as PR- Features are permuted as Z(n) = PRZ. It is worth noting that
P
holds for permutation matrix PR. E is the identity matrix.
We first prove the permutation equivalence of attention.
Q KT
(R)
A(R) = Softmar
((R)
Vd
Z W WK K 2
Softmaz
(R)
(nn) WT
Vd
PRZW WK Z PK
Softmaz
PRZWW
Vd
ZW WWWWZZ ZT Vd.
WK
PRSoftmazt
)P PRZW
ZW WKx ZT
PRSoftmont
IZW?
Vd
QKT )V
PRSoftman
Vd.
PRA,
and thus
Attention (atentiio(PRZ) = PRAttention(22 (Z).
(23)
By Lemma 2 the softmax layer following the attention is permutation-cquivaleen,, And the subse- quent the MLP layer which satisfies:
A2(R) a(A(R) WFWw?
a(PRAWT WT
PRO(AWT) WT
PRA2,
meaning
MLP(PRA) = PRMLP(A).
(24)
Hence we have proved the transformer encoder block is row permuaaaiionnncquivalenttt
Enc(PRZ) = Enc
(25)
n
14

---

Under review as a conference paper at ICLR 2023
B.3 PROOF OF THEOREM! 2
Proof. To prove the gradients are the same when the inputs are row-shuffled, we first calculate the all the gradients from the final layer back the first. Gradients expressed as
dl = tr( dl
dA2)
0A2
tr( 0l
tr( Øl T Hd(W,)) 0A₂
(dH)W?)
0A2
Let's study H first:
Ol
dh tr(
()H)W?)
0A
tr (W2 Ø1
dH)
0A
Øl
-tr((,
W2) dH);
JA2
indicating
Øl = Øl
W2.
(26)
0H
0A₂
For W2.
d/g A tr( Øl
Hd(WI))
AA2
OL
= tr(dW
0A
Øl
tr((
H) H)ddW>)
0A2
and
01
01 T
H.
(27)
OW2
0A₂
For A
Øl
dh tr((
W₂) ddH
AAg
Øl
tr(
d(a(Ai)))
OH
Øl T
tr(
a' d'(A1) ddi))
OH
0l
tx((
2 (((Ai))
0H
and
01
01
W2 3 a' d'(i).
(28)
0A
dA
Similarly, we calculate the gradients of A and WT:
Øl
Øl
W1,
(29)
0A
0A
a1
Øl T
A.
(30)
aw;
dA
15

---

Under review as a conference paper at ICLR 2023
In the attention operation:
0l T dlg tr(
dA)
0A
01 T
01 T
tr(
(dS)V) + tr(
SdV)
0A
0A
dl
y + tr((S" ĐI
ur((
dV),
0A
0A
and
01 = 01 VT
(31)
as 0A
Øl ST 01
(32)
0V 0A
First, for V ZWW:
dl 2 tr( 0l
dV)
0V
tr( Øl T
0l T eV Zdw?).
Wd))
tr(
ov
Similarly, the gradients of Z and Wy are:
Øl 0l
Wv,
(33)
az
0V
a1
01
(34)
dWv
av
Now focus S Softmart
QK"
Va
Øl
dls - tr(
dS)
as
tr( (diag(S) S S)d( QKT
0l T
as
Vd
+tr((diag(S)) (S) 5t S) 0l
T d QKT
Vd )),
as
and thus
S)z 0l K,
0Q Vd (diag (S) S)² 0S
(35)
Ø1
(Idiag (S) - 5 S) 01 TT Q.
(36)
0K
a5
And similarly the gradients of Wq and Wx k are:
01
01 Z.
(37)
aw Q
eQ
Øl
Z.
(38)
OW
OK
What happens in backward propagation with RS: First, let take black-box view of the Transformer encoder blocks. In our scheme, the input of Enc is the shuffled smashed data P and the output is Pn.2. The edge client obtains Pn and reverse the shuffling order to get
16

---

Under review as a conference paper at ICLR 2023
A3(R) Phi A2()- In the following, denote all variables involved with our RS method with subscript (R), and variables in vanilla split learning are without the subscript. According to Eq. 1
A A2 P PRA2 A2.
(39)
We have A3 A2 in plain SL, and thus
OL
01
01
(40)
(A
0A₂
0Ag
Eq. 40 suggests since the forwarding (from A3(R) the loss) is the same between the original and our scheme on the edge, its backward process is also equivalent, iee, each gradient of the weights
between As(n) and the loss / the same for our method and the original SL. Hence we only need to focus on gradients from A2(z) backward.
al
dl = tr( AA3(R)
22))
Ol
tr((PR AA3
yTh (ddA()))
and thus
01
0l
PR
PR
(41)
0A3
0A2
is quite an interesting conclusion, and we will soon find it important to the permutation-invariince
of gradients of the weight matrix. By substituting Eq. 41 into Eq. 27 obtain:
OL
H(R)
(42)
OW 2(R)
AA2(K)
Ōl PRH
(43)
AA
Øl H
(44)
AA2
Øl
(45)
aW2
reveals that the gradients of the weight matrix in our RS scheme would be the same as the gradients in vanilla SL. In fact, each gradient of the weight matrix is -iniuuaatiiooiiiaiianttt i.e., satisfying Eq. [45 whereas each gradient of the intermediate feature
Eq. 45
meeting Eq. 41 Properties of Eq. 45 and Eq. 41 are transductive, carrying from the final layer
backward to the first layer. Hence by Eq. 26
Ōl
Øl 0H
PR
(46)
HH (R)
and by Eq. 28
01
Øl We C (Ri)(A))
PR DA,
0Ai(m)
al
= Pal 0A
W₂ O a' (A1)).
Thus,
01
a1
PR 0Ai*
(47)
0 0A1(R)
and by Eq. 30
01
01
(48)
OW ((R)
OW,
17

---

Under review as a conference paper at ICLR 2023
By Eq. 29
we have:
01
Øt
Pr
(49)
(A(R)
0A
which passes the property S. But S a tricky one since in the derivation of Eq. 23 we notice that S(z) PRSP According to Eq.
31
al @S(m)
01 VT dA(R)
(R)
Øl
PR 0A
V PT R
which interestingly leads
01
01 PR as
P
(50)
(S
This is consistent with the S(z)²s 's permutation form, which passes the elegant properties down to Q.K: K:
01
Øl (diag((S()) - (()) (R))
K(R
(Q)
(5(R)
1
PR al 0S
( (Pddaag(S))P PRS Pd PRSPP
P
PR
Vd
1
Ol
(Pildiag(S) Sth 5)T P PR
R as
PH PH
PRK
Vd
PR Vd ((diag(S)- - 5t STT 0l
1
K,
0s
and hence
01
PR al
(51)
aQ (Q(R) (R) iQ
Similarly,
01
PR OK
(52)
0K (R)
By Eq.
37
0l
Øl
Z(R)
(53)
aW @QQ()) Q(n)
(Q(n)
01
01
P PAZ
(54)
aQ
aWQ
Similarly,
01
Øl
(55)
aW OWK(R) k(
oW*
And for V,
01
al
STH AA (R)
(56)
OV(R)
Øl
PRSTT P PR DA
(57)
-PRST Øl
(58)
0A
Øl
PR ΦV
(59)
Similarly,
18

---

Under review as a conference paper at ICLR 2023
a1
01 T (R)
X(m)
(60)
V(R)
01
σv Pk PR
(61)
a
(62)
dwv
For now, we have proved that the gradients of weights in our RS scheme are exactly the same as the gradients of weights in vanilla split learning, and by induction, we can conclude that the learned Enc with RS method is no different from the learned Enc without. It worth mentioning that if the attention is cut to multi-head, the property remains because cutting the second dimension (column) does not affect the permutation of the first dimension (row).
B.4 PROOF OF THEOREM 3
Proof. We denote variables involved in our RCS method with subscript (P). Row shuffling is included special case of RCS.
First and foremost, we 'encrypt' all the weight matrices by Eq. 10
Wilp) Pc W.W.
where Pg is the column permutation matrix, W; the weight of a normal Fnc, and E {1, K, V.. We denote the Transformer encoder block with such 'encryption' as Enciry Note that this operation requires W; to be a square one. We have proposed two ways to achieve this with little modification the original model without performance loss.
For Q:
Q(r) = Z(p) W Q(P)
(63)
PRIP' Po
(64)
= =PAZWTP PRQQPT.
(65)
(66)
Similarly for K, V:
K(P) PRKPT
(67)
V(P) PRVP..
(68)
For S = -Softmar( QK
dd
Q(P) KT
(P)
((m) Softmar(
(69)
Vd.
PRQPT PoK PT
Softmar
(70)
Vd
PROK PT
Softmar
(71)
Vd
QKT
PRSoftmar
PT
(72)
Vd
PRSPP
(73)
So for A:
A(p)
S(P/ViP) PRIPPT PRVPT
(74)
(75)
-PASVPT
(76)
=PRAPT.
(77)
19

---

Under review as a conference paper at ICLR 2023
Following the attention layer, A is fed to the MLP layer:
AL(P) - ((p)W((P)
(78)
PRAPE PoWiPt
(79)
PPRAWI
(80)
PRRAIPC
(81)
Similarly for A2,
A2(P) PRA2PE
(82)
As for the activation in the middle, the element-wise activation function cemmutation-euivvllee.
((P) PRHPC
(83)
Overall, we have proved Thm.
B.5 PROOF THEOREM 4
Proof. By row and column unshuffle, the computation of the forward propagation and backward propagation on the edge is no different with or without our RCS method. Hence we only focus on the propagation of the Transformer encoder blocks.
Similarly to the proof on RS, we denote A3(P) as the reversed intermediate feature that the edge receives:
As(P) P A2pp
(84)
By Thm. we have
Aapp) = A2 = A3.
(85)
First we focuses on the MLP layer:
Øl T ((
dl tr(
0Ag
=tr(Po Ø1 d(2r))
0Ag
Øl
=tr((Pn AA,
PT) dA2()))
that is:
01
PR Ol
PT.
(86)
0A2(P)
0A
With H(m PRHPT and Eq. 27 the gradient:
al
H(P)
W
AA2P)
Øl PT PRHPP
Pc 0A2
0l HPT
Pc dA₂
Øl
Pc
pT
OW2
that is:
01
Øl pT
Pe
(87)
OW2P)
aW2
20

---

Under review as a conference paper at ICLR 2023
By Eq.
28
Eq.
87
and similar derivation of Eq. 47 have
a1
(2()) o d' (A(()))
0AKpP)
0A2(p)
Pn 0A2
P PcW,Pe ① (Raa Pe
Øl
PR 0.2
W2Pel
[PRa' (RR'(A1)PP Po
Øl
PRl PRIgA 0A2
W₂ 2 (
Øl
PR 0Ai
Po.
that is:
01
Øl
PR
P..
(88)
(A((P)
0A1
The weight Wi(P) in the MLP has the following gradient by Eq 30
Ol
(PP
oW
@W((P)
I(P)
(P((P)
Øl
Pc AA
P
PRAPE
Pc Owl
P..
that is:
01
Øl
Pc
P
(89)
OW
ow,
And we come to the attention operation, from Eq.
we have
Ø1
Øl
WRPP;
0A(p)
dAi(r) Øl
Pn Pa 0A1 P Po
Øl
PROA W.PT
Øl
PR 0A
p.
that
01
0l PR
PT. 0A
(90)
AA(P)
Hence we observe the permutations rules for the gradients of the intermediate-layer outputs vary from the gradients of the weights. As for the gradients of the softmax-layer output, we have
0l
al
V dA
Øl P..
Pn a
PT.
Øl
=PR T PT
Øl
- as PR:
21

---

Under review as a conference paper at ICLR 2023
that is:
a1
01 Pn
Pk.
(91)
as
as
Since (p)) follows Eq. 73
we have the gradients for (P) combining with Eq. 91
0l
Øl
[(diag(S(p)) -()
K(P)
(Q)P)
d
(S
PR. P PRSP PR al (PRdiag( -
PR
as PRKP'
as
dl
((Padiag (S) PRSS SP PR P
PRIPE
as
0l
vd - PR P 05
5t
Vd PR - S" S)
P PRKPE
0s
01
PR(diag(S) - ST S)
PT PRKPE
Vd
0s
1
Ol
PR (diag(S) S 5) 0S Vd
KP
= PR P
aQ
By a similar derivation on K we obtain:
Øl
ōl
PR
P
(92)
(K(P)
Following a similar proof to the gradients of W((P) or W2()). we could easily derive:
Øl Pc
0l
P.
(93)
QPP)
aWQ
Q
Øl Pc dWk K
01
P.
(94)
OWK(P) K(P)
And by Eq. 32 the gradient of V(P) is
Ø1
ST Øl AA(P)
(VP)
Øl PRSPP PR A
P
Øl PT.
Pn OV
thus we have
PR
PT
(95)
0VP)
0v
01
Pc al PT.
(96)
@Wv(r)
awy
So far, we have proved the rule for the gradient of weight matrices:
Øl
Øl PT, i (1
Pe ow,
(97)
OW .PP))
W) are the weights of Enc(P) while W. the weights of Enc. With some induction, reach the conclusion that if a Transformer encoder blocks is randomly initialized and trained with
(P) it would eventually learn to become Enc(p), which is associated with Enc by Eq. 97
22

---

Under review as a conference paper at ICLR 2023
B.6 PROOFS ON PARAMETERS OF THE EDGE
We show in this section that the parameters of the edge, including the weights associating position embeddings, the same despite the shuffling method is used not.
Theorem 5. The parameters the edge trained with without row-column shuffling are the same.
Proof. We denote the embedded feature in the naive SL and in the our shuffling scheme as Zo Zo(P). respectively, and the feature be sent to the cloud in the two schemes as Z, ((P) In naive split learning. Zo = Z and 0 aZo az our scheme we have:
ipp; PRZoOP)
(98)
To prove the claim is prove:
Ø1
(99)
oz
aZo
It is clear that
01 T dZ(p))
dl = tr( (Z
tr( PC 01 T
Pk PRdZo(P) Po)
oz
tr(PP Pe Øl dZ)(P))
az
Øl
= tr( dZ)()))
0z
Hence,
ØL 0l
(100)
0Zu(P)
oz
OZ.
The second equality holds by similar argument to Eq. 95 The equivalence between the edge
weights the two schemes is accomplished by Eq, 100 and the fact that their forward procedure is exactly the same.
C SUPPLEMENTARY EXPERIMENTS
C.I VERIFYING THE PROPERTIES ON BIAS AND LAYER NORM
We do not mention bias and y, the weight in layer normalization, in the proofs in Appendix B Here some intuition about why they encrypted in the way shown in Eq. 10
b(p) bP ((P) = PP
Both bias and y are 1-D vector, and each element only interrelates with the corresponding column of Z in both forward and backward propagation. So if the columns permuted, bias and 7 should be permuted in the same way. During the experiments we find that the encryptioo/deerrytion of Cifar10. But CelebA, if most weight matrices
bias and y hardly affect the model performance are encrypted by Mw while bias and are not permuted, the accuracy would be greatly affected, which is merely 79.03 79.056%. But if the encryption is strictly performed as Eq. [0, the relative accuracy difference between normally trained model (tested with Z) and an encrypted model (tested with Z ( is merely 0.00013% (91.5 99.509911 % and 91.50979% respectively).
C.2 VERIFYING ON ORDER-DEPENDENT DEPENDENT TASKS
We consider the classification task is weakly order-dependent, i.e., the task may rely little the order of the patches of an input image. To verify the feasibility of our method on strictly order- dependent tasks, we designed simple task which strongly depends the input order. We label
23

---

Under review as a conference paper at ICLR 2023
the shuffled images in CelebA as I and the original ones O, and train ViT-Base the them from scratch to distinguish whether the images are shuffled. Within one epoch, the accuracy ViT- Base reaches around 97%, showing the model and the task strictly order-dependent. And conduct similar property-verifying experiments in Sec. 6.1 and the conclusion does not change: RS transparent the encoder, and encrypted models only process encrypted data. It demonstrates the shuffled Transformer also works on tasks strongly associated with the input patch order.
C.3 VERIFYING ON NLP DATA
We implement small Bert model and pre-trained model fine-tune it for natural lan- guage inference on the SNLI datase The small Bert has 2 layers and the input Z is of shape (batch_size, 128, 256). Due the non-square MLP (with hidden dimension of 512), the column shuffle is not suitable for this pre-trained model. Noting that the position embedding is not removed from the model. With or without the row shuffle method. the small Bert achieves the similar accu- racies: 76.4% and 76.5% respectively. The code is provided in supplementary materials.
C.4 VERIFYING ON TABULAR DATA
We use the DIFM (Lu 2021) model and Criteo dataset verify the proved properties on tabular data. The vector-wise part of DIFM model is Transformer encoder block. We shuffle the rows of the vector-wise part of the input and unshuffle its output. The model achieves the same AUC, 0.777, with without the row shuffle method.
summary, our method works on CV, NLP and tabular data, despite the specific tasks. This attributed to the modeling where Z is general matrix, and the permutation invariance property holds with no strings attached. Speaking of invariance, a negligible 10-7 error occurs per element in the permutation due float calculation error.
C.5 ATTACK RESULTS TO CIFAR10
(a) Original Cifar10 images
(b) Black-box (e=1): RCS
(c) Black-box (c=10): RCS
Figure 8: Results of the black-box attack to the private inference data of Cifar10.
We provide additional experimental results on Cifar10 in Fig. g and Tab. 6 Black-box attacks
described in Sec.Blix launched. Due to the sparse data distribution, the defence Cifar10 is more successful than on CclebA. RCS almost eliminates the sketch of the object in each reconstructed image in Fig.
24

---

Under review as a conference paper at ICLR 2023
Table 6: Results of the black-box attack to the private training and testing data of Cifar10. means desirable direction.
SSIML
PSNRL
F-SIML
unprotected SL
0.360
2.761
0.644
Our RS (inference)
0.075
0.987
0,464
Our RCS (inference)
0.094
0.984
0.421
Our RS (training)
0.275
10.812
0.390
Our RCS (training)
0.264
10.460
0.336
(a) Normally Learned
(is) Before Shuffle
(c) Alter Shuftle
Figure Cosine similarity between every two patches position embeddings learned different ways.
C.6 EXPERIMENTS ON POSITION EMBEDDINGS
To further verify that our method has little impact to network parameters on the edge as proved in Appendix B.6 visualized in Fig. 9 the cosine similarity of position embeddings learned at different places of the model on the CelebA classification tasks. We found that the position embedding is placed ahead of shuffling. the cosine similarity shares similar state that without shuffling, as shown in Fig. resembling a human face. Hence our shuffling method almost does not vary the weights on the edge.
To verify the impact of the removal of position embeddings in training, we train the Transformer from scratch and on pre-trained ones, both on large and small datasets. Except for training from scratch on Cifarl0 all model accuracies maintain at a similar level to that with position embeddings. In the exceptional case, the accuracy drops by 10% (~~ 80% with position embeddings and 70% otherwise). We consider it mainly due to the poor performance of the natural Transformer on small datasets. After all, Transformer works best with pre-training on large dataset.
C.7 ABLATION STUDY OF PATCH SIZE
Table 7: The privacy, utility and efficiency when selecting different patch size on eifar10. The width and height of input image are both 32 pixels. means desirable direction.
Utility
Privacy
Efficiency infer time (2k images)
patch size
num.
Accuracyt
JigsawGAN Acc|
2 x 2
256
82.64%
<0.1%
33s659ms
4 X
79.67%
1.16%
7s751mo
8 x 8
16
77.25%
60.03%
2s1 166s
16 x 16
66.51%
83.52%
694ms
The selection of different patch size have significant influences on the privacy, accuracy and ef- ficiency. For fixed input image size, increasing the patch size will decrease the total number of patches which are the basic unit of shuffling. As shown in Table 7 increasing the patch size obvi-
25

---

Under review as a conference paper at ICLR 2023
ously degrades the accuracy, since the performance of ViT is affected by decreased patch numbers. Revealed by the results of JigsawGAN (Li et al., (021) (using GAN model to reorganize the shuf- fled patches, aka. Jigsaw problem) and black-box attack, increasing the patch size also has harmful impact on the privacy, which indicates that larger size of patches carry more information in one basic unit of shuffling and make it easier for attacker to solve the relationships between patches. However, larger patch size and fewer patches significantly shorten the computation cost, as the time complexity of Attention block is quadratically proportional the number of patches.
26


Reviews:
[{"review_id": "NV_P0JFHGW", "reviewer": "Reviewer_pVBj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces blind training to preserve the data and model privacy via shuffled Transformers. An intriguing finding is proposed that, inputs and the model weights of the Transformer encoder blocks, the backbone of Transformer, can be shuffled without degrading the model performance.", "summary_of_the_review": "This paper proposed a blind training method to realize privacy-preserving split learning, where the cloud trains over unknown data and model for the edge. Theoretical proofs, property verification, and real-world performance-resisting attacks are provided. The method successfully\ndefends black-box, and white-box attacks without degrading accuracy and efficiency. However, there are some concerns/ weaknesses need to be clarified.", "strength_and_weaknesses": "strength:\n\nThis work focuses on a valuable problem – data and model privacy preservation. The authors give a clear problem statement about the concept of blind training. Moreover, experiment results prove the effectiveness of the proposed method.\n\nweakness:\n\n1. The authors state that “P_R can be chosen randomly for each Z, while P_C is randomly chosen once for the model”. How the row and column shuffling strategy is determined? \n\n2. What are the differences between row shuffling in the paper with the original training data shuffling operations?\n\n3. Since only one type of column shuffling is adopted for each model, will the performance be affected by the highly correlated features? If two dimensions have large information overlap, swapping them seems have a small impact on the performance. Did the authors consider such a situation? Such a situation is beneficial or harmful for the proposed method? \n\n4. What does ⊥ in Equ. (7) refer to? Perpendicular?\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HIK1ojUw3oO", "reviewer": "Reviewer_jfZZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a shuffling based method to improve the privacy and enable a split learning paradigm, where the cloud server only requires shuffled data from the edge. ", "summary_of_the_review": "I feel the paper lacks clarity in both the scope and the technical details. The proposed method might just be a trivial shuffling of the image patches without position encodings, and therefore lack technical novelty. ", "strength_and_weaknesses": "Strength: The proposed approach can improve the privacy of edge users.\n\nWeaknesses: \n\n1. The experiments are limited to vision Transformers, but the title seems to over claim it to any Transformer. For languages, it should be hard to train without position embeddings, as the orders of the tokens are important. I would suggest the authors to either modify the title or show some empirical evidence that the method also works for language models.\n\n2. I am quite confused with the notion of row and column shuffling. How are the matrix multiplications defined (Wx or xW)? At the beginning of Section 3, each X is just a vector. Do you shuffle on the patch level or pixel level? If you only change the order of the patches, isn't it trivial that the output won't change when position embedding is not used?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "78-JhGsSzOd", "reviewer": "Reviewer_N7YY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a shuffled transformer structure for privacy preserving. The networks are split into two parts, where the first part encodes the input data and the the input to the second part network is shuffled features without knowing the original data. The experiments have shown superior performance against diverse adversarial attacks. ", "summary_of_the_review": "The paper proposes a shuffled transformer for privacy protection. The idea is interesting and original, and the authors have provided a detailed theoretical deduction of the inference stage. However, the motivation seems vague to me and it is very hard to follow. I have doubts of whether such a shuffling on the feature space will affect the position encoding, and thus I'm not convinced by the qualitative and quantitative results. ", "strength_and_weaknesses": "Pros:\n+) The paper proposes an interesting topic of performance privacy protection on shuffling input features in the Transformer structure;\n+) The paper provides theoretical deduction on shuffled transformer;\n\nCons:\n-) The motivation is not clearly elaborated. Examples of privacy leakage of transformers should be provided to validate the importance of designing a shuffled transformer;\n-) After shuffling, is the positional encoding not working on such Transformer structure?\n-) I'm curious about the performance degration with the proposed method compared with naive transformer structure. More analysis should be given.\n-) The paper is very hard to follow. Authors should provide a more clear elaboration of the proposed method. \n-) Writing could be improved. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3s1gSqFMQUs", "reviewer": "Reviewer_kXfb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes *blind learning*, a novel split learning framework for training transformers. In this framework, the patch embedding, MLP, and loss layers reside at the client, and the transformer blocks reside at the server. During training and inference, the client obfuscates its data and model weights by shuffling the patch embeddings before sending them to the server, and then unshuffles the outputs of the transformer blocks sent back by the server. Crucially, since transformer blocks are invariant to random shuffling of the input data, the proposed shuffling by the client does not degrade model training or inference. Theoretical analysis and experimental evaluations demonstrating the transformer invariance to shuffling are provided. A privacy analysis of the proposed framework is also provided. A novel privacy definition for shuffling mechanisms is also provided. Lastly, the proposed framework is compared against various baselines with respect to classification accuracy for a target task and susceptibility to black-box and white-box reconstruction attacks.", "summary_of_the_review": "Novel framework and theoretical analysis. Strong results.", "strength_and_weaknesses": "# Strengths\n\n* Novel algorithm. The main idea of using the shuffle invariance property of transformers to obfuscate the client data and model weights during split learning is ingenious, novel, and well motivated.\n\n* Novel theoretical results. Analysis of the shuffling invariance property of transformers is novel and provides a strong theoretical foundation for the proposed framework. Privacy definition for shuffling mechanisms is also interesting and novel, albeit a bit tangental.\n\n* Good results. The proposed method achieves a favorable privacy-utility trade-off compared to relevant baselines. This is demonstrated clearly with experiments on the CelebA and CIFAR10 datasets. \n\n# Weaknesses \n\n* Poor writing. The paper would benefit greatly from a review by a native english editor.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject