Learning a Sine-Wave

A few month ago, i locked up myself into a mental hole, by trying to solve or at least partially solve the following problem:

Problem-Definition. Assume you have a sufficient long integer interval $I=[0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \mathsf{sign}(\sin(2x\pi/p))$. Formulated in words, the set $Z$ contains the randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that point (i.e., the sign value). Find the secret parameter $p$.

# Heuristic argument #

It can be heuristically proved, that even as few as $m =\log p$ points should be enough to find a unique value for $p$. Imagine a random sine wave that is plotted along the interval $I$. Since the points $x_i$ are randomly chosen from $I$, the chance that a point $x_i$ is traversed by the sine wave equal to its assigned sign value is $1/2$. Hence, the chances that a random curves traverses all $m$ points correct is $(1/2)^m$.

But it seems one can not do better than $\mathcal{O}(p)$, that is exponential in $m$.

The described problem to learn the sine-wave, e.g., its parameter $p$, has relationships for example to Integer Factoring or to the Approximation GCD-Problem (e.g., can be used to attack the homomorphic encryption scheme of Dijk et al. [1])

Next, i will describe one of my approaches and what seems to be the limitations of this approach. 

# Approach 1 #

To approach a problem, it is always a good start to find easy cases. Then solve the problem for this cases and then try to determine what prevents the idea from working in the general case.

In our case, an easy case is when the elements of $Z$ are not randomly chosen, but are of the form $x_i = 2x_{i-1}$. In that case, we get a $\mathcal{O}(\log^2 p)$ algorithm that returns $p$.

The algorithm in this case is as follows: Assume that we have the set $$Z = \{(x_1,s(x_1)),(x_2,s(x_2)),...,(x_m,s(x_m))\}$$ with $x_i = 2x_{i-1}$. The sign value gives us the information if the residue $r_j$ from $r_j \equiv x_i \pmod{p}$ (we denote $r_j$ in the following with $[x_i]$) is:

1. less than $p/2$, i.e., $0 \leq r_j \leq p$, if $s(x_i) = 1$ 
2. larger than $p/2$, i.e., $p/2 \leq r_j < p$, if $s(x_i) = -1$. 

Now we list all four possible cases, between $[x_i]$ and $[x_{i-1}]$::

1. $[x_m] > p/2$ and $[x_m] \equiv 0\pmod{2}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/2$
2. $[x_m] > p/2$ and $[x_m] \equiv 1\pmod{2}$, $\Rightarrow$ $[x_{m-1}] > p/2$ and $[x_{m-1}] = ([x_m]+p)/2$
3. $[x_m] < p/2$ and $[x_m] \equiv 0\pmod{2}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/2$
4. $[x_m] < p/2$ and $[x_m] \equiv 1\pmod{2}$, $\Rightarrow$ $[x_{m-1}] > p/2$ and $[x_{m-1}] = ([x_m]+p)/2$

As one can see, the information if $[x_m]$ and $[x_{m-1}]$ are larger of less than $p/2$, is enough to deduce the parity of $[x_m]$. Remember, only $x_m$ is known and not $[x_m]$. That parity information allows the get the information how $[x_{m-1}]$ is obtained from $[x_m]$. That is either by dividing by $2$ or first adding $p$ and then divide by $2$.

This information, repeated $m$-times, allows to get $p$ for $m = \log^2 p$. Here is a little example:

We have $$Z = \{(26,1),(52,1),(104,1),(208,-1),(416,-1),(832,-1),(1664,1),(3328,1) \}$$ We start with $$ 0 \leq [x_m] = [3328] < p/2$$ It is $0 < [x_{m-1}] = [1664] < p/2$ since its sign-value is positive. So we know that $$ 0 \leq [3228]/2 = [1664] < p/4$$ The next sign-value is negative, hence we have to add $p$ and then divide by $2$: $$ p/2 \leq [3228]/4+p/2 = [832] < p/2 + p/8$$ The next sign-value is again negative, hence $$ p/2+p/4 \leq [3228]/8+p/4+p/2 = [416] < p/2 + p/4 + p/16$$ and again $$ p/2+p/4+p/8 \leq [3228]/16+p/8+p/4+p/2 = [208] < p/2 + p/4 + p/8 + p/32$$ The next three sign-values are positive, which are always simple divisions by $2$:
$$ \frac{p}{16}+\frac{p}{32}+\frac{p}{64} \leq \frac{[3228]}{128}+\frac{p}{64}+\frac{p}{32}+\frac{p}{16} = [26] < \frac{p}{16} + \frac{p}{32} + \frac{p}{64} + \frac{p}{256}$$
Next, we divide by $p$: $$ \frac{1}{16}+\frac{1}{32}+\frac{1}{64} \leq \frac{[3228]}{128p}+\frac{1}{64}+\frac{1}{32}+\frac{1}{16} = \frac{[26]}{p} < \frac{1}{16} + \frac{1}{32} + \frac{1}{64} + \frac{1}{256}$$ Finally, we have $$ \frac{1}{16}+\frac{1}{32}+\frac{1}{64} \leq  \frac{[26]}{p} < \frac{1}{16} + \frac{1}{32} + \frac{1}{64} + \frac{1}{256}$$ which is equal to $$\frac{[26]}{p} - \frac{7}{64} < \frac{29}{256}$$
If we have $m=\log^2(p)$ points, we could use the famous approximation result that if $$\left| k - \frac{p}{q}\right| < \frac{1}{2q^2}$$ holds, one can find $p/q$ among the, only polynomial many, fractional convergents of the fraction $k$. See for example Wiener's Attack on the RSA cryptosystem.

Tripled points. What goes wrong in the case $x_i = 3x_{i-1}$? Why exactly does the previous algorithm fail and could it be fixed?

Lets look what happens to our case distinction.

1. $[x_m] > p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
2. $[x_m] > p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $\color{red}?$
3. $[x_m] > p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $\color{red}?$
4. $[x_m] < p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
5. $[x_m] < p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $\color{red}?$
6. $[x_m] < p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $\color{red}?$

So the red question marks indicate, that this value is not yet determined.

To make any progress, we have to assume that we know the value $p\pmod{3}$, W.l.o.g. we set $p \equiv 1\pmod{p}$, hence

1. $[x_m] > p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
2. $[x_m] > p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $[x_{m-1}] = ([x_m] + 2p)/3$
3. $[x_m] > p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $[x_{m-1}] = ([x_m] + p)/3$
4. $[x_m] < p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
5. $[x_m] < p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $[x_{m-1}] = ([x_m] + 2p)/3$
6. $[x_m] < p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $[x_{m-1}] = ([x_m] + p)/3$

We still have $4$ question marks. Let us look at point 2. We know that $[x_m]$ is larger than $p/2$ and $[x_{m-1}]$ is obtained by $[x_{m-1}] = ([x_m] + 2p)/3$, hence we have $$[x_{m-1}] = ([x_m] + 2p)/3 = [x_m]/3 + 2p/3 > p/6 + 4p/6 = 5p/6 > p/2$$ So the question mark at 2. has to be replaced with $[x_{m-1}] > p/2$.

What about point 3.? We again know that $[x_m] > p/2$ and $x_{m-1}]$ is obtained by $[x_{m-1}] = ([x_m] + p)/3$, hence we have $$[x_{m-1}] = ([x_m] + p)/3 = [x_m]/3 + p/3 > p/6 + 2p/6 = 3p/6 = p/2$$ So the question mark at 3. has to be replaced also with $[x_{m-1}] > p/2$.

