How to determine whether a point is greater than n/2?

JamDiveBuddy

12/4/22, 6:18 AM

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?

1 + 4

elliptic-curves

public-key

fgrieu

12/4/22, 6:35 AM

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$?

JamDiveBuddy

12/4/22, 7:55 PM

yes that is what i mean. Where x is less than n/2.

kodlu

12/4/22, 8:21 PM

Please edit the question clarifying that

Fractalice

12/8/22, 7:53 AM

This is sort of ill defined, since $[x]P = [x+n]P$. (@fgrieu's definition is ok though)

Score:4

Crypto

poncho

12/8/22, 3:11 AM

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.

0 + 1

István András Seres

12/8/22, 9:59 AM

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.