# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 4 Breaking Complexity of SAPKA Algorithms
### [PERSON] Attempts an Attack against [PERSON]
\begin{array}{cccc}\prod_{l\in\{1,\ldots,d\}}(g^{\circ N_{B}})_{ 1,l}^{(x_{A})_{l,1}}&\ldots&\prod_{l\in\{1,\ldots,d\}}(g^{\circ N_{B}})_{1,l}^ {(x_{A})_{l,d}}\\ \vdots&\ddots&\vdots\\ \prod_{l\in\{1,\ldots,d\}}(g^{\circ N_{B}})_{d,l}^{(x_{A})_{l,d}}&\ldots&\prod _{l\in\{1,\ldots,d\}}(g^{\circ N_{B}})_{d,l}^{(x_{A})_{l,d}}\\ \end{array} \right)\]\[=\left( \begin{array}{ccccc}s^{No_{\text{B}}}\right)_{1,1}^{(x_{A})_{1,1}}(g^{ No_{\text{B}}})_{1,2}^{(x_{A})_{1,2}}\dots(g^{No_{\text{B}}})_{1,d}^{(x_{A})_{1,d}}&\dots&(g^{ No_{\text{B}}})_{1,1}^{(x_{A})_{1,d}}(g^{No_{\text{B}}})_{1,2}^{(x_{A})_{2,d}} \dots(g^{No_{\text{B}}})_{1,d}^{(x_{A})_{1,d}}\\ &\vdots&\ddots&\\ (g^{No_{\text{B}}})_{d,1}^{(x_{A})_{1,d}}(g^{No_{\text{B}}})_{d,2}^{(x_{A})_{ 1,d}}\dots(g^{No_{\text{B}}})_{d,1}^{(x_{A})_{d,1}}&\dots&(g^{No_{\text{B}}})_{ d,1}^{(x_{A})_{d,d}}(g^{No_{\text{B}}})_{d,2}^{(x_{A})_{d,d}}\dots(g^{No_{\text{B}}})_{ d,d}^{(x_{A})_{d,d}}\end{array} \right). \tag{24}\]  
* For row \(b\in\{1,\dots,d\}\) of \(y_{A}\), [PERSON] creates a matrix \(W_{b}=(w_{a,d}^{(b)})\in\mathcal{M}(d,\mathbb{Z}_{p})\) to satisfy \[\left( \begin{array}{c}(g^{No_{\text{B}}})_{1,1}^{(x_{A})_{1,b}}(g^{ No_{\text{B}}})_{1,2}^{(x_{A})_{2,1}}\dots(g^{No_{\text{B}}})_{1,d}^{(x_{A})_{ d,b}}\\ \vdots\\ (g^{No_{\text{B}}})_{d,1}^{(x_{A})_{1,b}}(g^{No_{\text{B}}})_{d,2}^{(x_{A})_{ 2,1}}\dots(g^{No_{\text{B}}})_{d,d}^{(x_{A})_{d,b}}\end{array} \right)=\left( \begin{array}{c}w_{1,1}^{(b)}w_{1,2}^{(b)}\dots w_{1,d}^{(b)}\\ \vdots\\ w_{d,1}^{(b)}w_{d,2}^{(b)}\dots w_{d,d}^{(b)}.\end{array} \right)\] Step 2 For all \(a,l\in\{1,\dots,d\}\), [PERSON] calculates \[v_{a,l}:=\log_{(g^{No_{\text{B}}})_{a,l}}w_{a,l}^{(b)}.\] (25)
* For all \(l\in\{1,\dots,d\}\), [PERSON] verifies whether or not \[v_{1,l}=v_{2,l}=\dots=v_{d,l}\] (26) is true. * If (26) is true for all \(l\in\{1,\dots,d\}\), [PERSON] can recover row \(b\in\{1,\dots,d\}\) of \(x_{A}\): \[ \begin{array}{c}(x_{A})_{1,b}=v_{1,1}=\dots=v_{d,1}\\ (x_{A})_{2,b}=v_{1,2}=\dots=v_{d,2}\\ \vdots\\ (x_{A})_{d,b}=v_{1,d}=\dots=v_{d,d}.\end{array} \] As \(N_{\text{B}}\) is an invertible matrix, there exists exactly one \((X_{1,b},X_{2,b},\dots,X_{d,b})^{t}\in\mathbb{Z}_{p}^{d}\) to satisfy system (24) for a given \(y_{A}\), \(g^{No_{\text{B}}}\) of row \(b\in\{1,\dots,d\}\); thus, it must be \((x_{A1,b},x_{A2,b},\dots,x_{Ad,b})^{t}\). If (26) is false in some \(l\in\{1,\dots,d\}\), [PERSON] returns to Step 1. In Step 2, [PERSON] needs to calculate at least two DLPs of \(m\)-bit logarithms; thus, she requires \(2\cdot 2^{\frac{m}{2}}\) multiplications. As \(\mathbb{Z}_{p}\) forms a group under multiplication, for any arbitrary element \(e\) in \(\mathbb{Z}_{p}\), there exists a unique \(w_{a,d}^{(b)}\in\mathbb{Z}_{p}\) such that:  
\[ew_{a,d}^{(b)}=(y_{A})_{a,b}\]  
for each \(a\in\{1,\dots,d\}\). Thus, [PERSON] has \(2^{n(d-1)}\) choices for \((w_{a,1}^{(b)},w_{a,2}^{(b)},\dots,w_{a,d-1}^{(b)})\) and each \(a\in\{1,\dots,d\}\), and therefore, [PERSON] must repeat Steps 2 to 4 at most \(2^{nd(d-1)}\) times. The total multiplications required for this attack is denoted as:  
\[2^{nd(d-1)+\frac{m}{2}+1}=2^{s(m)d(d-1)+\frac{m}{2}+1},\]  
which is much larger than the total multiplications required for an exhaustive search on each row of \(x_{A}\in\underline{\mathcal{S}}\), namely:  
\[m2^{dm}\]  
Attack 3  
Suppose that [PERSON] attempts to determine \(x_{A}\) directly from the formula of [PERSON]'s public key \(y_{A}\):  
\[(y_{A})_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{No_{\text{B}}})_{a,l}^{(x_{A})_{1,b}}. \tag{27}\]As \(N_{B}\) is an invertible matrix, this is equivalent to solving the following system for \(X\in\underline{\mathcal{S}}\):  
\[(y_{A})_{a,b}=\prod_{l\in\{1,\ldots,d\}}(g^{\circ N_{B}})_{a,l}^{(X)_{l,b}} \tag{28}\]  
for all \(a,b\in\{1,\ldots,d\}\) and given \(y_{A},g^{\circ N_{B}}\).