# An Improved Multi-Chaotic Public Key Algorithm Based on Chebyshev Polynomials
## 2 Preliminary
### Security Analysis of the Algorithm Above  
The Bose algorithm (RMPKC) combines the Diffie-Hellman protocol framework. The authors of Reference [53] point out that attacking this algorithm is equivalent to solving the Diffie-Hellman problem, and the difficulty is \((NP)^{\widetilde{m}}\), where \(N\) and \(P\) represent the key space size and the complexity of the linear transformation, respectively. However, the algorithm still has the following shortcomings [28]:  
Let \(C\) be a complex field, and \(C^{n}\) be the \(n\)-dimensional vector space of \(C\). At this point, the linear transformation \(f_{1}(x),\;\;f_{2}(x)\) can be represented as \(f_{1}(x)=x\cdot L\), \(f_{2}(x)=x\cdot R\). Since \(f_{1}\circ f_{2}=f_{2}\circ f_{1}\), this means that \(LR=RL\); therefore,  
\[x_{nA}=x_{0}\cdot L^{n_{A1}}R^{n_{A2}}. \tag{15}\]  
1. If \(f_{1}(x)\) and \(f_{2}(x)\) are linear transformations on the vector space \(C^{n}\), it is difficult to choose suitable linear transformations \(f_{1}\) and \(f_{2}\), since \(f_{1}\circ f_{2}=f_{2}\circ f_{1}\) does not hold in this space. 2. Let \(A\) be any norm of \(\|A\|\), if \(\|L\|<1\) and \(\|R\|<1\), when \(n_{A1}\) and \(n_{A2}\) are two large integers, the statistical characteristics of the \(n\)-tuple vector \(x_{nA}\) are poor. In fact, in the instances given by [PERSON], despite \(x_{0}\) being secret, there are still potential security issues, such as when \(k>1\) and \(n\to 8,\;k^{n}\to 8\); when \(k<1\) and \(n\to 8,\;k^{n}\to 0\). This requires that \(n_{A}\) cannot be a large integer, otherwise the statistical characteristics of the public key will be compromised. Figure 7: Key exchange process of a multi-chaotic system. Although it is difficult for an attacker to infer the specific operational steps from the seed \(x_{0}\) to the public key \(x_{nA}\), they can still calculate \(|n_{A1}-n_{A2}|\) by conducting single-bit tests on [PERSON]'s pseudo-random sequence generator. Letting \(n_{0}\), \(n_{1}\) denote the number of 0s and 1s in an arbitrary bit sequence of length \(n\), the statistic is  
\[X=\frac{(n_{0}-n_{1})^{2}}{n}. \tag{16}\]  
This approximately follows a \(\chi^{2}\) distribution with 1 degree of freedom, so \(P(X<3.8415)>0.5\) and \(|n_{A1}-n_{A2}|<\sqrt{3.8415n_{A}}\). Let \(s=\left\lceil\sqrt{n_{A}}\right\rceil\), then \(|n_{Ai}-\left[0.5n_{A}\right]|<\sqrt{3.8415n_{A}}/2<s,i\in\{1,2\}\). Furthermore, based on Equation (15), we have  
\[x_{nA}=x_{0}\cdot(LR)^{\left\lfloor 0.5n_{A}\right\rfloor}L^{\xi}R^{\xi}, \tag{17}\]  
where \(\xi=n_{A1}-\left\lfloor 0.5n_{A}\right\rfloor\), \(\xi=n_{A2}-\left\lfloor 0.5n_{A}\right\rfloor\), such that \(\xi,\zeta\in\{0,\pm 1,\cdots,\pm s\}\). We can see that the algorithm provides three design parameters: the size \(N\) of the key, the computational complexity \(P\) of linear functions, and the number \(\widetilde{m}\) of linear functions. By analyzing the properties of the \(\widetilde{m}\)-CS pseudo-random sequence generator, we deduce that the computational degree of the algorithm is \((NP/\widetilde{m})^{\widetilde{m}}\), which is lower than \((NP)^{\widetilde{m}}\). In fact, the attacker can be computed as  
\[x_{i,\ i_{1},\ \cdots,\ j_{\widetilde{m}}}=f_{1}^{i+i_{0}}f_{2}^{i+i_{1}} \cdots f_{\widetilde{m}}^{i+i_{m}}(x_{0}), \tag{18}\]  
where \(i\in\left\{1,2,\cdots,\left\lfloor n_{A}/\widetilde{m}\right\rfloor\right\}\), \(i_{k}\in\{0,1\}(k=1,2,\cdots,\left\lceil\sqrt{N}\right\rceil)\). Based on \(x_{n_{A}}\in\left\{x_{i,\ i_{1},\ \cdots,\ j_{\widetilde{m}}}\right\}\), the computational complexity of breaking the private key \(n_{A}\) can be calculated as  
\[C_{break}\leq\sum\
olimits_{i=1}^{\left\lfloor N/\widetilde{m}\right\rfloor} iP\cdot\widetilde{m}\cdot N^{0.5\widetilde{m}}. \tag{19}\]  
4. Since it requires step-by-step adaptation to the selection rules, Alice cannot use a fast algorithm to encrypt messages. Nonetheless, the attacker can estimate \(n_{A}\) and calculate the weight of the matrix through a sum of squares algorithm.