1
$\begingroup$

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".

$\endgroup$
7
  • 1
    $\begingroup$ Like this one Generating a random point on an elliptic curve over a finite field? 2. method. $\endgroup$
    – kelalaka
    Feb 15 at 19:15
  • $\begingroup$ 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? $\endgroup$
    – chausies
    Feb 15 at 19:22
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 15 at 19:24
  • 1
    $\begingroup$ Yes, it will be uniform. Yes, SageMath already uses this. The theory is the number of points and the number of possible coordinates. $\endgroup$
    – kelalaka
    Feb 15 at 19:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – Daniel S
    Apr 2 at 17:51
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Apr 1 at 6:36
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 1 at 8:07
  • $\begingroup$ 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). $\endgroup$
    – fgrieu
    Apr 1 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.