# Privacy Preserving Classification of EEG Data Using Machine Learning and Homomorphic Encryption
## 2 Methods
### Optimization Formulation  
Numerical optimization is typically performed using gradient-based iterative methods that converge in an unknown number of steps. Unfortunately, such formulations are difficult to apply on homomorphically encrypted data because they require an unknown (and typically large) number of operations, there are often nonlinear functions involved, and they require a comparison operation for evaluating the convergence. As most HE schemes are homomorphic only for addition and multiplication, they do not allow for division and do not support nonlinear function evaluation. The comparison between encrypted values is another operation that cannot be performed [28]. To bypass these requirements, we are proposing a solution inspired by previous work, where non-linear functions are approximated with low degree polynomials. Specifically, when performing such approximations, the resulting model turns into a polynomial function. If the loss function to be minimized is also analytically differentiable, the entire optimization problem is convex and can be solved analytically. Let \(X\) be a \(N\) by \(M\) matrix containing the input data where each row \(\mathbf{x}_{i}\) is a data sample and \(\mathbf{y}\) is a column vector of size \(N\) containing the output values. Following the idea of encoding or encrypting the numbers into a polynomial form as suggested in [9; 12; 18], we assume that the model function to be optimized can be reduced to a multivariate polynomial function as in Equation (10):  
\[P(\mathbf{x})=\sum_{i=0}^{N_{t}}a_{i}p_{i}(\mathbf{x}), \tag{10}\]  
where \(p_{i}(\mathbf{x})\) is a monomial term combining components of \(\mathbf{x}\) at different powers, e.g., \(x_{1}x_{2},x_{1}^{2}x_{2},x_{1}^{2}x_{2}^{2}\) etc., \(\mathbf{a}=[a_{1},a_{2},\ldots,a_{N_{t}}]\) are the model parameters, and \(N_{t}\) is the number of terms. As discussed in [3], to determine the model parameters, a cost function must be defined and optimized. Thus, we assume that the objective is to minimize the sum of squares, described by Equation (11):  
\[C(\mathbf{a})=\sum_{i=0}^{N}(P(\mathbf{x}_{i})-y_{i})^{2}, \tag{11}\]  
With respect to the inputs \(x_{i}\), \(C(\mathbf{a})\) is a highly nonlinear function. However, with respect to the parameters, \(\mathbf{a}\) is a quadratic function where the minimum can be computed directly by solving the normal equation of the over-determined linear system \(P\mathbf{a}=y\). The already derived, widely known and used Equation (12) is employed for this purpose:  
\[\mathbf{a}=\left(P^{T}P\right)^{-1}\!\!P^{T}\mathbf{y}, \tag{12}\]  
where \(P\) is a \(N\) by the \(N_{t}\) matrix containing the numerical values obtained when evaluating each polynomial feature \(p_{i}(\mathbf{x}),i\in[1,N_{t}]\) for each data sample \(\mathbf{x}_{i}\), \(i\in[1,N]\). Although all the steps above require only algebraic operations, since the proposed encoding scheme does not allow for the division of two numbers, we cannot completely compute \(\left(P^{T}P\right)^{-1}\) in the encoded-encrypted form. Therefore, we only compute the dot products \(P^{T}P\) and \(P^{T}\mathbf{y}\) in the encrypted form and then perform the remaining operations after decryption. This is a notable limitation that prevents the model fitting process to be performed completely on encrypted data. However, typically, the number of data samples \(N\) is much larger than the number of model parameters \(N_{t}\); therefore, the dot product \(P^{T}P\) results in a small matrix \(N_{t}\) by \(N_{t}\), while \(P^{T}\mathbf{y}\) results in a vector of size \(N_{t}\). Since the input data are significantly regressed by these operations, decrypting does not expose the original data. Referring to overfitting issues, they typically appear when the model is too complex. In our case, if the number of polynomial terms is not too large, the model does not attempt to learn or explain the random error or noise present in the data.