Capped Linex Metric Twin Support Vector Machine for Robust Classification

In this paper, a novel robust loss function is designed, namely, capped linear loss function Laε. Simultaneously, we give some ideal and important properties of Laε, such as boundedness, nonconvexity and robustness. Furthermore, a new binary classification learning method is proposed via introducing Laε, which is called the robust twin support vector machine (Linex-TSVM). Linex-TSVM can not only reduce the influence of outliers on Linex-SVM, but also improve the classification performance and robustness of Linex-SVM. Moreover, the effect of outliers on the model can be greatly reduced by introducing two regularization terms to realize the structural risk minimization principle. Finally, a simple and efficient iterative algorithm is designed to solve the non-convex optimization problem Linex-TSVM, and the time complexity of the algorithm is analyzed, which proves that the model satisfies the Bayes rule. Experimental results on multiple datasets demonstrate that the proposed Linex-TSVM can compete with the existing methods in terms of robustness and feasibility.

Introduction
Data collecting and reasonable processing are becoming increasingly crucial as modern computer technology advances. As an excellent machine learning tool, support vector machine (SVM) [1][2][3][4] has been widely used in financial forecast, bioinformatics, computer vision, image annotation, data mining and other fields in recent years. The main idea of SVM classification based on statistical learning theory and optimization theory is to construct a pair of parallel hyperplanes to maximize the minimum distance between two classes of samples. Generally speaking, the optimal hyperplane is realized by solving an optimization problem with inequality constraints. In order to avoid overfitting, scholars extend support vector machines to soft difference support vector machines (C-SVM) [5], introduce relaxation variables to relax constraints, and increase the penalty term of relaxation variables in the objective function. However, the loss function adopted by C-SVM is generally a hinge loss, which makes it very sensitive to noise. In the following research, C-SVM is extended to deal with the problem of function estimation, and a support vector interpretation of ridge regression [6] is proposed, which is different from the inequality constraints in C-SVM, as it uses equivalent constraints. Similarly, Suykens [7] considered equality constraints in the sense of least squares and proposed a least squares support vector machine (LSSVM). Unlike C-SVM, it does not use the non-support vector machine to optimize the classifier; LSSVM makes full use of the information of all data points and uses L 2 loss to punish both data points symmetrically. In order to further improve the performance of classification, researchers need to impose heavier penalties on samples that are misclassified. For this reason, in the literature [8], Ma et al. considered asymmetric linear exponential loss (LINEX) to be used to achieve this goal, and Linex-TSVM is proposed to study the binary classification problem. However, both SVM, C-SVM , LSSVM and Linex-TSVM have their own advantages, but they all have to solve a large-scale QPP(Quadratic Programming problem), which requires a lot of time to learn and is not suitable for dealing with practical problems. Because all the above models need to solve a big QPP, to further improve the computing speed, Jayadeva et al. [9] proposed a twin support vector machine (TSVM) for pattern classification based on the generalized eigenvalue approximation support vector machine (GEPSVM). Since TSVM solves two smaller QP problems instead of a single large QPP, it can theoretically learn four times faster than a standard SVM. The main goal of TSVM is to find two parallel hyperplanes, each of which is as close as possible to the corresponding class in the sample data, while being as far away from the other classes as possible. Therefore, TSVM is more suitable for the classification of large-scale data.
It is well known that distance metrics play a crucial role in many machine learning algorithms. Although the above algorithms demonstrate good performance in pattern classification, it is worth noting that most of them adopt the L 2 -norm distance metric, whose squaring operation will exaggerate the impact of outliers on model performance. To effectively alleviate the impact of the L 2 -norm distance metric on the robustness of the algorithm, the L 1 -norm distance metric with the bounded derivative has received extensive attention and research in many fields of machine learning in recent years [10][11][12]. Recently, more and more researchers have paid attention to the capped L 1 -norm. The capped L 1 -norm can solve the deficiency of L 1 -norm unboundedness. In particular, Wang et al. [13] proposed a new robust TSVM (CTSVM) by the applying the capped L 1 -norm.
Inspired by the successful application of capped L 1 -norm and linex loss function [14][15][16][17], meanwhile, the latest research shows that no scholar has extended the Linex loss function to twin support vector machines, therefore, a new robust twin support vector machine is established in this paper. The details and the main contributions of this work are as follows: (1) A novel robust loss function is designed, namely, capped linear loss function L aε .
(2) A novel robust twin support vector machine, namely capped linex twin support vector machine (Linex-TSVM) is proposed.
(3) A efficient iterative algorithm is designed to solve Linex-TSVM, which is not only easy to implement, but also theoretically guarantees the existence of a reasonable optimal solution. We analyze the computational complexity of the algorithm and prove that the model satisfies the Bayesian rule.
(4) Extensive experiments conducted across multiple datasets demonstrates that the proposed Linex-TSVM is competitive with state-of-the-art methods in terms of robustness and feasibility. Therefore, the Linex-TSVM is feasible for practical applications.
The rest of this article is organized as follows. In Section 2, we briefly review Linex-SVM and TSVM. In Section 3, we describe in detail the proposed capped linex loss function and Linex-TSVM, and give the relevant theoretical analysis. After the experimental results on multiple data sets are presented in Section 4, we conclude this paper in Section 5.

Related Work
In this section, we are warranted to review Linex-SVM and TSVM.

Linex-SVM
Linex loss function is a typical asymmetric loss function, defined as: where a = 0 is a parameter. If a < 0, the left side of Linex loss is steeper than the right side, and the opposite is true when a > 0. The value of |a| decides the symmetry of Linex loss function. This shows that the symbol of a determines the shape of the function. When a takes an appropriate value, it can be reduced to square loss. Linex loss function is not only asymmetric, but also convex and derivable; thus, it is widely used in statistics.
For the dichotomy problem in n-dimensional Euclidean space, the training set can be expressed as where x i ∈ R n is the feature vector of the data i, and y i ∈ {−1, +1} is the label of the data i. For the training set Equation (2), the Linex-support vector machine model can be written as a convex optimization problem with equation constraints in Equation (3) by  introducing a linear loss function: min ω,b,ξ where ξ = (ξ 1 , ξ 2 , · · · , ξ m ) is a slack variable, C is a penalty parameter and a is a parameter of the Linex loss. Furthermore, we can use the Nesterov accelerated gradient (NAG) method to obtain the optimal solution (ω 1 , b 1 ) and construct the decision function f (x) = sgn(ω T 1 x + b 1 ).

TSVM
The support vector machine is not suitable for dealing with large-scale data, to improve the practical application of the model and further shorten the learning time. Jayadeva et al. proposed a twin support vector machine (TSVM) for pattern classification based on the generalized eigenvalue approximation support vector machine (GEPSVM). The details are as follows: Considering n dimensional Euclidean space R n the binary classification problem, the training set is T = {x i , y i |i = 1, 2...m}, x i ∈ R n , where y i ∈ {−1, 1}. A ∈ R m 1 ×n represents all positive samples; B ∈ R m 2 ×n represents all negative samples. TSVM identifies two non-parallel hyper planes in the feature space: where The TSVM classifier is obtained by solving the following pair of QPPS: min where C 1 ≥ 0, C 2 ≥ 0 represent regularization parameters, e 1 , e 2 are all unit vectors, ξ 1 , ξ 2 are the slack vectors. Then, the dual problem of TSVM is obtained by dual theory: Furthermore, by introducing the kernel method, TSVM can be extended to nonlinear space, and it can be decided whether the sample data x belongs to positive class or negative class according to the shortest distance between the sample data x and two non-parallel planes. The decision function is

Capped Linex Loss Function
In this section, in order to minimize the influence of abnormal values on the classification results of the model, we propose a novel robust loss function, that is, the capped linex loss function. The details are as follows: Definition 1. The capped linex loss function is defined as where a = 0 is a parameter, when a < 0, the left side of the loss function is steeper than the right side; when a > 0, the right side of the loss function is steeper than the left side; see Figure 1. ε > 0 is a thresholding parameter; x i is the component of x. Figure 1 shows the comparison between the capped linex loss function and the linex loss function. Obviously, we can observe that the improved linear loss has an upper bound, and when the error tends to be consistent, even if there are outliers, the loss will not increase to a certain extent, which improves the robustness of the model.

