# 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. 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? 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$. 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. 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. Apr 2 at 17:51

The procedure that Mike Kaye suggested works; the other method would be to select a random value, and then use a Hash-to-Curve method to translate that random value to a point; they have been designed so that the order of that generated point is unknown.

• There's room for expanding the answer on Hash-to-Curve. I find it nontrivial to extract the method(s) from the linked draft RFC. Also, the RFC "first hashes the input byte string to produce a uniformly random byte string", which silently assumes the input varies and is not handpicked, something I haven't found stated nearby, thus I'm not taking for granted that the rest if airtight.
– fgrieu
Apr 1 at 6:36

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 Apr 1 at 8:07
• Also: the method uses "rejection sampling". It's hard to make a constant-time implementation of that, and some state that might matter in the context (ask why to them, not me; I've learned the hard way that when there's a requirement in a standard, the path of least resistance is to comply when possible, even if the rationale is unstated, lost, and the requirement demonstrably not useful in the situation at hand).
– fgrieu
Apr 1 at 8:14