# 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 "throwing away" $$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 "fake" 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 "throw away" the value of $$a$$ after generating $$Q$$). This is all to ultimately enable "playing poker over the phone".

• Like this one Generating a random point on an elliptic curve over a finite field? 2. method. – kelalaka Feb 15 at 19:15
• Will that method yield $Q$'s that are uniform over the the valid $Q$'s that would be generated as $a\cdot G$? Also, will that method be inefficient, in particular, because of rejecting invalid $x$'s? – chausies Feb 15 at 19:22
• Since there are multiple parties involved, you can have the first party generate a random $U$ (it won't matter how it's generated). The second party multiplies $U$ by a random value and returns $Q$ = $[b]U$. Neither party knows what to multiply $G$ by to get $Q$. – Aman Grewal Feb 15 at 19:24
• Yes, it will be uniform. Yes, SageMath already uses this. The theory is the number of points and the number of possible coordinates. – kelalaka Feb 15 at 19:26
• @AmanGrewal Your solution needs to assume that the second party is an honest actor or that they provide a zero-knowledge proof that they know $b$. Otherwise they could simply ignore $U$ and return a value of their choice. – Daniel Shiu Apr 2 at 17:51

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$$.
• In general elliptical curves used in cryptography the generator $G$ does not generate all possible points on the curve. So you need to multiply your point by co-factor which you forgot to mention – Manish Adhikari Apr 1 at 8:07