Capped Linex Twin Support Vector Machine
Linex-SVM model still needs to be improved: linex loss is an unbounded function, and the loss tends to be consistent with the increase in error. However, in practical applications, datasets are often accompanied by noise, and the unboundedness of the linex loss function will affect the overall performance of the model. In other words, Linex-SVM is a relatively weak method in dealing with training sets with outliers. In addition, almost all the instances in the Linex-SVM contribute to the final optimal hyperplane, which will greatly reduce the training speed.
In order to improve the classification performance of Linex-SVM, we first improve Linex loss to capped linex loss and introduce regularization term to enhance robustness. Secondly, we generalize Linex-SVM to twin support vector machine, and transform a large QPP into two small QP problems to improve the training speed. Based on the above two points, a new twin support vector machine model, named the capped linex twin support vector machine (Linex-TSVM) is obtained: min where C 1 , C 2 , C 3 , C 4 ≥ 0, e 1 ∈ R m 1 and e 2 ∈ R m 2 are the unit vectors. ξ and η are slack vectors.
In addition, we also notice that when using the traditional convex optimization method, it is difficult to solve the problems Equations (12) and (13) simply and quickly. Here, in order to simplify the original problem to an approximate problem that is easier to solve, we use the re-weighted trick [12,[18][19][20], the most important of which is the formula (12) as an example, for the distance measurement items, when the F = 1 |x| holds, then . Further, in order to simplify function e aξ − aξ − 1 into an easy-to-solve ξ T Qξ, we define Q as diagonal matrices with i-th diagonal element as: similarly, Based on the above discussion and calculation, we can obtain the optimization problem Equations (16) and (17), as follows: min where e 1 ∈ R m 1 and e 2 ∈ R m 2 are the unit vectors, F and K are also two diagonal matrices: (16) and (17), we use diagonal matrices F, Q and K, U, respectively, to reduce the influence of outliers and abnormal noise on the model. Specifically, if the points in the same class are far away from the hyperplane, they can be treated as noise and removed. In addition, the model mainly sets the elements in the diagonal matrix according to the distance from the data point x i to the hyperplane. For F, if f i is greater than ε 1 , the corresponding f i is set to a smaller value (Smallval), which is almost equivalent to 0. Where 'Smallval' is a small constant, which will be set to 10 −8 in the experiment.

Remark 1. What is more detailed is that in the objective functions Equations
The corresponding Lagrange function of the above optimization problem Equation (16) can be written as: where α is a Lagrange multiplier, derive the Lagrange function about ω 1 and β 1 , obtain the following Karush-Kuhn-Tucker Conditions.
Through KKT condition, the dual problem of Equation (12) is as follows: Similarly, the dual problem of Equation (13) is: where β is a Lagrange multiplier, and Thus, we get the vector Z 1 and Z 2 , and gain the new data point x ∈ R n to a positive or negative category.
Based on the above discussion, our algorithm will be presented in Algorithm 1.

Bayes Rule
We want to prove that the model proposed in this paper can satisfy the Bayes rule, assuming that the sample (x i , y i ) are independent of the same probability φ, and the probability φ is defined on X × Y, where X ∈ R n , Y = −1, 1. Further, we assume that the conditional distribution φ(y|x) is a binomial distribution, including φ(−1|x) and φ(1|x). As we all know, the ultimate goal of the classification problem is to obtain a classifier C : X → Y with small error . Bayesian classifier [8] is defined as the classifier with the lowest probability of classification error among all kinds of classifiers.
For any loss function L, the expected risk of the classifier f : X → R can be defined as Next, by minimizing the expected risk of all measurable classification functions, we can obtain Based on the above important definition of Bayes rule, we obtain Theorem 1 to prove that Bayes rule holds for capped linex loss function. The details of the proof are as follows.

Computational Complexity Analysis
This part mainly analyzes the computational complexity of Algorithm 1. As we all know, the computational complexity includes the number of iterations and the computational cost of iterations. The computational complexity of Algorithm 1 after one iteration is divided into two parts: (1) the time complexity of solving QPP is not more than m 3 4 , and the inverse of matrix is not greater than (n + 1)(n + 1). Therefore, the total time complexity of solving Linex-TSVM is about O(t · ( m 3 4 (n + 1)3)), where t is the number of iterations, and the experimental results of this paper demonstrate that t = 50 meets the expectation. Under the condition of universality, the number of iterations of each algorithm is much less than the number of samples. Similarly, Linex-TSVM has cubic time complexity in the number of samples.

Experimental Results and Discussions
In this section, we first set the experimental parameters in Section 4.1, and in sections Sections 4.2 and 4.3, we give in detail the experimental results of the model Linex-TSVM with or without noise. Finally, we present some results on the data set in Section 4.4 to prove the convergence of the objective function.

Evaluation Criteria
In order to evaluate the classification performance of our proposed truncated linear loss support vector machine more accurately, we compare it with other mature methods, including SVM, LSSVM, C-SVM, Linex-TSVM, and TBSVM. For these five support vector machines and Linex-TSVM, the iterative process is stopped when the difference between the target values of the two iterations is less than 0.001 and the number of iterations is more than 50. At the same time, in order to measure the performance of all algorithms, the traditional precision index (ACC) is used to measure the performance of these algorithms, which is defined as follows: Among them, TP and TN represent correct positive samples and negative samples, respectively. FN and FP represent wrong positive samples and negative samples, respectively. In order to make a more accurate comparison, we use the quadratic programming (QP) toolbox of matlab to solve the QP problem in related algorithms. The experimental environment consists of a Windows 10 machine and Intel i7 Processor (3.70 GHz) with 8 GB of RAM.

Parameters Selection
For the learning algorithm, its performance is very sensitive to the parameters involved, so it is necessary to record the parameters of each algorithm in detail and list them as follows.
SVM and LSSVM:the kernel parameter σ. C-SVM: the regularization parameter c, the kernel parameter σ.
The experimental parameters are selected by ten cross-validation methods, and the test accuracy is the average of 10 clusters of results in each dataset.

Description of the Datasets
To verify the effectiveness of Linex-TSVM, we conduct numerical simulations on different datasets, including seven benchmark datasets from the UCI machine learning repository and two artificial datasets. The datasets are described as follows: Artificia datasets: In the artificial dataset (a) and (b), there are 50 positive samples and 50 negative samples, represented by '+', ' ' and ' ', respectively, as shown in Figure 2. Because the outliers will have a certain impact on the classification performance, it is also the standard to measure the stability of the algorithm. Therefore, we introduce four outliers in the artificial dataset to evaluate its robustness, two of which belong to class +1 and two belong to class −1.
UCI datasets: Australian, Spect, Pima, German, Vote, CMC, Sonar, Spect and Large dataset(codrna). Details of the eight UCI datasets are given in Table 1. These UCI datasets are used to test the performance of our algorithms and related algorithms. We divide all the data sets into ten subsets, including nine training sets and one test set, that is, 10-fold cross-validation, so that the process is repeated ten times, and the average value of the final result is taken as the criterion to measure the performance of the model. At the same time, we normalize the eight participating data sets, which can avoid errors caused by different orders of magnitude and units, keeping the result within [0, 1].

Experimental Results on the Employed Datasets without Outliers
Eight UCI datasets are selected and the running results are compared with the other six algorithms to verify the better classification performance of the proposed algorithm.
All experimental results presented in Table 2 are based on optimal parameters. Here, "Time(s)" denotes the average runtime in seconds taken by each algorithm according to the optimal parameters, "ACC ± S" denotes the average classification accuracy plus or minus standard deviations.   Intuitively, it can be observed from Table 2 that the classification performance of the twin support vector machine based on capped linear loss function proposed in this paper is better than that of the other six models. Except for CMC data sets, Linex-TSVM has better results on other data sets. At the same time, we also observe that the computing time of this model is not dominant, which is because the model is more complex. The time of LSSVM algorithm for solving a system of linear equations is shorter, and compared with SVM, it shortens the time while retaining accuracy, which is in line with the relevant theory. It is worth mentioning that the result of Linex-SVM is still good, which shows that the introduction of linear loss function is meaningful.
Through the detailed analysis of the above experimental results, we can obtain an objective and reasonable conclusion: the use of capped linear loss function on the basis of TBSVM can improve the classification performance, and the introduction of L 1 -norm distance metric can also enhance the robustness of the model; thus, our model is an effective supervision algorithm without the influence of outliers.

Experimental Results on Artificial Dataset with Outliers
It is well known that outliers tend to have a certain impact on classification performance, which is also a measure of the stability of the algorithm. Therefore, we introduce outliers in artificial datasets (a) and (b), respectively, and Figure 2 is displayed visually. In order to further verify the robustness of the capped linear loss function, we show the classification accuracy of this algorithm on artificial data sets (a) and (b) in Figure 3 From Figure 3, we observe that the proposed Linex-TSVM has higher accuracy when considering outliers; on artificial datasets (a) and (b), the classification accuracy of Linex-TSVM is 68.06% and 91.97%, respectively, which is better than the other five algorithms, can deal with outliers well, and has stronger robustness and better classification ability.
In summary, the capped L 1 -norm is robust to different types of outliers in the literature [21][22][23][24][25]. It can overcome the residual error of outliers in the experiment, and can help the model to eliminate the influence of outliers. In particular, the truncated linear loss function in this model can increase the punishment for outliers. In a word, Linex-TSVM can effectively improve the robustness of TBSVM.

Experimental Results on UCI Dataset with Outliers
In order to verify that this model is also suitable for large-scale data with outliers, we add 10% and 25% noises to the eight UCI data sets, respectively. The reason why the algorithm is introduced into the model is that in practical application, there are various kinds of data and there must be different degrees of noise. In order to verify that the model is suitable for data sets of different fields and different sizes to a certain extent, it is necessary to introduce different noise to compare the models. At the same time, we find that after adding noise, the accuracy will fluctuate to a certain extent, but the overall trend shows a slow decline, which shows that when the noise is relatively large, it will have a certain impact on the model, but the model in this paper is more stable. The results, such as Tables 3 and 4, show that after the introduction of outliers, the seven algorithms all have varying degrees of accuracy fluctuations, but show a downward trend as a whole, and the classification accuracy of Linex-TSVM is almost better than other algorithms. This shows that the model proposed in this paper has stronger robustness.
Specifically, in Tables 3 and 4, Linex-TSVM has the best accuracy in seven of the eight data sets, while the least squares support vector machine model has the shortest computing time under different noises. It is worth noting that compared with SVM, LSSVM, NPSVM, C-SVM, Linex-SVM, due to the use of capped linear loss function, the penalty for outliers is increased, so it has better classification accuracy. Linex-TSVM is better than Linex-SVM and TBSVM.  Table 4. Experimental results on UCI datasets with 25% Gaussian noise. Furthermore, in order to more comprehensively analyze the robustness of the algorithm under different noises, we have carried out more experiments on Australian, Spect, Pima, German, Vote, CMC, Sonar, Codrna and Spect, and we use different noises to test the performance of the six algorithms. For an original dataset X, we changed it with X + λX, where λ = q X F X F and q is a noise factor. Here,X is the noise matrix whose elements are i.i.d. standard Gaussian variables. The value is q ∈ {0.1, 0.2, 0.3, 0.4}. Through Figure 4, we can observe that under different noise factors, Linex-TSVM shows better classification accuracy and stability, while the other six models are relatively more volatile.

Datasets ACC ± S (%) ACC ± S (%) ACC ± S (%) ACC ± S (%) ACC ± S (%) ACC ± S (%) ACC ± S (%) Times (s) Times (s) Times (s) Times (s) Times (s) Times (s) Times (s)
Next, we introduce the box line diagram to verify that the model is better from another point of view. In Figure 5, we select six datasets to analyze the height of the box reflects the fluctuation of the data to a certain extent, that is, it represents the fluctuation of classification accuracy. The upper and lower edges represent the maximum and minimum values of the group of data, and the points outside the box can be understood as "outliers" in the data, so we can directly observe that the classification accuracy of Linex-TSVM is higher than that of other models.
To sum up, the capped linear loss function twin support vector machine proposed in this paper is superior to the other six algorithms in terms of classification accuracy and robustness, indicating that Linex-TSVM is a robust learning algorithm for large-scale data classification with noise.

Analysis for the Convergence
In this section, we show the convergence curve of the proposed algorithm on four datasets to directly verify that the convergence speed of the proposed algorithm can achieve the desired speed. The result is Figure 6, where the horizontal axis represents the number of iterations and the vertical axis represents the value of the objective function. We set: when the difference between the target values of two consecutive iterations is less than 0.001 and the number of iterations is less than 50, the iterative process stops.
The result of Figure 6 shows that the value of the objective function of Linex-TSVM decreases monotonously with the increase in the number of iterations, and the algorithm can converge quickly in about 5 iterations, that is, it converges within a limited number of iterations, and we obtain satisfactory results, which is consistent with the previous theoretical analysis.

Statistical Analysis
In this section, the statistical analysis method-Friedman test is used to compare the differences among the six algorithms involved. In this paper, the Friedman test is a statistical test of the homogeneity of multiple (related) samples, which makes full use of all the information in the original data and has many advantages. It is worth noting that the zero hypothesis means that all algorithms have the same performance. When the zero hypothesis is rejected, we can perform the post-processing test of the Nemeny test [26]. Next, the average ranking and accuracy of the six algorithms on seven data sets are shown in Table 5.
Next, we take eight UCI datasets with 10% Gaussian noise as examples to compare the six algorithms. The formula for Friedman statistical variables is as follows: where k is the number of algorithms and N is the number of UCI datasets. In our paper, k = 7, N = 8. R i represents the average ranking of the i algorithm on the seven UCI datasets. In addition, according to the χ 2 F distribution with k − 1 degrees of freedom, we can obtain: where F F ((k − 1), (k − 1)(N − 1)) obeys the F-distribution, and its degree of freedom is (k − 1) and (k − 1)(N − 1). In this paper, we choose α = 0.05 and we can get F α (6, 42) = 2.34. Obviously, F F > F α , we reject the zero hypothesis. Intuitively, from the Table 5, ee observe that Linex-TSVM has better classification performance, which means that our algorithm is more effective.
Next, through the Nemenyipost-hoctest, we can further compare the errors of the six algorithms in this paper. If the average rank difference between each other is greater than the critical value, the results demonstrate that the performance of the two algorithms is different. By dividing the Studentized range statistic by √ 2, we can obtain q α = 2.95. Therefore, we calculate the critical difference (CD) by the following formulation: Based on Figure 7, the performance of Linex-TSVM is significantly better than SVM, LSSVM, C-SVM, Linex-SVM and TBSVM, but the different between Linex-SVM and TBSVM is not obvious, because the different is smaller than the calculated CD value. Through the above analysis, the Linex-TSVM proposed in this paper has better performance.

Conclusions
The Twin Support vector machine classification has become a research hotspot. Twin support vector machine models based on different loss functions have been proposed, such as TPMSVM, TWSVM, SG-TSVM and so on. It is urgent to propose a loss function with better performance under the framework of support vector machine. The summary of this paper is as follows: Firstly, this paper proposes capped linear loss function and applies it to twin support vector machine, and proposes a new robust classification model, which is called truncated linear loss function twin support vector machine. Compared with the linear loss support vector machine model proposed by Ma et al. [8], it has better classification performance.
Secondly, we give an efficient iterative algorithm to solve Linex-TSVM. Unlike SVM, which needs to solve a large QP problem, this algorithm needs to solve a pair of small QP problems. Finally, we strictly analyze the computational complexity of the algorithm; it is verified that Linex-SVM satisfies the Bayesian rule. Experimental results on multiple data sets demonstrate that our algorithm Linex-TSVM is more feasible and robust in dealing with large-scale datasets with outliers than other models, and intuitively show the convergence of the algorithm. In particular, compared with SVM, LSSVM, C-SVM, NPSVM, Linex-SVM and TBSVM,the average accuracy of Linex-TSVM is higher than that in the absence of noise. The average accuracy of the model in this paper is higher than that of 4.36%, 4.29%, 2.53%, 2.33%, 1.91% and 0.77%, respectively. Linex-TSVM is more robust and stable for outliers.
The focus of future work is that we should still focus on finding better models to improve different data classification results, shorten the computing time while ensuring accuracy, and extend the model of this paper to other work, such as multi-classification problems. In future work, we can further consider applying different models to practical hot issues, such as face recognition, fingerprint recognition, UAV scheduling and so on. Of course, how to develop a better new algorithm for our Linex-TSVM is also very important.


How do Cross-View and Cross-Modal Alignment Affect Representations in Contrastive Learning?

Various state-of-the-art self-supervised visual representation learning approaches take advantage of data from multiple sensors by aligning the feature representations across views and/or modalities. In this work, we investigate how aligning representations affects the visual features obtained from cross-view and cross-modal contrastive learning on images and point clouds. On five real-world datasets and on five tasks, we train and evaluate 108 models based on four pretraining variations. We find that cross-modal representation alignment discards complementary visual information, such as color and texture, and instead emphasizes redundant depth cues. The depth cues obtained from pretraining improve downstream depth prediction performance. Also overall, cross-modal alignment leads to more robust encoders than pre-training by cross-view alignment, especially on depth prediction, instance segmentation, and object detection.

Introduction
Pretraining of neural networks has been an established tool in computer vision for several years [2]. It allows to successfully finetune neural networks on new tasks with fewer iterations and less annotated data [3]. Commonly, models are initialized using weights pretrained for image classification on the ImageNet dataset [4], but recently, self-supervised approaches that do not rely on manual annotations have outperformed ImageNet pretraining [5]. : Redundant information is shared across modalities, while complementary information is exclusive to a modality. In this work, we show that cross-modal visual representation learning predominantly encodes redundant information of 2D and 3D data. *Images (b) and (c) were taken from [1].
In the realm of self-supervised representation learning, contrastive learning [6] has become a popular approach for visual representation learning. In contrastive learning, the model learns to distinguish different variations of the same instance (e.g. crops of a single image) from all other instances. These variations can be created artificially or by using natural data correspondences, such as images and text [7] or from multiple viewpoints [8,1].
A common objective is to enforce similarity between features across views or sensing modalities. This is called representation alignment [9]. While severe failure cases of such representation alignment have been discussed [9,10], the effects on the representation itself were not studied, as of yet. Figure 1 shows a conceptual illustration of the information available in 2D image data and 3D point clouds in the ScanNet dataset [11]. Some information, such as about depth and surfaces, is available in both modalities. Although this information may be more detailed and more accurate in one modality than in the other, both modalities can express such properties to a certain degree. In the context of sensor fusion, this is typically called redundant information. Other information is exclusive to a modality, which is called complementary information. 3D point clouds, for example, are generally color-and textureless.
Intuitively, a representation which discards complementary information is less expressive than one that includes redundant and complementary information. On the one hand, discarding texture and color information, for example, leads to a less complete visual representation. On the other hand, ImageNet pretrained models were found to be texture-biased and by increasing their shape-bias the performance on tasks such as object detection could be improved [12]. So what is the influence of complementary and redundant information on the visual representation quality?
In this work, we study how complementary and redundant information affect visual representation learning when exploiting cross-view and cross-modal representation alignment, and how this relates to the performance of a finetuned model on a transfer learning downstream task. For this purpose, we use Pri3D [1], a method that uses 3D information of a scene to enable cross-view and crossmodal representation alignment for visual representations learning.

Related work
Self-supervised representation learning has recently surpassed supervised pretraining on ImageNet [5]. Various approaches have been explored to learn a global feature vector per image, such as contrastive learning [5,6] and methods that do not require negative samples during training [13,14]. Since many computer vision tasks require per-pixel features, several works focused on learning dense representations [15,16]. Inspired by this success for visual representations, contrastive learning has also been applied to 3D point cloud data [17,18,19].
Several approaches have explored cross-modal and cross-view visual representation learning. While some propose a single model [20] for multiple modalities, we are interested in training a vision-only model using crossmodal and cross-view input. To this end, some have matched images and natural language to improve the learned visual representation [7,21], whereas others use 3D signals [22,23,1], or match representations of different views of a scene [8,1].
While cross-modal feature spaces are a common technique [24,25,26,1,27,19], they can introduce several caveats. Especially when dealing with partially incomplete or corrupted data, representation alignment may hinder effective learning for multi-view clustering [9]. In domain adaptation, avoiding representation alignment across modalities has also proven to be beneficial to prevent discarding complementary sensor information [10]. In representation learning, cross-modal training can even lead to an emphasis on a single strong modality and potentially harm the overall performance [28].
Our goal is to understand the effects of cross-view and cross-modal representation alignment on contrastive learning in more detail. Specifically, we do not consider corrupted or incomplete sensor data, but we investigate how redundant and complementary information influence the learned representations, and whether similar effects as observed for shape-biased vs texture-biased networks [12] can be observed. We base our empirical study on Pri3D [1] as it uses both cross-view and cross-modal representation alignment for contrastive learning, as well as their combination. As our main contributions, we: 1. assess how cross-view and cross-modal representation alignment affect the complementary and redundant information encoded in the learned visual perpixel representations, 2. evaluate the transfer learning performance in different settings on various tasks and datasets to investigate the robustness of cross-view and cross-modal alignment.
2D images and 3D point clouds have low-level redundant and complementary features, as illustrated in Figure 1. Therefore, these modalities lend themselves to study cross-view and cross-modal representation alignment. Our analysis of alignment in representation learning is based on Pri3D [1]. Pri3D uses 3D information for 2D visual representation learning. It employs a selfsupervised contrastive learning approach that does not require any human annotation, but only RGB images and registered point clouds that can be obtained, for example, from an RGB-D dataset. This section summarizes the two contrastive losses of Pri3D and discusses how the feature spaces of the losses can be separated.

Pri3D: contrastive losses
Pri3D finds pairs of pixels and elements of a regular grid in 3D space, so-called voxels, for contrastive learning. Pixels and voxels are matched by their distance in 3D space to define two losses. One loss requires pairs of pixels across views, whereas the other loss is based on pairs of pixels and 3D points across modalities. Since Pri3D matches pixels and voxels based on their 3D positions, it is relatively robust with respect to incomplete sensor data.
Cross-view contrastive loss (VIEW) This contrastive loss matches pixels across different views of the same scene. It requires two RGB-D images from the same scene and the corresponding relative camera poses and calibration. Once two pixels from two different views A and B are within a 2 cm distance, they are considered a positive pair in the sense of contrastive learning [6]. Only pixels that are part of a positive pair are used in this loss, as the negative pairs are also constructed from these pixels. To form the negative pairs, each pixel a of view A of a positive pair (a, b) is paired with all pixels k of view B which are part of a positive pair but not k = b. For each image x, an encoder-decoder network f predicts a set feature vectors f (x), and f a denotes the L2normalized feature vector of pixel a. Using the set of positive pairs M , Pri3D employs a PointInfoNCE loss [18] where τ is a temperature hyperparameter. This cross-view loss is called the VIEW loss, following the convention of Pri3D. Compared to other visual representation learning approaches, VIEW does not rely on strong augmentations that may corrupt color information [6].
Cross-modal contrastive loss (GEO) Unlike the VIEW loss, the pairs for the GEO loss do not consist of two pixels from different views, but instead of a pixel and a voxel. The positive pairs are again pixels and voxels within 2 cm distance in 3D space. The negative pairs are all other non-matching pixels and voxels pairs, similar to the VIEW loss.
The voxel is associated with a feature vector obtained from a dense 3D feature encoder. This dense 3D feature encoder is jointly learned with the dense 2D feature encoder. The loss function (Eq. (1)) remains the same with f a and f b now being feature vectors from the 2D and 3D feature encoders, respectively. Thus, this crossmodal loss enforces the features to be similar across the two modalities and is called the GEO loss, following the convention of Pri3D.

Pri3D: representation space separation
In Pri3D [1], the GEO and the VIEW loss use the same visual feature vector for a single pixel. Thus, the combination VIEW+GEO enforces mutual alignment of cross-view and cross-modal representations. Interestingly, in the implementation published by the original Pri3D authors [29], the feature spaces of both losses are separated by a linear layer preceding the GEO loss (see Figure 2). We hypothesize that the original purpose of this layer was merely to match the feature dimensions of the 2D and 3D backbone (e.g. for ResNet50 2D backbone this layer projects 128 to 96 channels). Yet, this separation of feature spaces relaxes the alignment of the cross-view with the cross-modal feature representation. The feature vector of a pixel in the GEO loss is now computed by a linear function on the feature vector of the same pixel in the VIEW loss, thus the two feature vectors are not the same anymore. The cross-view and the cross-modal representations are not directly aligned. Since the effect of this linear layer was not described in the literature, we include both variants in our experiments. In the following, we will distinguish this variation by adding (lin) to models that include the linear layer that separates the feature representations. These and other differences to the original Pri3D paper are described in more detail in the supplementary material.

Experiments
In our experiments, we examine how cross-view and cross-modal representation alignment in Pri3D influence the encoded complementary and redundant information and how possible differences in the representations affect downstream transfer learning performance.

Setup
The experiments consist of two main steps: We first pretrain models based on the variations of Pri3D (see Section 3). Afterward, the pretrained models are used to initialize training on downstream tasks, where we distinguish between a frozen (Section 4.2), a half-frozen (Section 4.3), and a full finetuning (Section 4.4) setting.

Pretraining
Our implementation is mainly based on the published code of Pri3D, and thus, we follow the same pretraining protocol as presented in the paper [1] and give a coarse outline here. We always use a UNet-style ResNet50 2D backbone and a UNet-style sparse convolutional 3D backbone. As in [1], the 2D backbone is initialized using supervised ImageNet pretraining before performing selfsupervised pretraining on the ScanNet dataset [11]. The ScanNet dataset is a collection of RGB-D sequences of indoor scenes, captured with a Kinect-like setup. On this dataset, the model is trained for 5 epochs using stochastic gradient descent with a learning rate of 0.1 with polynomial decay of 0.9 and the batch size is 64, unless explicitly mentioned otherwise. This corresponds to approximately 60k iterations and 4 days of training time on 8 Nvidia V100 GPUs for pretraining a single model. The temperature parameter in the losses (Eq. (1)) is set to 0.4.

Per-pixel downstream tasks
In Sections 4.2 to 4.4 the per-pixel representations are evaluated on depth prediction, image reconstruction, and semantic segmentation while parts of the pretrained network are frozen. To decode the information from features extracted by the frozen pretrained network, we append a non-linear per-pixel MLP (see Figure 2c). This MLP is implemented as a sequence of 1x1 convolutions: (c = 3 for image reconstruction, c = 1 for depth estimation, and c = #classes for semantic segmentation). The MLP is followed by a bilinear fixed interpolation that upscales the output from 120 × 160 to 240 × 320, which is analogous to the semantic segmentation downstream experiments of Pri3D [1] with the UNet architecture. Note that we discard the last convolutional layer from the pretrained model, which, during pretraining, linearly projects the features to the space in which the contrastive loss operates. It can be regarded as the head network which aims to solve the contrastive task.
For image reconstruction and depth prediction, we choose an L2 loss directly on the RGB input pixel values and depth ground truth values, respectively. For semantic segmentation, we use the common cross-entropy loss to predict the semantic classes of each pixel. Other than that, the same training protocol as for the semantic segmentation task in [1] is applied. The mean Intersectionover-Union (mIoU) is the metric for the semantic segmentation quality. The datasets used for depth prediction and image reconstruction are: • • Cityscapes [32]: A dataset of 5000 semantically annotated frames of urban street scenes in 50 different cities.

Object-centered downstream tasks
To perform object detection and instance segmentation, the encoders of the pretrained models are used to initialize a Mask RCNN model [33] of the Detectron2 library [34] in Section 4.5. Due to the downstream architecture, the decoders are discarded. In addition to ScanNet25kframes and NYUv2, the models are evaluated on the 2017 version of the COCO dataset [35] that contains more than 118k training and 5000 validation images. The Average Precision (AP) metric is used on all datasets.

Frozen downstream tasks
With the frozen downstream tasks, where we keep all weights of the pretrained network frozen, we investigate how well the pretrained models capture color, depth, or semantic information by predicting this information from the learned per-pixel representations. Using these frozen downstream tasks, we show how the different alignment strategies in Pri3D influence the learned representations. For semantic segmentation, this frozen setup is similar to the linear evaluation protocol commonly used to evaluate the quality of global image features in visual representation learning [6]. In this linear evaluation protocol, the performance of a linear classifier on the global features is often regarded as a proxy metric for the representation quality. In our setup, we evaluate whether a non-linear MLP can provide a proxy metric for the representation quality.
The first four rows of Table 1 show the best performance on the validation data during the training process for each model variation and frozen downstream task. Compared to the cross-view model (VIEW), all other models perform worse on frozen image reconstruction and semantic segmentation. In contrast, the models that include the cross-modal GEO loss perform better than the VIEW on ScanNet depth prediction, while on NYUv2 this general trend is not visible. The VIEW+GEO (lin) model outperforms the VIEW+GEO model on all three frozen downstream tasks by more than 10%. Figures 3 and 4 show the qualitative reconstruction and depth prediction results. In both cases, the ranking of the models on ScanNet is reflected in the visual reconstruction quality. The VIEW model achieves the best visual reconstruction, followed by the VIEW+GEO (lin),  Table 1: Validation performance on the three tasks and four datasets. Rows 1-4 show the frozen downstream setting where the pretrained weights are fixed, in rows 5-8 the encoder of the UNet-style architecture is fixed, and in the last four rows, the entire models are finetuned. To have a consistent notion that a greater value means better performance, the negative L2-Loss is shown. Blue color indicates relative improvement with respect to the cross-view model (VIEW).
VIEW+GEO and GEO models. It is notable that the results differ especially on flat texture-rich surfaces, for example in the first row where the GEO model does recover the wallpaper. All model variations discard most of the color information. The most detailed and smoothest depth estimation is obtained by the VIEW+GEO (lin) model. The depth gradient along surfaces appears smooth whereas the depth estimation based on VIEW+GEO and VIEW is speckled on flat surfaces.
In conclusion, the cross-view VIEW loss preserves more texture information while the cross-modal GEO loss leads to a better depth representation. This observation is in line with the ideas of complementary and redundant information discussed in Figure 1 mation. Notably, the depth prediction result is even better than for the GEO model, suggesting that even with respect to the redundant information, this separation is beneficial. The semantic segmentation performance differs strongly between the model variations and benefits from the crossview loss and the linear layer in VIEW+GEO (lin) that lifts the direct alignment.

Half-frozen downstream tasks
By freezing only the encoder part of the UNet-style models, the following experiments provide insight to which part of architecture discards the texture information. The experimental setup, architecture, and datasets remain the same as for the frozen downstream tasks in Section 4.2, except that now also the decoder is finetuned together with the MLP and only the encoder is fixed during finetuning. The GEO model performs best across all tasks and datasets as seen in rows 5-8 of Table 1. The model excels on depth prediction, and interestingly, also outperforms the VIEW model on image reconstruction. The combined models outperform VIEW on depth prediction, but the other tasks show mixed results. The linear layer (lin) improves the VIEW+GEO performance slightly.
Overall, the results are in stark contrast to the frozen downstream tasks. Given that the GEO model outperforms the VIEW model, it seems that the decoder discards the texture information in the frozen downstream tasks, and recovering the texture is possible by finetuning. At the same time, the encoder of the GEO model extracts very robust features across tasks and datasets.

Full finetuning downstream tasks
To assess the practical value and generality of a visual representation, the models are now fully finetuned and evaluated on the downstream tasks. In contrast to the frozen downstream tasks, all weights in the model are finetuned during the downstream task training. 1 As the full model is finetuned, the per-pixel MLP is not needed anymore and is omitted. Rows 9-12 in Table 1 show the full finetuning downstream performance. Models that were trained including the GEO loss outperform the VIEW model on depth prediction. Again, GEO is the best model for image reconstruction. On semantic segmentation, VIEW performs best on Cityscapes and KITTI, but not on the other two datasets.
Also in this full finetuning setting, cross-modal alignment improves depth prediction performance. For semantic segmentation, the results are generally mixed, but it is notable that VIEW performs well on the two outdoor datasets. This may indicate that the cross-modal models are biased towards spatial layouts of indoor scenes. Adding the feature space separation (lin) to VIEW+GEO does not have a positive effect, but rather tends to decrease the performance.

Instance and object segmentation
As discussed in [12], texture-biased networks are inferior to shape-biased networks for object detection. In order to test whether this also holds for texture-biased net-works compared to depth-biased networks, the pretrained encoders are finetuned for object detection and instance segmentation. Table 2 shows that the cross-modal GEO model outperforms the VIEW model on 5 out of 6 task and dataset combinations. The combined models VIEW+GEO and VIEW+GEO (lin) models show mixed results, perform well on ScanNet, but not on COCO. On NYUv2, their difference is most pronounced where the linear feature separation (lin) leads to the worst performance among the four model variations while omitting it results in the best performance.
Combining the losses in the VIEW+GEO and VIEW+GEO (lin) models seems to be beneficial within the pretraining dataset, but not when shifting domains. Overall, although the performance differences are small, the GEO model appears to be more robust. This supports the idea that texture-biased networks are not as robust for object-centered tasks as the depth-biased GEO network.

Discussion
The comparison on the frozen downstream tasks reveals that cross-view and cross-modal representation alignment influence the complementary and redundant information encoded in the learned representations. While the VIEW model preserves the texture and the GEO model preserves the depth, the combination VIEW+GEO does not result in the different low-level features complementing each other, but instead a fully shared feature space is obtained where complementary information is lost and redundant details are less accentuated. VIEW+GEO (lin) improves the combined model on all three frozen downstream tasks and raises the question of whether this means we have found a generally better representation. The performance on the half-frozen and full finetuning downstream tasks contradict this apparent conclusion and we even find that the GEO model performs most robustly across tasks and datasets. This shows that reducing texture-bias in networks increases robustness, similar to findings in [12].
On semantic segmentation, the frozen downstream task shows a distinct ranking that is persistent across datasets. These distinct performance differences were not observed once the decoder is finetuned as well. A possible explanation could be that the texture-bias is to a certain degree useful but also easy to recover and thus not important to learn during pretraining. So although the strong differences on the frozen downstream tasks reveal that the diverse representations either incorporate or discard com-plementary information, the performance on the frozen tasks does not correlate with the finetuning downstream performance.
The comparison of VIEW+GEO with VIEW and GEO indicates different behavior on data within the same domain and across domains. The VIEW+GEO model excels especially in object detection, instance segmentation, and semantic segmentation on the ScanNet dataset. A similar effect of overfitting to the pretraining dataset is also reflected in the learning rate variations shown in the supplementary material. In a broader context, this could mean that aligning cross-modal and cross-view representations may harm generalization across datasets but could prove especially useful when exploiting unlabelled data within the same domain for better performance on a small annotated subset. Still, further experiments are needed to verify this hypothesis.
Our empirical study comes with certain limitations. Although our results are obtained on various datasets and tasks, the pretraining and finetuning results are always subject to stochastic effects in the training processes. Further, we only focused on the most obvious modalityspecific information such as color and depth. The image reconstruction and depth prediction tasks only test some characteristics of the learned representations while other characteristics may be more indicative with respect to downstream finetuning performance. Still, our results show that the different pretraining strategies yield representations that encode different information.
Aligning feature representations across views and across modalities is a common approach in self-supervised learning. Yet, the effects on the learned visual representations are often not well understood. We showed quantitatively that, in contrast to cross-view representation alignment, cross-modal representation alignment can lead to discarding complementary information of the individual modalities. In the context of cross-modal learning on images and point clouds, texture is considered complementary information of the visual data and depth is redundant information. Pretraining by cross-modal alignment was especially useful for tasks that require a notion of the spatial layout, such as depth prediction, and also instance segmentation and object detection. This effect is similar to the observations of previous work that shape-biased networks are more robust than texture-biased networks. Thus, pretraining with emphasis on the redundant information achieved the most robust performance when finetuning the visual backbone networks on various downstream tasks and datasets.
Merging complementary information is a fundamental goal of sensor fusion and discarding that information may harm the overall performance on such a task. While our results have indicated that visual representations become more robust by reducing the texture-bias through crossmodal alignment, future work should investigate whether these results still hold for self-supervised approaches that fuse different sensing modalities.

Relation to results presented in Pri3D
To the best of our knowledge, all models in Pri3D [1] were pretrained with a depth loss in addition to the VIEW and GEO loss. This proxy depth loss follows the formulation presented in [2] and details are found in the official Pri3D implementation [3]. Note that this loss is also preceded by a linear per pixel layer that reduces the backbone output channels to a single channel (see Figure 1). We did not include this proxy loss, because our goal was to focus on the effects of cross-view and cross-modal representation alignment. Table 1 show the results of the Pri3D variations once the proxy depth loss is used. The relative performance change is given with respect to the corresponding model without the depth loss, which is not listed explicitly. While the depth loss does have positive effects on semantic segmentation of ScanNet and NYUv2, it is not beneficial on the object detection and instance segmentation tasks on the same datasets. On the other datasets and tasks it leads to mixed results.
Further, from what we understand, some models in [1] were pretrained with a learning rate of 0.1 and others with 0.01. Table 2 shows the effect of the learning rate change. Within the ScanNet dataset, the higer learning rate outperforms the lower learning rate, and vice versa on the other datasets. The pretraining learning rate thus seems to be a crucial factor that should be taken into account when evaluating models within or across datasets.  Performance change in %


Balanced Encoding of Near-Zero Correlation for an AES Implementation

Power consumption of a circuit can be exploited to recover the secret key of a cryptographic algorithm. This technique is known as power analysis, one of the well-known techniques of side-channel analysis. Many software countermeasures against power analysis present a time-space trade-off. Masking and shuffling come at cost of the execution time and the extreme use of run-time random number generators. Internally encoded implementations of block ciphers, on the other hand, require large memory space to store a set of lookup tables. While the internal encoding is widely used in white-box cryptography, it has a serious drawback. It cannot protect the secret key against power analysis. In this paper, we propose a secure internal encoding method of an AES implementation. Provided that the five inner rounds are left unprotected because these are not subject to power analysis, the lookup tables are approximately 232KB in size and the number of operation including XORs and table lookups are about 1,000 in total. This is about half the table size required by the white-box AES implementation, which is vulnerable to power analysis, and is about three times the amount of operations required by the straightforward AES implementation.

Introduction
In the gray-box model, software cryptographic implementations executed in untrusted environments can be attacked by exploiting side-channel information such as timing or power consumption. Such information is highly likely to expose a secret key, so an attacker can recover it from non-protected implementations without the effort of reverse engineering. Among many leakage sources of sidechannel information, the correlation to key-dependent intermediate values has been exploited by various attacks. For example, power analysis including Differential Power Analysis (DPA) [13] and Correlation Power Analysis (CPA) [8] analyzes the correlation between the power consumption of the target computation and the corresponding hypothetical values. The attacker queries the software implementation of a cryptographic primitive with arbitrary inputs and collects power traces through physical interaction with an oscilloscope. For every pair of the input and the subkey candidate to the target cryptographic function such as SubBytes, the attacker computes the hypothetical value. The correct candidate produces the correct hypothetical values which are strongly correlated to a particular point in the power traces because the power consumption is proportional (or inversely proportional) to the data processed in the circuit. Here, DPA divides the power traces into sets based on the hypothetical values and gets the average traces of each set. If the subkey candidate is correct, a differential trace then shows a noticeable peak at the points related to the target function. In the case of CPA, the subkey is simply guessed by calculating a correlation between hypotheses and each point in the traces.
The number of power traces required for successful power analysis depends primarily on the power model and electronic noise. A power model such as a bit model or a hamming weight model determines how to express the power consumption of the target function. On the other hand, electronic noise is partly generated in power measurement and is partly generated due to constant components such as leakage current and transistor switching [19]. Generally speaking, as the noise increases, the number of power traces required for key recovery increases. Recently, several studies [7,16,22] have defined another threat model of computational analysis, in which an attacker can access a source code or an executable of the target primitive. In this threat model, a computational trace can be collected by observing the computations in memory without electronic noise. Hence, the key-dependent intermediate values or the memory addresses pertaining to read and write access are clearly revealed.
Computational analysis was originally adapted by Differential Computation Analysis (DCA) [7], a non-invasive attack extracting the secret keys from a wide range of different white-box implementations [9,10] without having to perform a detailed reverse engineering of the target implementation. From the attacker's perspective, the noise-free computational traces have also contributed to DCAvariant attacks such as Zero difference enumeration [2], collision attacks, mutual information analysis [21], and bucketing attacks [27]. From the cryptographic engineer's perspective, on the other hand, the noise-free traces can be used to evaluate the protection of secret keys against power analysis with the reduced number of traces compared to classical power analysis and without an expensive oscilloscope.
The common software countermeasures reducing the problematic correlation are masking and operation shuffling. The basic idea of masking is to split every sensitive variable s into d + 1 shares s 0 , . . . s d such that s 0 • s 1 • . . . • s d = s, where a group operation • is the XOR ⊕ in most cases or is sometimes the modular addition. Here, any subset of less than d + 1 shares or leakage signals should be statistically independent of s. This is achieved by picking up the masks s 1 , . . . , s d uniformly at random and by setting the masked variable s 0 such that s 0 = s • s 1 • . . . • s d . Then d is called the masking order. Because the attack cost of higher-order DPA exploiting d + 1 leakages grows exponentially with the masking order [19], higher-order masking schemes can secure block-cipher implementations.
The disadvantage of higher-order masking is that it is not efficient when recomputing a new S-box S which blinds the input and the output with random masks. A second-order masked AES implementation takes more than 20 times the execution time compared to the first-order implementation [23]. Since the first-order masking can be broken by the second-order DPA with reasonable efforts, a practical approach for industrial practitioners is often to combine it with shuffling [12].
Shuffling randomizes the sequence of independent operations for each execution of encryption. This spreads the leakage point of a key-sensitive variable over t different points. Provided that the sequence is shuffled uniformly at random, then the signal-to-noise ratio of the instantaneous leakage on the sensitive variable is reduced by a factor of t. Shuffling is easy to implement and less costly than higher-order masking especially when applied to the S-box. However, the combination of first-order masking and shuffling is not sufficiently secure against advanced power analysis [25,26].
It is noteworthy that the higher-order DCA [5] is reminiscent of higher-order DPA attacks. This attack was developed to recover the secret key from the masked and shuffled implementation by using computational traces. In addition, an algebraic DCA attack [4] has been proposed to break the linear masking on the white-box implementation independently of the masking orders in the white-box setting. In order to resist both computational and algebraic attacks, a white-box masking scheme that combines linear and nonlinear components has been proposed [24]. However, this masking technique is a hardware-based countermeasure that is largely dependent on a run-time random number generator. In general, masking schemes are costly in terms of run time and often lead to the joint leakage. Although a masking technique can be customized into the precomputation tables of the white-box instances [15,16], it is also costly in terms of memory requirements.
In light of this, there is a clear need for a software-based and non-masking countermeasure against power analysis in the gray-box setting. By doing so, the software implementation of a block cipher in the low-cost device such as ID cards can effectively protect the secret key within limited resources. To achieve this goal, we revisit the internal encoding for the table-based AES implementation. The internal encoding was originally used in white-box cryptography to enhance the table diversity and ambiguity [9,10]. However, the high correlation that still remains in the encoded intermediate values is the main cause of the vulnerabilities of white-box cryptography to gray-box attacks [7,22]. This vulnerability has raised the need for balanced encoding methods.
In this paper, we primarily focus on finding the balanced encoding method. Above all, we customize an 8-bit linear transformation in such a way to eliminate the problematic correlation. Here we note that our linear transformation is designed to use not only nonsingular but also singular matrices. This improves on the table diversity and ambiguity. Because the linear transformation is unable to conceal zeros per se, the nonlinear transformation is partly used to hide zeros. When an AES algorithm is implemented by using our encoding method, the key can be protected from power analysis. The proposed AES implementation requires approximately 232KB of memory space for lookup tables and 1,000 operations including XORs and table lookups. Importantly, it is not dependent on masking techniques and run-time random sources in the device.
The rest of the paper is organized as follows: Section 2 explains the basic concepts of power analysis and the existing method of the internal encoding. In Section 3, we propose our encoding method. In Section 4, we introduce our AES implementation protected by the balanced encoding and analyze its performance and cost. Section 5 shows the experimental results on calculating the correlation between the lookup values and the hypothetical values. Section 6 summarizes this paper.

Preliminaries
In this section, we first introduce the well-known techniques of power analysis, which is still one of the most prevalent ways for extracting secret keys from IC cards. Using oscilloscopes in power analysis requires a large number of power traces because the key-dependent information in the trace is not clear due to the measurement noise. However, given the source code or executable of the target cipher, collecting computational traces from memory is more practical than collecting power traces. It is important to notice that if the key is not extracted from noise-free computational traces, it can be determined that the key is secure against power analysis. To demonstrate the security of the proposed AES implementation, we conduct experiments using computational traces in Section 5. Therefore, we explain methods used to measure correlation in the experiments. Lastly, we briefly demonstrate the key leakage caused by the problematic correlation in the existing method of internal encoding adapted to white-box cryptography.

Power Analysis
Power analysis is a non-invasive attack to extract the key from low-cost devices such as IC cards. In the gray-box model of power analysis, an attacker can select a plaintext and access the ciphertext. The attacker can also collect timing or power consumption information related to the encryption operation. However, it is not possible to access the internal resources of the computing environment to observe or manipulate memory. Power consumption of IC cards is proportional (or inversely proportional) to the Hamming weight (HW) of data processed in the circuit [19]. Suppose that an attacker knows a correct subkey of the AES algorithm. For a target operation like SubBytes, power consumption of a circuit is then strongly correlated to the attacker's hypothetical value at a point of power traces. The following explains two fundamental techniques of power analysis, Differential power analysis (DPA) and Correlation power analysis (CPA).
DPA is a statistical method for analyzing power consumption. A selection function D(b, C, k * ) is defined to compute a key-sensitive variable b, where C is a ciphertext and k * is a subkey candidate. If k * is a wrong key candidate, D will evaluate b correctly with a 1/2 probability. DPA records N power traces V 1..N [1.
.κ] consisting of κ points. Then the differential trace ∆ D [j], where j ∈ [1, κ], is generated by computing the difference between the average of traces for D(·) = 1 and D(·) = 0 as follows: , a sample point in the trace. That point indicates power consumption of computing b. For this reason, a correct subkey will result in a noticeable peak in the differential trace, but it is unlikely that the wrong key candidate will produce a spike.
CPA improves on DPA by taking advantage of leakage models such as the HW. For K different key candidates, let h n,k * be the hypothetical value for the power estimation, where n ∈ [1, N ], and k * [0, K). A correlation between hypothetical values and power traces can be obtained by the estimator r as follows [19]: where h * k and V [j] are the sample means of h * k and V [j], respectively. Like in the case of DPA, a correct subkey makes a noticeable spike in the correlation plot.
As mentioned previously, each point of a power trace is also affected by electronic noise of power measurement as well as constant components such as leakage currents and transistor switching. The noise has a significant impact on the number of power traces needed to recover the key. However, it is not necessary to collect power traces if the source code or execution binary is available. In this threat model, Differential computation analysis (DCA) [7] collects noise-free computational traces consisting of read-write data or memory addresses accessed by the software. Since the collected information has no noise, the computational traces make CPA successful with fewer traces. In order to collect computational traces during the encryption, dynamic binary instrumentation (DBI) tools including Pin [18] and Valgrind [20] can be adapted.
Walsh transform can also quantify a correlation using only simple XOR and addition if the intermediate values or computational traces can be collected [22]. To evaluate the security of software cryptographic implementations, the Walsh transform can be inserted in the source code to calculate the correlation without having to use DBI tools. By doing so, scanning every sample point of the traces is not necessary. Compared to Pearson correlation coefficients, the Walsh transform consists of lightweight operations and shows the correlation as a natural number. Definition 1. Let x = x 1 , . . ., x n , ω = ω 1 , . . ., ω n be elements of {0, 1} n and x·ω = x 1 ω 1 ⊕. . .⊕x n ω n . Let f (x) be a Boolean function of n variables. Then the Walsh transform of the function f (x) is a real valued function over {0, 1} n that can be defined as

High Correlation in the Existing Encoding Method
So far, the internal encoding consisting of linear and nonlinear transformations has been applied to white-box cryptographic implementations for block ciphers in order to obfuscate key-dependent intermediate values. Unfortunately, the current encoding method cannot hide the keys completely from power analysis [1,14]. First, the linear combinations of intermediate values are highly correlated with the intermediate values due to the key-dependent distribution. For example, suppose that an 8-bit linear transformation is applied to 3 · x, where x is the SubBytes output. Then the linear combination of the first to fifth bits of 3 · x is always correlated to the first bit of x. Second, the two 4-bit concatenated nonlinear transformations show a limited confusion effect on 8-bit values.
Let f i (·) denote the encoding on the MixColumns multiplication in the first round of a white-box implementation of an AES-128 algorithm (WB-AES) [9]. To be specific, the MixColumns multiplication is performed between the SubBytes output and the first column of MixColumn matrix. Given the SubBytes output x, f i∈[0,31] (x) is an encoded 32-bit value of MixColumns multiplication. Fig. 1 illustrates the Walsh transform with ω = 8. Although the correct subkey has W f i = 0 at 30 bits out of 32 bits, the 6th and the 7th bits of f (·) are highly correlated to the 4th LSB of x. Their Walsh transform scores are 128. In contrary, the average of |W f i | of the wrong key candidates was 13.07 (max = 52 and s.d = 9.44). This gives us that the subkey can be recovered by power analysis with an overwhelming probability.
Previously, the classical and customized masking techniques have been proposed to solve this problem of the internal encoding [5,15,16] masking is however expensive in terms of computational costs and is not secure against higher-order DPA attacks. On the other hand, the customized masking requires tens of megabytes for lookup tables, which cannot be stored in a low-cost device. To address this problem, we propose a non-masking encoding method that takes up less memory space for an AES-128 algorithm.

Proposed Encoding
Before going into depth on our balanced encoding, let's start by explaining the imbalances in the existing 8-bit linear transformation of a white-box AES implementation. For x ∈ GF(2 8 ), let S (x) denote the SubBytes output multiplied by ∈ {1, 2, 3}, the elements in the MixColumns matrix. Here, S (x, y) refers to the y-th bit of S (x), where y ∈ [1,8] (the MSB is the first bit). The following matrix S is defined as An asterisk often refers to either a row or a column. For example, S i, * refers to the i-th row, and S * ,j refers to the j-th column of S . If M i,j is an 8 × 8 binary invertible matrix, an 8-bit linear transformation with S is given by R = M ·S . Each row in R i, * is then computed by the XOR operations between the selected rows in S ; if M i,j = 1, S j, * is XORed to compute R i, * By Definition 2, for random integers i, i ∈ [1,8] and , ∈ [1,3], the balanced linear transformation must satisfy the Walsh transform as follows: In other words, this implies HW(R i, * ⊕ S i , * ) = 128. As pointed out in [14], the key-dependent distribution of S , however, leads to HW(R i, * ⊕ S i , * ) = 0, which results in the Walsh transform value 256, with an overwhelming probability. Table 1 lists V and W, the row index of S and the sets of the row indexes of S , respectively, producing the Walsh transform value of 256 for each pair of ( , ). The first row of the table means that if = , the Walsh transform value would be 256 only if the j-th row from S and S was selected, where j ∈ [1,8]. For ( , ) = (2, 1), for example, suppose that R 2 contains a row computed by a linear combination of the 7-and 8-th rows of S 2 . This row is then identical to the 8th bit of S 1 . In other words, this linear transformation is unable to protect R 2 from an attacker calculating a correlation using the 8th bit of S 1 .
Considering AddRoundKey performed before SubBytes, a subkey k will be added to the input x of S(·). Here, it is easy to know that S(x ⊕ k) can by expressed by a permutation of columns in S and S . Thus, the same row indexes listed in Table 1 will lead to the same results even after k is added to x.

Basic Idea
Overall, our encoding protects a byte using a customized 8-bit linear transformation and a simple nibble encoding. To be balanced, the linear transformation must generate a matrix M that does not contain the row indexes listed in Table 1. Previously, the linear transformation has adapted only invertible matrices to guarantee its inverse transformation. However, using only binary invertible matrices, after excluding those row indexes, reduces the table diversity. To solve this problem, our linear transformation is designed to adapt singular matrices as well as nonsingular ones. It is noteworthy that this proposed linear transformation is capable of decoding, i.e., inverse transformation, even though both singular and nonsingular matrices are utilized. The following explains the proposed 8-bit linear transformation consisting of 4-bit transformations. In addition, the 4-bit nonlinear transformations, often called the nibble encoding, are partly used to hide the value of 0.
Notation. For 8-bit binary vectors X, Y, Z, the superscripts H and L represent their upper 4 bits and lower 4 bits, respectively. Thus, X = X H ||X L . The encoding is denoted by E, consisting of the linear and nonlinear transformations, denoted by L and N , respectively. By abuse of notation, N H denotes the nibble encoding for the upper 4 bits whereas N L denotes for the lower 4 bits of the input. The subscripts to N are used to indicate different nibble encodings. The decoding is denoted by D. Let denote two sets of 4 × 4 binary matrices by F  and G, which are chosen under the certain conditions explained in the following. f $ ← − F means a random sampling from F. Idx (v) is defined to be a function:

Balanced Linear Transformation
Suppose f and g are the elements randomly chosen from F and G, respectively. For an 8-bit vector X = X H ||X L , the proposed linear transformation Z = L(X, f, g) is defined as follows: where · implies multiplication. This can be represented by M · X, using an 8×8 matrix M defined as follows: During the computation of L, if M * ,i =1, the i-th row of X is to be XORed. The balance can be achieved by using binary vectors f i, * that are not listed in Table 1, where i ∈ [1,4]. Let B F i denote the blacklist, i.e., the set of binary vectors that must not appear to the i-th row of f ∈ F. There exist 27,000 Table 1. Our exhaustive search found that a total of 1,098,661,500 (> 2 30 ) pairs of (g, f ) satisfies In other words, our linear transformation guarantees the table diversity consisting of more than 2 30 pairs of (g, f ) producing the Walsh transform value of 0. For each f , the average numbers of row vectors at g 1, * , g 2, * , g 3, * , and g 4, * are approximately 14, 13.6, 14.2, and 14.6, respectively.
For four 8-bit values X 1 , X 2 , X 3 , and X 4 , let Y and Z stand for the followings: Then, the inverse of the linear transformation is accomplished by Y = L −1 (Z, f, g): Then, it is easy to see that S can be considered a permutation of columns in S . Without loss of generality, R = M · S. If Equation 1 is true, then It also implies that HW(R i, * ⊕ S i , * ) = 128. This gives us that the protection of L on MixColumns does not produce intermediate values which are highly correlated to the correct hypothetical value of it.

Nibble Encoding for Hiding Zeros
Because of the balance provided by L, all intermediate values have no problematic correlation to the correct hypothetical values before applying nibble encodings. For this reason, the use of nibble encoding is restricted to hide the value of 0, which cannot be hidden by multiplication. Simply speaking, each nibble encoding swaps the value 0 with e ∈ [0, 0xF ], whereas the other values remains the same. The focus is on finding a candidate e, keeping the balance in the encoding. Fig. 2 shows graphical representation of two nibble encodings applied to R . In the upper and lower 4 bits, every four-bit chunk from 0 to 0xF appears exactly 16 times because of the balance by L. Let denote two candidates to be swapped in the upper and the lower four bits by e H and e L , respectively. In other words, the upper (resp. the lower) nibble encoding performs 16 swaps between 0 and e H (resp. e L ). Let J H 0 be a set of column indices with the upper four bits of R equal to zero, and let J H e be a set of column indices with the upper four bits equal to e as follows: For the upper 4-bit nibble encoding N H , a candidate e H must satisfy the following conditions to provide the first-order balanced encoding: Here, it is worthy noting that the balance must be investigated for all ∈ {1,2,3} since a single matrix M will be used to protect S 1 , S 2 , and S 3 (see Section 4). Similarly, we define J L 0 ={j|R 5,j ||R 6,j ||R 7,j ||R 8,j = 0} J L e ={j |R 5,j ||R 6,j ||R 7,j ||R 8,j = e} For the lower 4-bit nibble encoding N L , a candidate e L must satisfy the following conditions: A more graphical way of representing the implication is illustrated in Fig. 3. 0 can be swapped with e H if the HW of every column in J H 0 and J H e are the same for each row of S . Also, e L can be found in the same manner using column indices belonging to J L 0 and J L e . By using 100 different pairs of (f, g), R ∈{1,2,3} was constructed and was then encoded by a pair of nibble encodings. We found that an average of 12

Protected AES-128
From now on, we describe a secure design of AES with a 128-bit key protected by our balanced encoding. Overall, this is inspired by a white-box cryptographic implementation of AES [9], which is mainly composed of a series of internally encoded lookup tables. Our focus is, however, on protecting against DPA-like attacks which take advantage of correlation to the key-dependent intermediate values.
In other words, the rest of gray-and white-box attacks such as cryptanalysis and fault injection are not taken into account. Thus, the proposed structure is not as heavyweight as a white-box implementation.

Threat Model
We clarify the threat model as follows. Above all, an attacker has no access to the internal computing resource in the device. This non-invasive attacker can obtain the input and output of encryption and can collect power traces. When conducting power analysis, the target hypothetical values against the table-based implementation of AES are one of the followings. First, the most common hypothetical value is the output of MixColumns multiplication. More specifically, it is the result of multiplication of the SubBytes output with one of the three coefficients in the MixColumns matrix. Second, the partial or three XOR operations between four bytes from MixColumns multiplication can be attacked. Here we note that the three XORs compute a subbyte of the round output.
Ironically, the low correlation provided by the proposed encoding increases the probability that the lowest-ranked key is the correct key as a result of power analysis. To solve this problem, we explain a method of deliberately raising the ranking of correct subkeys in the power analysis results.

Design
The following describes a rearrangement of AES-128 by which a series of lookup tables is generated. By shifting the initial AddRoundKey into the first round and by applying ShiftRows to the round key (except the final round key), AES-128 can be described concisely as follows: state ← plaintext for r = 1 · · · 9 ShiftRows(state) AddRoundKey(state,k r−1 ) SubBytes(state) MixColumns(state) ShiftRows(state) AddRoundKey (state,k 9 ) SubBytes(state) AddRoundKey(state, k 10 ) ciphertext ← state, where k r is a 4 × 4 matrix of the r-th round key, andk r is the result of applying ShiftRows to k r . By doing so, AddRoundKey can combine with SubBytes before multiplying each column of the MixColumns matrix for the first -ninth rounds.
Let T-boxes be an 8×8 lookup table defined as where j is the column index of the vector. The next step is to make a composition U • T , say U T , mapping each subbyte of the plaintext to the MixColumns multiplication. Because the first key-dependent intermediate value, after running encryption, is exposed by looking up the U T table, its output must be encoded. Let denote them by In order to apply L on the four bytes of a column vector above, four sets of (f, g) are required; therefore each round uses 16 sets in total. The subscripts j,k are used to index a set pertaining to L, where j is a column index and k ∈ {1, 2, 3, 4}. y i,k is then encoded by L j,k (y i,k , f j,k , g j,k ). The structure of lookup tables precomputing the operations up to the MixColumns multiplication are simply depicted in Fig. 4. Note that the second round begins with the decoding of the first round output whereas the first round does not have to decode the plaintext. Through out this paper, we assume that the nibble encoding (blank squares in Fig. 4) is always applied to every boundary of lookup tables.   can be placed in a 4×4×4 array. The next step is to combine the encoded results of MixColumns multiplication into the round output by conducting XOR operations. Since the nibble encoding swaps zeros with unknown values, every XOR operation depicted by ⊕ in Fig. 5 must be performed by looking up the XOR tables, denoted by T x . An instance of T x is generated by using three nibble encodings to decode two 4-bit inputs and to encode a 4-bit output. Due to the distributive property of multiplication over XOR, L does not have to be decoded in this process. The final round does not involve MixColumns, and thus T 10 is not composed with U . Because its outputs make a ciphertext, T 10 does not encode the output. Let Q 0 denote the set of tables above, protected by the proposed encoding. As previously pointed out, we need another set of lookup tables, say Q 1 , so that the correct key does not show the lowest correlation as a result of power analysis. Here, Q 1 is simply generated by flipping the input and output bits of Q 0 . By doing so, Q 1 can also provide the balanced encoding on the encryption of a plaintext. In order to effectively protect the key from power analysis, the balance must be broken to some extent. So, a plaintext is encrypted by using Q 0 with probability α and by using Q 1 with probability 1 − α. Let {b 1 , b 2 · · · b n } be a sequence of binary numbers where b i = 0 or 1 such that If a random number generator is available in the device, each encryption begins by picking up i ∈ [1, n] at random and encrypts a plaintext using Q bi . If α = 1/2, a binary number, say b, may be simply generated to choose Q b . In this case, this is the only operation that the encryption depends on the run-time random number generator. Otherwise, based on the fact that power analysis uses uniformlydistributed plaintexts, i can be derived from plaintexts. For example, if n is unknown and less than 256, an XOR sum of every subbyte of the plaintext (mod n) can be used to choose i. By doing so, the encryption becomes independent of run-time random sources.

Costs
From the 1st to 2nd rounds, the size and the number of lookups of the table are only half compared to a white-box AES implementation [9]. This is because we do not protect the intermediate values by a 32-bit linear transformation which is replaced with four 8-bit transformations. Only the first and the last two MixColumns are protected against the non-invasive power analysis, and thus the proposed encoding is applied to those five outer rounds. During the encryption operation, one byte must pass through two MixColumns to be affected by all the bits in the key. For the inner rounds (from the 3rd to the 7th rounds) a straightforward AES implementation is adapted. Table 3 shows the table size of the number of lookups for the outer rounds. Here, the additional memory consumption including the S-box and the rest of round keys required for the inner-round operations is negligible and therefore gives approximately 116KB of the table size. Because the size of Q 0 and Q 1 are the same, the total size is about 232KB. In addition, approximately 400 operations including lookups and XORs are required for the inner rounds and thus about 1,000 operations are needed in total. Simply put, the additional cost for applying the proposed encoding is mainly imposed by the lookup tables of the protected rounds. From the practical point of view, each execution of encryption does not need to generate random numbers and a new set of masked tables.

Experimental Results
Our experiments can be divided into two parts. First, we demonstrate the balanced encoding using only Q 0 . To that end, the UT outputs and the round outputs were analyzed. We measured how much they correlate with the correct hypothetical values through the Walsh transforms and the DCA attacks. Second, we show that there is an increase in the correlation coefficients when using either Q 0 or Q 1 with a 1/2 probability. As mentioned before, it has the same effect as the increase in encoding imbalance. By doing so, the correct subkey does not lead to the lowest correlation.

Analysis of the UT Outputs
To demonstrate the effect of the balanced encoding on the UT outputs, we provide the following experimental results. First, the correlation of the UT outputs to the hypothetical values was investigated in the first round. Specifically, the hypothetical values guess the results of MixColumns multiplication, i.e., the Sub-Bytes outputs multiplied by 1, 2, or 3. In the following, we take a close look at U T 1 0,0 , a slice of the UT table mapping the first subbyte of a plaintext to the MixColumns multiplication in the first round. The Walsh transforms W t is defined: Here, W t tells us how much the lookup values of U T 1 0,0 and the hypothetical SubBytes output multiplied by ∈ {1, 2, 3} are correlated. For every single bit of the correct hypothetical values, all of the Walsh transforms give 0 as a result of the balanced encoding as shown in Fig. 10 -Fig. 12 in Appendix A. Fig. 6 shows a small part of the results obtained by the hypothetical values -the first bit of the SubBytes output multiplied by 1, 2, and 3. This balanced encoding has an influence on the result of DCA attacks using the hypothetical SubBytes output. In order to illustrate it, 10,000 computational traces of encryption using 10,000 random plaintexts were collected by using Valgrind. Table 4 shows the DCA result based on the SubBytes output. All correct subkeys ranked the lowest out of eight attacks at least once. Table 5 compares the highest correlation coefficient from all key candidates and the coefficient from the correct key. When the computational traces are composed of only the UT outputs, the DCA results and the corresponding correlation coefficients are shown in Table 10 and Table 11 in Appendix B, respectively. This shows the proposed encoding addresses the correlation problem caused by the existing encoding method. These two experiments were carried out to show there is no problematic correlation between the encoded lookup values and the correct values of S ∈{1,2,3} . Table 4: DCA ranking on the AES encryption using only Q 0 when conducting mono-bit CPA on the SubBytes output with 10,000 computational traces.``````T   166 0.163 0.164 0.159 0.155 0.170 0.154 0.155 0.156 0.166 0.165 0.160 0.170 0.160 0.156 0.158 With α = 1/2, the probability that a plaintext is encrypted with Q 0 or Q 1 is the same. The next experiments are almost the same with the previous ones, except that Q 0 and Q 1 were selected with a 1/2 probability for each encryption.
In other words, the Walsh transforms were calculated by using the UT lookup values from Q 0 and Q 1 . All of the results are provided in Fig. 14 -Fig. 16 in Appendix A, and Fig. 7 shows one of them. The hypothetical value was, like in the case of the previous experiments, the first bit of the SubBytes output multiplied by 1, 2, and 3. There was an increase in the encoding imbalance by which the correct subkey does not lead to the lowest correlation to the correct hypothetical values. The encoding imbalance shown in the results of the Walsh transforms above improves the protection of keys against DCA attacks searching for either the highest-or lowest-ranking subkey candidate. While the correct subkeys are in the lowest rank in Table 4, those are not in the highest or lowest ranks as shown in Table 6 when a plaintext was encrypted by looking up Q 0 or Q 1 with a 1/2 probability. Compared to Table 5, the gap between correlation coefficients computed by the correct and wrong subkeys are reduced as shown in Table 7.

Analysis of the Round Outputs
The encoded round output of the first round was analyzed so that the balance in the encoding applied to the round output can be investigated. Let p1 and p2   denote the first two byte of the plaintexts. When the remaining 14 bytes are fixed to 0, the first byte of the first round output can be expressed as follows.
where c is a constant. For simplicity, represents the encoding applied to δ. Then, the first subbyte of the first round output protected by the proposed encoding can be written by • δ(p1, p2). If we assume that the attacker knowsk 0 0,0 , the corresponding hypothetical value is given by where k * is the key candidates. Let the subscripts i and i denote the i-and i -th bits, respectively. For a fixed p1 and the correct key candidate, by Equation (2), we expect Thus, the Walsh transform W γ is defined: To see the effect of the balance in the encoded round output, we calculated W γ for all i, i ∈ [1,8]. As a result, the correct subkey always produced zeros on the Walsh transforms as illustrated in Fig. 13 in Appendix A, and Fig. 8 shows one of the results in the case of i = 1. Only the correct subkey (0x55) scores 0 for all i ∈ [1,8]. We also collected 10,000 computational traces while performing encryption using plaintexts consisting of the first two random bytes (p1, p2) followed by the 14 zeros. Assuming that the first subkeyk 0 0,0 is known, we mounted a customized DCA attack to recover the second subkeyk 0 1,0 . Table 8 shows the result. It is noteworthy that the DCA ranking of the correct subkey is relatively high compared to Table 4 because there is a decrease in the correlation coefficients computed by each of all key candidates. For this reason, the round output protected by the proposed encoding is not an attractive attack target for power analysis. The Walsh transforms and the DCA results with respect to the round outputs obtained by looking up Q 0 and Q 1 with a 1/2 probability are provided in Fig. 9 and Table 9, respectively. There is no noticeable point of key leakage. These experimental results give us the following. The proposed encoding has the effect of extremely lowering the problematic correlation to the correct hypothetical intermediate value. However, due to this fact, a variant of power analysis can find the subkeys that lead to the lowest correlation on the UT output. If a plaintext is encrypted by either Q 0 and Q 1 with a 1/2 probability, it is possible to counteract the variant of power analysis in advance.   operations quickly. In this paper, we improved on the internal encoding of the table-based AES implementation in such a way to protect the key hidden in the tables from power analysis as well as simple memory observation. Since our proposed encoding is perfectly balanced, power analysis attackers may guess the key which leads to the lowest correlation to the correct hypothetical values. To solve this problem, we suggested to generate the complement of the balanced tables and use it to encrypt a plaintext with a 1/2 probability. Meanwhile, our scheme requires only 232KB in the memory space and 1,000 operations including XORs and lookups. It is also noteworthy that it does not rely on run-time random number generators.
As future work, we remark that it seems possible to combine our implementation with countermeasures of fault attacks [3,6,11]. In particular, our table-based implementation is easy to combine with a table redundancy method for protecting fault attacks [17]. By doing so, we can defend against power analysis and fault attacks at the same time with only a few hundred kilobytes of memory space. Since a table redundancy method is also not dependent on a run-time random source, a combination of both techniques seem to be reasonable for lowcost devices. Note, however, that the proposed implementation is secure under the gray-box model. In other words, the key would lead to the lowest correlation if a white-box attacker could manipulate the execution flow so that either table of Q 0 or Q 1 is always selected.

A The experimental results of the Walsh Transforms
All of the Walsh transform results explained in Section 5 are provided. First, Fig. 10 -Fig. 12 show W t1 -W t3 , respectively, using only Q 0 . Next, Fig. 13 depicts W γ . Every Walsh transform with respect to the correct subkeys and Q 0 results in the value of 0. In contrary, Fig. 14 -Fig. 16 illustrate W t1 -W t3 , respectively, with an increase in the encoding imbalance when using Q 0 and Q 1 . Fig. 17 also demonstrate it with respect to W γ .
B The experimental results of the DCA attacks on the UT outputs Table 4 and Table 5 in Section 5 show the results of DCA using the computational traces that contain every computation in the encryption. For this reason, the DCA ranking of the correct subkey was not always the lowest. To show the effectiveness of our balanced encoding in more detail, we would like to provide DCA results using the 10,000 computational traces consisting of only the UT output values. This will help us understand more accurately how the Walsh transform score 0 for the UT output appears in the correlation coefficients. As shown in Table 10, all correct subkeys were ranked lowest in all cases as a result of the DCA attacks. In this regard, it can be seen that the correlation coefficients calculated by the correct subkeys shown in Table 11 is much lower than the coefficients provided in Table 5.