## 5 Analysis of the Protocol
### Security Analysis  
In this section, we show that the security of the proposed scheme is information-theoretically secure. This implies that even though a minor amount of information is inevitably divulged to establish a useful linear regression model, the attacker cannot compute the exact values of the other party's data, even if the attacker has infinite computing power. We assume that all parties are semi-honest, i.e., the participants strictly follow the protocol, but they may be interested in knowing additional information that they are not explicitly permitted to know. **Theorem 1**. : _Assume that each party collects more than \(m+1\) data. The proposed collaborative learning method for the optimal parameters of a linear regression model is secure in the following sense:_  
1. _A does not have enough information to compute any elements in_ \(X_{2}\) _and_ \(\vec{y}_{2}\)_;_
2. _B does not have enough information to compute any elements in_ \(X_{1}\) _and_ \(\vec{y}_{1}\)  
Figure 1: Secure collaborative learning of linear regression without encryption. In the protocol, assume that \(A\) and \(B\) intend to utilize the least square method to construct a linear model that comprises \(m\) features. Proof. : Assume that some curious party attempts to calculate the values of the other party's data using the information he/she has collected in the protocol. We show that the number of unknown variables is greater than the number of equations he/she can formulate. This implies that the curious party cannot determine the exact value of the other party's data, even if they have infinite computing power. Assume that \(A\) has a set of \(n_{1}\) data and \(B\) has a set of \(n_{2}\) data: \(n_{1}+n_{2}=n\) and \(n_{1},n_{2}>m+1\), where \(m\) is the number of features in the system. First we show that \(A\) cannot compute the data of \(B\) (i.e., elements of \(X_{2}\) and \(\vec{y}_{2}\)) by using the information \(A\) collects in the execution of the protocol. The number of elements in \(X_{2}\) is \(n_{2}\times(m+1)\), but the first column of \(X_{2}\) is a constant. Thus, there are \(n_{2}m\) variables. The number of elements in \(\vec{y}_{2}\) is \(n_{2}\), and it contains \(n_{2}\) variables. Thus, \(A\) has a total of \(n_{2}(m+1)\) unknowns. On the other hand, the number of elements in \(X_{2}^{T}X_{2}\) is \((m+1)^{2}\), and the number of elements in \(X_{2}^{T}\vec{y}_{2}\) is \(m+1\). The first element in the first row of \(X_{2}^{T}\vec{y}_{2}\) is \(n_{2}\). Thus, \(A\) has only \((m+1)^{2}+n_{2}-1\) quadratic equations. Since \(n_{2}>m+1\), \(A\) does not have enough information to compute the values of the elements in \(X_{2}\) and \(\vec{y}_{2}\). Similarly, we can show that \(B\) does not have enough information to compute the values of the elements in \(X_{1}\) and \(\vec{y}_{1}\). Theorem 1 shows that even if the parties or the server have infinite computational power, there is not enough information to infer the values of the other party's data. That is, the security of the proposed linear regression scheme does not depend on computationally hard problems, such as factoring large integers or solving discrete logarithm problems in a large finite group. These computationally hard problems are solvable if the attacker has sufficient computing power: for example, by using a quantum computer. Although we have proved that the curious party cannot compute the values of the dataset of the other party, even if they have infinite computing power, the curious party does know some information about the dataset. For example, the amount of data and the sum of the squares of the data, etc. For the information leakage in general, we note that [PERSON] and [PERSON] show that if a machine learning model is useful, it must reveal some information about the data on which it was trained [26; 27]. Our proof indicates that the information disclosed to the other party through the proposed collaborative linear regression scheme is minimal.