4
$\begingroup$

I'm having trouble understanding the solution to a problem that tries to solve the discrete logarithm problem over an elliptic curve. It goes as follows:

Consider an elliptic curve P256 generated by $G$ with size $n$. Consider function $H:P256 \rightarrow \mathbb{Z}_n$ that is used to build a random walk $P(i)$ as follows: $P(i) = W(P(i-1))$ with $W(P) = P + H(P)G$. Finally, consider a distinguisher function $D: P256 \rightarrow \{0,1\}$ (if $D(P) = 1$ we say that P is a distinguished point). Assume for all P and P' that $H(P)$ is independent from $D(P')$, $H(P)$ is uniformly distributed and $P[D(P') = 1] =\frac{1}{t}$.

Consider the following algorithms:

Precom(t,m) -> L
for i = 1,...,m 
 take P_0 = aG with a random
 compute P(0),...,P(l-1)
 until P(l-1) is in the set P(0),...,P(l-2) or D(P(l-1)) = 1
 if P(l-1) is in the set P(0),...,P(l-2) abort else add to L (P(l-1),log)

Dlog(Q) 
loop
 set P(0) = aG+Q
 compute P(0),...,P(l-1)
 until P(l-1) is in the set P(0),...,P(l-2) or D(P(l-1)) = 1
 if P(l-1) is not in the set P(0),...,P(l-2) then 
  (if (P(l-1),b) is in L then stop)
endloop

The question I'm trying to solve goes as follows:

We assume that Dlog never finds a looping random walk (the condition "until $P(l-1)$ is in the set $P(0),\dots,P(l-2)"$ is never satisfied). We further assume that Precomp visited at least $\frac{nk}{t}$ points (for some value k, where t is the parameter of the algorithm). Show that the expected number of iterations of the loop in Dlog is at most $1+\frac{1}{k}$.

I even have the answer:

An iteration repeatedly picks a new point. If new, this new point is distinguished with probability $\frac{1}{t}$. But the point is not new with probability at least $\frac{\text{number of visited}}{n} \ge k\frac{1}{t}$. So, each new point has a probability to be new and distinguished with less than $\frac{1}{k}$ times the probability of being not new. So, we reach a distinguished point from $L$ with probability at least $\frac{k}{k+1}$ and iterate with a probability less than $\frac{1}{k+1}$. So, the expected number of iterations is at most $1+\frac{1}{k}$.

What do I not understand from this answer? Well for starters how are they calculating the expectation? But the whole process is quite obscure. Also if you could comment on the usefulness of conditions of the kind:

Assume for all P and P' that $H(P)$ is independent from $D(P')$, $H(P)$ is uniformly distributed and $P[D(P') = 1] =\frac{1}{t}$.

would be useful for me because I find them in many problem statements and I'm not always sure where I am using them.


Please feel free to enhance my $\LaTeX$ where needed. Also, if there is something you do not understand, don’t hesitate to post a comment asking for clarification. In case of doubt, you can see also take a look at the PDF describing the complete problem.

$\endgroup$
  • $\begingroup$ Please copy the text exactly; what you have wriiten sometimes doesn't make sense. $\endgroup$ – fkraiem Jan 14 '17 at 0:25
4
$\begingroup$

I hope I interpreted this correctly, as both the question here and the pdf are not completely clear to me. As the question seems to do, I will everywhere assume that the chosen walks are completely random.

The idea is that we are going to run the ${\tt Dlog}$ function, and we want to know the expected value of the number of times we have to iterate its loop. Suppose we start a loop, and we have chosen points $P_0,\ldots,P_{\ell-1}$. Three things can happen:

  1. We have seen the point $P_{\ell-1}$ before.
  2. We have not seen the point $P_{\ell-1}$ before, and the point is distinguished.
  3. We have not seen the point $P_{\ell-1}$ before, and it is not distinguished.

This is an exhaustive list of options. Now let's suppose that if we are in 3, that we choose $P_{\ell}$ and continue the loop. Then after a while we are going to end up either in 1 or 2. This shows that every loop either ends up on a point which we have seen before (let's call this event $X$), or ends up on a point which we have not seen before, and the point is distinguished (let's call this event $Y$).

Estimating some probabilities:

Let's call $\mathcal{P}(X)=x$ and $\mathcal{P}(Y)=y$. Since these two options are exhaustive, we have $$x+y=1.$$ Since by assumption we visited at least $k\frac{n}{t}$ points, we have $$x\geq \frac{1}{n}\cdot k\frac{n}{t}=k\frac{1}{t}.$$ Moreover, suppose we visited $v$ points, then $$y=\frac{n-v}{n}\frac{1}{t}\leq\frac{1}{t}.$$ Combining the last two equalities, we conclude that $x\geq k\frac{1}{t}\geq ky$. Writing $x=1-y$, from this it follows that $1-y\geq ky$, and therefore that $y\leq\frac{1}{k+1}$. Thus $-y\geq\frac{-1}{k+1}$. From this we we have that $$x=1-y\geq1-\frac{1}{k+1}=\frac{k}{k+1}.$$ Finally we conclude that $$\frac{1}{x}\leq \frac{k+1}{k}=1+\frac{1}{k}.$$

The final argument:

So why did we do all of this. Well, we have defined a "successful" event, namely $X$, and an "unsuccessful" event, namely $Y$. How many times do we have to repeat before we end up in $X$? This is a standard geometric distribution with probability $x$. It has expected value $$\sum_{i=1}^{\infty}\left(i\cdot xy^{i-1}\right),$$ which is known to equal $\frac{1}{x}$. As $\frac{1}{x}\leq 1+\frac{1}{k}$, we are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.