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?
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, 2021 at 6:35
-
$\begingroup$ yes that is what i mean. Where x is less than n/2. $\endgroup$– JamDiveBuddyAug 4, 2021 at 19:55
-
2$\begingroup$ Please edit the question clarifying that $\endgroup$– kodluAug 4, 2021 at 20:21
-
$\begingroup$ This is sort of ill defined, since $[x]P = [x+n]P$. (@fgrieu's definition is ok though) $\endgroup$– FractaliceAug 8, 2021 at 7:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\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, 2021 at 9:59