# Can we break ECDLP with this machine?

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Also we have a machine that is able to leak some information about $k$. If $k$ be an odd number this machine say $k$ is odd, else return two points $\frac{k}{2}\cdot P$ and $P'$ such that $2\cdot P'=Q$. Can we find $k$ with this machine? Other question is can we know that is $k$ divisible by other prime number?

• Dear poncho, when some peoples look at the easy problem, they don't think about hard problems behind it. Maybe the answer of this problem is evident (no) , but are you think about difference between $\frac{k}{2} \cdot P ,P'$ and use of it for design ZK protocols? – Meysam Ghahramani Jan 12 '16 at 21:39
• The problem might be easier if you consider a more limited machine (Oracle); suppose that you had an Oracle that, given $P$ and $Q = kP$ (with $0 \le k < n$ where $n$ is the order of the point $P$), told you if $k$ was even or odd (and nothing else). With such an Oracle, could you recover $k$? If so, how? (Hint: how would you recover bit 1 of $k$?) – poncho Jan 13 '16 at 5:12