# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 4 Breaking Complexity of SAPKA Algorithms
### [PERSON] Attempts an Attack against [PERSON]  
We assume the following:  
* a prime number \(p\), where \(|p|=n\);
* a semi-group \(\mathcal{S}:=\mathcal{M}(d,\mathbb{Z}_{p})\);
* a subset \(\underline{\mathcal{S}}:=\{y\in\mathcal{S}\;:\;|y|_{\mathcal{S}}\leq d^{2}m \}\subset\mathcal{S}\);
* \(x_{A}\in\underline{\mathcal{S}}\);
* \(N_{B},x_{B}\in\mathcal{S}\);
* a map \(x_{g}:\mathcal{S}\to\mathcal{S}\), \(x_{g}(y):=g^{y}\), where \(g\) is a primitive element of \(\mathcal{S}\); and
* a not linear monic polynomial \(s\), where \(n=s(m)>m\) for all \(m\in\mathbb{N}\). [PERSON]'s goal is to obtain \(x_{A}\) from the following public keys: \[y_{B,1}(y)_{a,b}:=N_{1}^{-1}\circ x_{4}(y)_{a,b}=\prod_{l\in\{1,\ldots,d\}}(g^{ xy})_{l}^{(N_{B})_{a,l}}\]\(y_{B,2}(y)_{a,b}:=x_{1}\circ x_{2}(y)_{a,b}=\prod_{l\in\{1,\ldots,d\}}(g^{\circ x_{ B}})_{a,l}^{(y)_{l,b}}\), where \(a,b\in\{1,\ldots,d\}\), and the following elements:  
\(g^{\circ x_{B}}\)  
\(g^{\circ N_{B}}\)  
\(y_{A}=N_{1}^{-1}\circ x_{4}(x_{A})=g^{\circ N_{B}x_{A}}\), to calculate  
\[y_{B,1}^{-1}(y_{A})_{a,b}=x_{4}^{-1}\circ N_{1}(g^{\circ N_{B}x_{A}})_{a,b}= \log_{g}(g^{\circ N_{B}^{-1}N_{B}x_{A}})_{a,b}=\log_{g}(g^{x_{A}})_{a,b}=(x_{A })_{a,b} \tag{22}\]  
for all \(a,b\in\{1,\ldots,d\}\). It appears that she first needs to obtain an element \(N_{B}\) by calculating \(\log_{g}(g^{\circ N_{B}})_{a,b}\) for all \(a,b\in\{1,\ldots,d\}\), the complexity of which is equivalent to the complexity for calculating \(d^{2}\)\(n\)-bit logarithms for the map \(x_{g}\), because she does not know \(N_{B}\), so as to obtain \(N_{B}^{-1}\). After obtaining \(N_{B}\), she can proceed to the final two equalities of (22), and the complexity of calculating \(\log_{g}(g^{x_{A}})_{a,b}=(x_{A})_{a,b}\) for all \(a,b\in\{1,\ldots,d\}\) is equivalent to the complexity of calculating \(d^{2}\)\(m\)-bit logarithms for the map \(x_{g}\). We now verify that [PERSON] really needs to calculate at least the same amount as to obtain \(d^{2}\)\(n\)-bit logarithms by calculating \(\log_{g}(g^{\circ N_{B}})_{a,b}\) for all \(a,b\in\{1,\ldots,d\}\). In Attack 1, we attempt to find other descriptions for map \(y_{B,1}\), as in Section 4.2. In Attack 2, we attempt an attack in which [PERSON] avoids calculating \(d^{2}\) DLPs for \(N_{B}\), and we compare the breaking complexity of the attack with an exhaustive search for \(x_{A}\in\mathcal{\underline{S}}\). In Attack 3, we attempt to determine the least complexity that [PERSON] requires to obtain \(x_{A}\). Hereafter, we refer to the logarithm of matrix \(M\in\mathcal{M}(d,\mathbb{Z}_{p})\) as follows:  
\[\log_{g}M=(\log_{g}M_{a,b})\qquad(g\in\mathbb{Z}_{p})\]  
\[\log_{G}M=(\log_{G_{a,b}}M_{a,b})\qquad(G\in\mathcal{M}(d,\mathbb{Z}_{p})).\]  
Attack 1  
Using the known element \(g^{\circ N_{B}}\), [PERSON] attempts the following calculation for all \(a,b\in\{1,\ldots,d\}\):  
\[\log_{g^{\circ N_{B}}}(y_{A})=\log_{g^{\circ N_{B}}}g^{\circ N_{B}x_{A}}. \tag{23}\]  
However, unlike in Section 4.2, the relation \(\log_{g^{\circ N_{B}}}g^{\circ N_{B}x_{A}}=x_{A}\) does not hold. She obtains \(X\in\mathcal{S}\) instead of \(x_{A}\in\mathcal{\underline{S}}\) from (23):  
\[\log_{g^{\circ N_{B}}}g^{\circ N_{B}x_{A}}=\log_{g^{\circ N_{B}}}(g^{\circ N_ {B}})^{\circ X}=X.\]  
In this case, \(X\) holds for the relation  
\[N_{B}\bullet X=N_{B}x_{A},\]  
where \(\bullet\) denotes element-wise matrix multiplication. Obviously, \(X=x_{A}\) does not always hold, so \(N_{1}^{-1}\circ x_{4}(y_{A})=\log_{g^{\circ N_{B}}}(y_{A})\) also does not hold. Moreover, to obtain \(x_{A}\), [PERSON] needs to calculate \(\log_{g}g^{\circ N_{B}}=N_{B}\). Attack 2  
We introduce an attack in which [PERSON] does not calculate \(\log_{g}g^{\circ N_{B}}=N_{B}\). The public key of [PERSON] \(y_{A}\) is described as  
\[y_{A}=\left(