1
$\begingroup$

How can we determine if a private key associated with a point, on an EC, is less than or greater than 1/2 $n$, where $n$ is the order?

$\endgroup$
4
  • 7
    $\begingroup$ The first step to determining something is defining it. How do you define that a point $P$ of the curve is "less than $n/2$"? Do you mean $\exists x\in\mathbb N$ with $x\cdot G=P$ and $x<n/2$, where $G$ is some given point of the curve? Or something else? In the first case, hint: what must be the cost of such algorithm relative to one finding $x$? $\endgroup$
    – fgrieu
    Aug 4 at 6:35
  • $\begingroup$ yes that is what i mean. Where x is less than n/2. $\endgroup$ Aug 4 at 19:55
  • 2
    $\begingroup$ Please edit the question clarifying that $\endgroup$
    – kodlu
    Aug 4 at 20:21
  • $\begingroup$ This is sort of ill defined, since $[x]P = [x+n]P$. (@fgrieu's definition is ok though) $\endgroup$
    – Fractalice
    Aug 8 at 7:53
4
$\begingroup$

How can we determine if a private key associated with a point, on an EC, is less than or greater than $1/2 n$, where $n$ is the order?

The obvious way is to compute the discrete log of the private key (achievable in $O( \sqrt{n} )$ steps, and compare.

In addition, it can be shown that there isn't a significantly cheaper way - given an Oracle that, given a point, computes where the discrete log is greater than or less than $1/2 n$, we can compute the discrete log with $\log_2{n}$ queries (plus some relatively cheap operations); hence this Oracle cannot be cheaper than $1 / \log_2{n}$ times as cheap as the above naïve approach.

$\endgroup$
1
  • $\begingroup$ Put differently, this is not possible unless DLog is easy. More formally, the most significant bit of the discrete logarithm is a hardcore bit [Blum-Micali '81]. Additionally, you could generate a PRNG from this hardcore bit. $\endgroup$ Aug 8 at 9:59

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.