# New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement
## 2 Methods and Abstract of This Study
### Restrictions on SAPKA Framework  
We have already explained the high level of generality of SAPKA. However, owing to this generality, algorithms that do not ensure secure PKA are also included in this class. We present one example as follows:  
Let \(\mathcal{S}\) be \(\mathcal{S}:=\mathbb{Z}_{p}\) for some prime number \(p\). [PERSON] selects the numbers \(x_{B},n_{B}\in\mathcal{S}\) and keeps them secret. Let the maps \(x_{1},x_{2},x_{3},x_{4},N_{1}:\mathcal{S}\to\mathcal{S}\) be defined, for \(y\in\mathcal{S}\), as:  
* \(x_{1}(y):=x_{B}y\)
* \(x_{2}:=id\)
* \(x_{3}(y):=x_{B}y\)
* \(x_{4}(y):=id\)
* \(N_{1}(y):=n_{B}y\).  
In this case, all keys are described as in Table 2.  
The SSK calculations are performed as follows:  
\[\kappa_{A}=x_{1}\circ x_{2}(x_{A})=x_{B}x_{A}\]  
\[\kappa_{B}=x_{3}\circ N_{1}(y_{A})=x_{3}\circ N_{1}\circ N_{1}^{-1}\circ x_{4 }(x_{A})=x_{B}x_{A}.\]  
In this case, [PERSON] sending \(y_{B,1}\) means that \(n_{B}^{-1}\) must be a public key, although this element is supposed to be a secret; otherwise, [PERSON] cannot calculate \(y_{A}\). [PERSON] can easily calculate [PERSON]'s secret key \(x_{A}\) with \(n_{B}n_{B}^{-1}x_{A}=x_{A}\); thus, [PERSON] can recover the SSK by calculating \(y_{B,2}(x_{A})=x_{1}\circ x_{2}(x_{A})\). Without limiting this type of algorithm to be included in the SAPKA class, the main subclass that we attempt to construct in Section 5 can include weak algorithms. In this case, the subclass cannot be the one that we aim to construct.  
To limit algorithms such as the above example, we add restrictions on the construction of [PERSON]'s public keys using a map referred to as a \"non-easily invertible map\" with the following definition.  
**Definition 1**.: _The map \(f_{g}:\mathcal{S}\to\mathcal{S}\) is called as a non-easily invertible map if the calculation \(f_{g}^{-1}\circ f_{g}(y)\) for all \(y\in\mathcal{S}\) is difficult to compute in the mean of the computational complexity, and the order of complexity for computing \(f_{g}^{-1}\circ f_{g}(y)\)\((y\in\mathcal{S})\) is equal to or greater than \(O(2^{t(n)})\), where \(n\) is the bit size of \(y\) and \(t:\mathbb{N}\to\mathbb{R}^{+}\) is a monotonically increasing function:_  
\[t(n)=an\]  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Key** & **Parameter** \\ \hline \multirow{4}{*}{Bob} & Secret keys & maps \(x_{1},x_{2},x_{3},x_{4},N_{1}:\mathcal{S}\to\mathcal{S}\) and elements \(x_{B},n_{B}\in\mathcal{S}\) \\ \cline{2-3}  & Public keys & \(y_{B,1}(y)=N_{1}^{-1}\circ x_{4}(y)=n_{B}^{-1}y\)\((y\in\mathcal{S})\) \\ \cline{2-3}  & SSK & \(\kappa_{B}=x_{3}\circ x_{4}(x_{A})=x_{B}x_{A}\) \\ \hline \multirow{4}{*}{Alice} & Secret key & \(x_{A}\in\mathcal{S}\) \\ \cline{2-3}  & Public key & \(y_{A}=N_{1}^{-1}\circ x_{4}(x_{A})=n_{B}^{-1}x_{A}\) \\ \cline{1-1} \cline{2-3}  & SSK & \(\kappa_{A}=x_{1}\circ x_{2}(x_{A})=x_{B}x_{A}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Complete list of key of example algorithm of SAPKA.  
_for some \(a\in\mathbb{R}^{+}\setminus\{0\}\)._  
\(O\) of this definition is [PERSON]'s big-O notation (Definition 5 in Section 4.1). We limit [PERSON]'s public keys \(y_{B,1}\) and \(y_{B,2}\) to be constructed as  
\[y_{B,1}(y)=N_{1}^{-1}\circ x_{4}(y)=f_{g}\circ N_{1}^{\prime-1}\circ x_{4}^{ \prime}(y)\]  
\[y_{B,2}(y)=x_{1}\circ x_{2}(y)=f_{g}\circ x_{1}^{\prime}\circ x_{2}^{\prime}(y)\]  
for certain non-easily mapped \(f_{g}:\mathcal{S}\to\mathcal{S}\) and certain maps \(x_{1}^{\prime},x_{2}^{\prime},x_{4}^{\prime},N_{1}^{\prime}:\mathcal{S}\to \mathcal{S}\). By doing so, attacks from [PERSON] cannot be performed within a polynomial time. Furthermore, with several additional restrictions in Section 5, Requirement 2 of Section 2.1 can be achieved.  
We attempt 4. of the method mentioned in Section 2.2 within this restricted SAPKA class with a non-easily invertible map (the explicit definition of this restricted SAPKA class by a non-easily invertible map is also provided Section 5).