If I have a scalar $x$ and point $B$, then I can compute $X = f(x,B)$

If the function $f$ is point multiplication, i.e. $f(x,B) = x \cdot B$, then $B$ can be determined if $X$ and $x$ are known.

Under the circumstances where $x$ and $X$ will be known, is it possible to modify the function $f$ such that $B$ cannot be determined?

It is necessary that:

  1. the function $f$ is commutative, i.e. $f(x, f(y, B)) = f(y, f(x, B))$

  2. $X$ cannot be determined from $x$.

  3. If many pairs of ($x$, $X$) are given out, it cannot be inferred that any two of the pairs were created using the same base point $B$, even if $B$ is not itself determinable.

Edit: It would be fine to limit our choice of $x$ if that would prevent $B$ from being determined.

Edit: The curve used is ed25519

  • $\begingroup$ Why did you delete your previous (almost identical) question? $\endgroup$ – yyyyyyy Feb 9 '17 at 18:18
  • $\begingroup$ I realised the last question was a total mess. Hopefully this question makes things much clearer. $\endgroup$ – knaccc Feb 9 '17 at 18:20

If you're not tied to EC, here's one easy method: let $N$ be a composite number of unknown (secret) factorization; then:

$$f(x, B) = B^x \bmod N$$

is both uninverible, and commutative. If $f$ needs to be a permutation (that wasn't specified), then we can select the factors $p, q$ of $N$ s.t. $p-1, q-1$ have no small odd factors (and restrict the allowable values of $x$ to small odd values $>1$).

If you absolutely have to do EC, well, the obvious approach would be to actually use a pseudocurve (that is, do the EC operations in the standard way, but work on a ring rather than a field), with the ring being (yes, you guessed it) the integers modulo $N$ (where the factorization of $N$ is secret). Yes, an operation may fail, but if the factors of $N$ are large enough, this will practically speaking never happen. $N$ needs to be large enough so that directly factoring $N$ is infeasible (which means it's much larger than moduli we normally do EC in), however it would appear to meet your requirements. Note that point counting on a pseudocurve doesn't work (or so we hope; if it did, then we could factor), and hence the standard way of inverting point multiplication (which involves finding the multiplicative inverse modulo the order of the curve) is unusable.

| improve this answer | |
  • $\begingroup$ Thanks for your answer! The hope is for the trapdoor function that prevents x from being determined from X to be as good as the trapdoor function that EC provides. $\endgroup$ – knaccc Feb 9 '17 at 18:50
  • $\begingroup$ I've just added an edit to the post, specifying a requirement that it cannot even be determined if the same base point has been used between pairs of (x, X). Does your solution meet this requirement? $\endgroup$ – knaccc Feb 9 '17 at 18:55
  • 1
    $\begingroup$ @knaccc: not quite, if $x, y$ are both odd, someone could check the Jacobi symbol of $f(x, B), f(y, C)$, and have a decent chance to determine that $B \ne C$ if that's in fact the case. One obvious fix to that would be to make it $f(x, B) = B^{2x} \bmod N$; that does mean that $f$ is not a permutation. Alternatively, one could restrict allowable values of $B$ to values with Jacobi symbol 1. $\endgroup$ – poncho Feb 9 '17 at 19:04
  • $\begingroup$ Thank you so much @poncho - I will show you answer to some more people who will be able to help me understand the implications of what you've said better. Much appreciated. $\endgroup$ – knaccc Feb 9 '17 at 19:04
  • 1
    $\begingroup$ @knaccc: actually, in this case, EC would not keep the key size down; as I mentioned in the answer, we would need a large pseudocurve (to make the factorization of N problem difficult); perhaps 2048 bits... $\endgroup$ – poncho Feb 10 '17 at 13:44

This was too long for a comment.

If the function f is point multiplication, i.e. $f(x,B)=x\cdot B$, then $B$ can be determined if $X$ and $x$ are known.

This is not true. A counter-example: a standard result says that an elliptic curve has exactly 3 points of order 2. Now take $X=\mathcal{O}$ (the neutral element), and $x=2$.

| improve this answer | |
  • $\begingroup$ Hi, thanks for your comment. Please could you clarify: are there lots of cases where B cannot be determined? If so, this problem could be solved by limiting the choice of x or B? $\endgroup$ – knaccc Feb 9 '17 at 23:07
  • $\begingroup$ @knaccc If you work over a finite field, it depends on the number of points on the curve defined over the field. The multiplication by $x$ will be invertible when it is co-prime to this order. So the more composite your order, the more the above behaviour will happen. If it is prime, it is only rarely not invertible: when $x$ is a multiple of the group order. $\endgroup$ – CurveEnthusiast Feb 10 '17 at 7:37

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.