# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 2 Methods and Abstract of This Study
### [PERSON]'s Strategies for Recovering SSK  
[PERSON] wishes to calculate \(\kappa_{A}\) or \(\kappa_{B}\) by determining the secret key of [PERSON] or [PERSON] from the public keys. She knows the two composed maps of [PERSON] and one element of [PERSON], as follows:  
\[y_{B,1}(y)=N_{1}^{-1}\circ x_{4}(y)\qquad(y\in\mathcal{S}), \tag{6}\]  
\[y_{B,2}(y)=x_{1}\circ x_{2}(y)\qquad(y\in\mathcal{S}), \tag{7}\]  
\[y_{A}=N_{1}^{-1}\circ x_{4}(x_{A}). \tag{8}\]  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Key** & **Parameter** \\ \hline \multirow{4}{*}{Bob} & Secret keys & \(x_{1},x_{2},x_{3},x_{4},N_{1}:\mathcal{S}\rightarrow\mathcal{S}\) \\ \cline{3-3}  & Public keys & \(y_{B,1}=N_{1}^{-1}\circ x_{4}:\mathcal{S}\rightarrow\mathcal{S}\) \\ \cline{3-3}  & & \(y_{B,2}=x_{1}\circ x_{2}:\mathcal{S}\rightarrow\mathcal{S}\) \\ \cline{3-3}  & SSK & \(x_{B}=x_{3}\circ x_{4}(x_{A})\in\mathcal{S}\) \\ \hline \multirow{4}{*}{Alice} & Secret key & \(x_{A}\in\mathcal{S}\) \\ \cline{3-3}  & Public key & \(y_{A}=N_{1}^{-1}\circ x_{4}(x_{A})\in\mathcal{S}\) \\ \cline{1-1} \cline{3-3}  & SSK & \(x_{A}=x_{1}\circ x_{2}(x_{A})\in\mathcal{S}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Complete list of key of SAPKA.  
[PERSON]'s Strategy 1  
If \(x_{4}\) is an invertible map, \(y_{B,1}\) is also invertible; thus, she attempts to determine \(x_{A}\) from (6) and (8):  
\[x_{A}=y_{B,1}^{-1}(y_{A})=x_{4}^{-1}\circ N_{1}\circ N_{1}^{-1}\circ x_{4}(x_{A }). \tag{9}\]  
Subsequently, she can calculate  
\[\kappa_{A}=x_{1}\circ x_{2}(x_{A}).\]  
If \(x_{4}\) is not an invertible map, she obtains a set \(\{x_{E}\in\mathcal{S}:y_{A}=N_{1}^{-1}\circ x_{4}(x_{E})\}\) instead of an element from (9). However, in this case, she can calculate the SSK as follows:  
\[x_{1}\circ x_{2}(x_{E})=x_{3}\circ x_{4}(x_{E})=x_{3}\circ N_{1}\circ N_{1}^{ -1}\circ x_{4}(x_{E})=x_{3}\circ N_{1}(y_{A})=\kappa_{B}. \tag{10}\]  
The second equation of (10) is obtained from the compatibility condition (5), and the final equation is obtained from the definition of \(\kappa_{B}\) (see Figure 1 or Step 5 of Section 2.4).  
[PERSON]'s Strategy 2  
First, [PERSON] attempts to obtain a map \(N_{1}\) from (6) and then attempts to obtain a map \(x_{3,E}:\mathcal{S}\rightarrow\mathcal{S}\) that satisfies  
\[x_{3,E}\circ N_{1}\circ N_{1}^{-1}\circ x_{4}(y)=x_{1}\circ x_{2}(y) \tag{11}\]  
for all \(y\in\mathcal{S}\). Finally, she can calculate the SSK as follows:  
\[x_{3,E}\circ N_{1}(y_{A})=x_{3,E}\circ N_{1}\circ N_{1}^{-1}\circ x_{4}(x_{A })=x_{1}\circ x_{2}(x_{A})=\kappa_{A}. \tag{12}\]  
Suppose that [PERSON] constructs \(y_{B,1}\) and \(y_{B,2}\) to satisfy the following two requirements:  
1. It is difficult to calculate \(x_{4}^{-1}\circ N_{1}\circ N_{1}^{-1}\circ x_{4}(y)=y\) for all \(y\in\mathcal{S}\) in real time, or it is difficult to determine the invertible map of \(y_{B,1}\), \(x_{4}^{-1}\circ N_{1}\) in real time.
2. It is difficult to determine the map \(N_{1}\) from \(y_{B,1}=N_{1}^{-1}\circ x_{4}\) in real time, or it is difficult to obtain a map \(x_{3,E}\) to satisfy (11) in real time.  
Then, it is difficult for [PERSON] to obtain \(x_{A}\) from (9) and to proceed to (12) in real time; that is, [PERSON] cannot obtain the SSK in real time. It should be noted that the secret key \(x_{A}\) that [PERSON] selects is not strongly related to [PERSON]'s breaking complexity owing to Requirement 1. This means that [PERSON] may take substantially more responsibility for maintaining security than [PERSON]. In this case, [PERSON] can select her secret key space as a small one in terms of the bit size, provided that an exhaustive search for \(x_{A}\) is difficult in real time, and we expect that this will reduce [PERSON]'s computational complexity for \(y_{A}\) and \(\kappa_{A}\).