How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key Given an elliptic curve with generator $G$, is it possible to generate a random point on the curve $Q = a \cdot G$ without knowing the secret value $a$ that generated it? Note that just using an $a$ to generate $Q$, and then &quot;throwing away&quot; $a$ (forgetting about it) isn't a valid solution. Also note that $Q$ should be uniformly distributed over all valid values (i.e. as if $a$ was chosen uniformly between 0 and $n-1$).
A toy application I have is about making some &quot;fake&quot; Diffie–Hellman secret exchanges, where 1 party can't get to the secret because they don't know their key $a$ (and weren't just be trusted to &quot;throw away&quot; the value of $a$ after generating $Q$). This is all to ultimately enable &quot;playing poker over the phone&quot;.
Pick a random $x$ value. Calculate $y^2 = x^3+ax+b \bmod p$. Then try to form $y$ by taking the square root $\bmod p$. If the square root fails then no $(x,y)$ pair exists on the curve. If the square root works, flip a coin; if tails form $y = p-y \bmod p$.
This is how public key compression works. Only the low bit of y is saved. Form $y^2$, take the square root (which had better work). If the low bit of $y$ is wrong then form $y = p-y$.