While I was reading the paper entitled (http://dx.doi.org/10.1109/ISCAS.2003.1204947)
Kocarev, Ljupco, and Zarko Tasev. "Public-key encryption based on Chebyshev maps." Circuits and Systems, 2003. ISCAS'03. Proceedings of the 2003 International Symposium on. 2003.
I encountered a table, Table 1, on page III-30 which has bounded the values of two parameters as follows (N denotes the number of bits used in gnump to do multiprecision computations):
----------------------------------
| N-bit precision | $r_0$, $s_0$ |
----------------------------------
| 256 | ~ $2^{70}$ |
----------------------------------
| 512 | ~ $2^{190}$ |
----------------------------------
| 1024 | ~ $2^{450}$ |
----------------------------------
| 2048 | ~ $2^{970}$ |
----------------------------------
The chebyshev polynomials of the first type are defined recursively as $$ T_n(x) = 2xT_{n-1}(x) - T_{n -2}(x), \ \ n \geq 2 $$ by starting points $T_0(x) = 1$ and $T_1(x) = x$ for $n \in \mathbb{N}$ and $x \in [-1,1]$.
These parameters are bounded to make $T_{r_0}(T_{s_0}(x))$ without errors. This is where my question arises! How did they obtain this bound?
I understand that the result of multiplying these two numbers with certain bits should not exceed the precision, however, there is a gap, i.e. $70 + 70 = 140 < 256$.
Besides, the intuition of facing such a problem is as follows:
In this paper, there are two parties $A$ and $B$, who share a value $x \in [-1,1]$ and $B$ wants to send a message to $A$, using $A$'s public key, $(x, T_{s_0}(x))$. Note that $s_0$ is the $A$'s private key.
Party $B$ chooses a random $r_0$ as ephemeral key and then computes $Z = T_{r_0}(T_{s_0}(x))$ and encrypts a number like $M$ by $X = Z \times M$. Then, $(X, T_{r_0}(x))$ is sent as the encryption of $M$ to $B$.
Given that $A$ holds $s_0$, he can compute $Z' = T_{s_0}(T_{r_0}(x))$, which is equal to $Z$ by the semigroup property of Chebyshev. Then, he can recover $M$ by dividing $X$ by $Z'$.
If there are any errors in computing these values, the recovery of plaintext message fails!