What about point 5.? We have now the case that $[x_m] < p/2$. And $[x_{m-1}]$ is obtained by $[x_{m-1}] = ([x_m] + 2p)/3$, hence we have $$[x_{m-1}] = ([x_m] + 2p)/3 = [x_m]/3 + 2p/3 < p/6 + 4p/6 = 5p/6$$
Here we have a problem. We dont know if $[x_{m-1}]$ is smaller or larger than $p/2$. All the information we get is that it is smaller than $5p/6$.

For completness, what about point 6.? We have again the case that $[x_m] < p/2$. And $[x_{m-1}]$ is obtained by $[x_{m-1}] = ([x_m] + p)/3$, hence we have $$[x_{m-1}] = ([x_m] + p)/3 = [x_m]/3 + p/3 < p/6 + 2p/6 = p/2$$
Here we succeed and the questionmark at 6. has to be replaced with $[x_{m-1}] < p/2$.

1. $[x_m] > p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
2. $[x_m] > p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $[x_{m-1}] > p/2$ and $[x_{m-1}] = ([x_m] + 2p)/3$
3. $[x_m] > p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $[x_{m-1}] > p/2$ and $[x_{m-1}] = ([x_m] + p)/3$
4. $[x_m] < p/2$ and $[x_m] \equiv 0\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = [x_m]/3$
5. $[x_m] < p/2$ and $[x_m] \equiv 1\pmod{3}$, $\Rightarrow$ $\color{red}?$ and $[x_{m-1}] = ([x_m] + 2p)/3$
6. $[x_m] < p/2$ and $[x_m] \equiv 2\pmod{3}$, $\Rightarrow$ $[x_{m-1}] < p/2$ and $[x_{m-1}] = ([x_m] + p)/3$

Nevertheless, also if we could replace the last questionmark, we are still facing the problem, that a combination of two successive sign-value, does not lead to a distinct residue class of $[x_m]$  modulo $3$. If for example we know that $[x_m] > p/2$ and $[x_{m-1}] > p/2$, then we are left with two cases, namely $[x_m] \equiv \pm 1\pmod{3}$.
It is not hard to imagine that this approach gets even worse if the ration $x_m/x_{m-1} > 3$ or is even in $\mathbb{Q}$. So probably this approach, dispite it is able to solve the named special case, does not generalize.

[1] Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan (2009-12-11). "Fully Homomorphic Encryption over the Integers" (PDF). International Association for Cryptologic Research. Retrieved 2010-03-18.