# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 3 Concrete Examples of SAPKA
### Schur Exponentiation-Based DH (Sedh)  
Let \(\mathcal{S}\) be the multiplicative semi-group \(\mathcal{S}:=\mathcal{M}(d,\mathbb{Z}_{p})\) of \(d\times d\) matrices with entries in \(\mathbb{Z}_{p}\). The algorithm introduced in this section uses _Schur exponentiation_; that is, element-wise matrix exponentiation. The symbol \(c^{\alpha M}\) is defined as follows:  
\[\left(c^{\alpha M}\right)_{ij}:= \begin{cases}c^{M}&\text{if $M$ is a scalar}\\ c^{M_{ij}}_{ij}&\text{if $M$ is a matrix}\end{cases} ;\qquad i,j\in\{1,\cdots,d\}.\]  
The key agreement process is as follows:  
1. [PERSON] selects a matrix \(x_{B}\in\mathcal{S}\), an invertible matrix \(N_{B}\in\mathcal{S}\), and a primitive element \(g\) of \(\mathbb{Z}_{p}\). Subsequently, he constructs the quintuple \(C_{SE}:=(x_{1},x_{2},x_{3},x_{4},N_{1})\in\mathcal{K}_{B}\) for all \(a,b\in\{1,\dots,d\}\) as follows: * \(x_{1}(y)_{a,b}:=\prod_{l\in\{1,\dots,d\}}(g^{\circ x_{B}})^{(y)_{l,g}}_{a,l}\)\(x_{2}:=id\)
* \(x_{3}(y)_{a,b}:=\prod_{l\in\{1,\dots,d\}}(y)_{l,b}^{(x_{B})_{a,l}}\)
* \(x_{4}(y):=g^{sy}\)
* \(N_{1}(y)_{a,b}:=\prod_{l\in\{1,\dots,d\}}(y)_{l,b}^{(N_{B}^{-1})_{a,l}}\),  
where \(y\in\mathcal{S}\). The compatibility condition holds for all \(y\in\mathcal{S}\) and \(a,b\in\{1,\dots,d\}\):  
\[x_{1}\circ x_{2}(y)_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{\circ x_{B}})_{a,l}^{(y )_{1,b}}=\prod_{l\in\{1,\dots,d\}}g^{(x_{B})_{a,l}(y)_{1,b}}\]  
\[=g^{\sum_{l\in\{1,\dots,d\}}(x_{B})_{a,l}(y)_{1,b}}=g^{(x_{B}y)_{a,b}}=(g^{ \circ x_{B}y})_{a,b}\]  
\[x_{3}\circ x_{4}(y)_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{\circ y})_{l,b}^{(x_{B} )_{a,l}}=\prod_{l\in\{1,\dots,d\}}g^{(y)_{1,b}(x_{B})_{a,l}}\]  
\[=g^{\sum_{l\in\{1,\dots,d\}}(x_{B})_{a,l}(y)_{1,b}}=g^{(x_{B}y)_{a,b}}=(g^{ \circ x_{B}y})_{a,b}.\]  
Step 2B [PERSON] constructs their public keys \(y_{B,1},y_{B,2}\) as a map for each  
\[y_{B,1}(y)_{a,b}:=N_{1}^{-1}\circ x_{4}(y)_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{ \circ y})_{l,b}^{(N_{B})_{a,l}}\]  
\[y_{B,2}(y)_{a,b}:=x_{1}\circ x_{2}(y)_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{ \circ x_{B}})_{a,l}^{(y)_{1,b}}\]  
for all \(a,b\in\{1,\dots,d\}\). In this case, \(y_{B,1}(y)_{a,b}\) can also be expressed as follows:  
\[y_{B,1}(y)_{a,b}=\prod_{l\in\{1,\dots,d\}}(g^{\circ y})_{l,b}^{(N_{B})_{a,l}}= \prod_{l\in\{1,\dots,d\}}(g^{\circ N_{B}})_{a,l}^{(y)_{1,b}}.\]  
[PERSON] sends the maps \((y_{B,1},y_{B,2})\) to [PERSON]. This is equivalent to sending the matrices \(g^{\circ N_{B}},g^{\circ x_{B}}\in\mathcal{S}\). Step 1A [PERSON] selects her secret key \(x_{A}\in\mathcal{S}\). Step 2A [PERSON] calculates her public key \(y_{A}\) for all \(a,b\in\{1,\dots,d\}\) as follows:  
\[y_{A_{a,b}}:=y_{B,1}(x_{A})_{a,b}=N_{1}^{-1}\circ x_{4}(x_{A})_{a,b}=\prod_{l \in\{1,\dots,d\}}(g^{\circ N_{B}})_{a,l}^{(x_{A})_{l,b}} \tag{14}\]  
\[=(g^{\circ N_{B}x_{A}})_{a,b}\]  
and sends it to [PERSON]. Step 3A [PERSON] calculates the SSK denoted by \(\kappa_{A}\) for all \(a,b\in\{1,\dots,d\}\) as follows:  
\[\kappa_{A_{a,b}}:=y_{B,2}(x_{A})_{a,b}:=x_{1}\circ x_{2}(x_{A})_{a,b}=\prod_{ l\in\{1,\dots,d\}}(g^{\circ x_{B}})_{a,l}^{(x_{A})_{l,b}}=(g^{\circ x_{B}x_{A}} )_{a,b}. \tag{15}\]  
Step 3B [PERSON] calculates the SSK denoted by \(\kappa_{B}\) for all \(a,b\in\{1,\dots,d\}\) as follows:  
\[=g^{\sum_{l\in\{1,\dots,d\}}(x_{B})_{a,l}(y)_{1,b}}=g^{(x_{B}y)_{a,b}}=(g^{ \circ x_{B}y})_{a,b}\]0  
\[=g^{\sum_{l\in\{1,\dots,d\}}(x_{B})_{a,l}(y)_{1,b}}=g^{(x_{B}y)_{a,b}}=(g^{ \circ x_{B}y})_{a,b}\]1  
_is satisfied for all \(y\in\mathcal{V}\) and \(a\in\{1,\ldots,d\}\), where \(x_{B},N_{B}\) are the same as above. Thus, [PERSON] can select her secret key \(x_{A}\) from \(\mathcal{V}\) and the computational complexity for calculating \(y_{A}\), \(\kappa_{A}\), and \(\kappa_{B}\) is obviously reduced compared with the case when \(x_{A}\in\mathcal{S}=\mathcal{M}(d,\mathbb{Z}_{p})\). The precise breaking and computational complexities for the \(C_{SE}\) of both the \(x_{A}\in\mathcal{V}\) and \(x_{A}\in\mathcal{S}\) cases are investigated in the following section._