# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 4 Breaking Complexity of SAPKA Algorithms
### Computational Complexity of SEDH for Alice and Bob  
For a given \(d\in\mathbb{N}\), approximately \(dm\) multiplications are required if the bit size of the exponent is \(n\) to calculate one scalar exponentiation. Furthermore, approximately \(m\) multiplications are required if the bit size of the exponent is \(m\). Thus, the calculation  
\[g^{\circ X} \tag{32}\]  
requires approximately \(d^{2}s(m)=2d^{3}m\) multiplications if \(X\in\mathcal{S}\). If \(X\in\underline{\mathcal{S}}\), it requires approximately \(d^{2}m\) multiplications. Moreover, the calculation  
\[\prod_{l\in\{1,\ldots,d\}}(Y_{a,l})^{(X)_{l,b}} \tag{33}\]  
requires \(ds(m)=2d^{2}m\) multiplications if \(X\in\mathcal{S}\) and \(dm\) multiplications if \(X\in\underline{\mathcal{S}}\) for each \(a,b\in\{1,\ldots,d\}\). Thus, according to (14) and (15), the computational complexities required by [PERSON] for \(y_{A}\) and her SSK denoted by the functions \(T_{y_{A}},T_{x_{A}}:\mathbb{N}\to\mathbb{R}^{+}\) of \(m\) are  
\[T_{y_{A}}(m):=d^{3}m \tag{34}\]  
\[T_{x_{A}}(m):=d^{3}m. \tag{35}\]  
From the calculations of \(g^{\circ x_{B}},g^{\circ x_{B}}\), and (16), [PERSON]'s computational complexities for \(y_{B,1}\), \(y_{B,2}\), and their SSK, denoted by the functions \(T_{y_{B,1}},T_{y_{B,2}},T_{x_{B}}:\mathbb{N}\to\mathbb{R}^{+}\) of \(n\), become  
\[T_{y_{B,1}}(n):=d^{2}n \tag{36}\] \begin{table}
\begin{tabular}{c c} \hline \hline  & **Requirements** \\ \hline \(n\) & Sufficiently large for one DLP \\ \hline \(m\) & \(2^{dm}\) must be sufficiently large for an exhaustive search \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Requirements for \(n\) and \(m\). \[T_{y_{B,2}}(n):=d^{2}n \tag{37}\] \[T_{x_{B}}(n):=d^{3}n \tag{38}\]  
As \(n=s(m)=2 dm\), \(T_{y_{B,1}}\), \(T_{y_{B,2}}\), and \(T_{y_{K_{B}}}\) can be described as functions of \(m\) as follows:  
\[T_{y_{A},1}(n)=T_{y_{B,1}}(s(m))=d^{2}s(m)=2d^{3}m\]  
\[T_{y_{B,2}}(n)=T_{y_{B,2}}(s(m))=d^{2}s(m)=2d^{3}m\]  
\[T_{x_{B}}(n)=T_{x_{B}}(s(m))=d^{3}s(m)=2d^{4}m.\]  
Thus, the total complexity for [PERSON] and [PERSON] can be compared:  
\[T_{y_{A}}(m)+T_{x_{A}}(m)=2d^{3}m<4d^{3}m+2d^{4}m=T_{y_{B,1}}(s(m))+T_{y_{B,2}}( s(m))+T_{x_{B}}(s(m)). \tag{39}\]  
When \(d\) is given, \(T_{y_{A}}(m)+T_{x_{A}}(m)\) and \(T_{y_{B,1}}(s(m))+T_{y_{B,2}}(s(m))+T_{x_{B}}(s(m))\) have the same order of complexity. \(2d^{4}\) and \(2d^{3}\) are considered as coefficients. Of course, we can consider the total complexity for [PERSON] and [PERSON] by the functions \(T^{\prime}_{A},T^{\prime}_{B}:\mathbb{N}\to\mathbb{R}^{+}\) of \(d\), which are defined as  
\[T^{\prime}_{A}(d):=2 md^{3}\]  
\[T^{\prime}_{B}(d):=4 md^{3}+2 md^{4}\]  
for a given \(m\). In this case, \(T^{\prime}_{A}(d)\in O(d^{3})\), \(T^{\prime}_{B}(d)\in O(d^{4})\), and \(O(d^{4})\subset O(d^{3})\) are obvious. Which values of \(m\) and \(d\) should be given and which should be the input of the functions can be determined the environment in which the algorithm is used, such as the computational resources and communication infrastructure. As mentioned in Remark 1, [PERSON] can select her secret key \(x_{A}\) not only as a matrix, but also as a vector, whereas \(x_{B}\) and \(N_{B}\) are selected as matrices. Let \(\mathcal{V}\) be a vector space of \(\mathcal{V}:=\mathbb{Z}_{p}^{d}\), where \(|y|\leq dn\ (y\in\mathcal{V})\) and a subset \(\underline{\mathcal{V}}\) of \(\underline{\mathcal{V}}:=\{y\in\mathcal{V}:|y|\leq dm\}\subset\mathcal{V}\), and suppose that \(x_{A}\) is selected from \(\underline{\mathcal{V}}\). In this case, the breaking strategy against this algorithm for Eve is as follows:  
* solving \(d^{2}\) DLPs for \(N_{B}\) and \(d\) DLPs for \(x_{A}\), and
* an exhaustive attack for \(x_{A}\) within \(\underline{\mathcal{V}}\), the size of which is \(2^{sm}\). That is, the breaking complexity is equivalent to the case when \(x_{A}\in\underline{\mathcal{S}}\) in terms of the order of complexity. Thus, there is also no problem in selecting \(n\) and \(m\) from the relation of Theorem 1 in this case.