5
$\begingroup$

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

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

2 Answers 2

Reset to default
1
$\begingroup$

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
$\endgroup$
9
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 13:44
1
$\begingroup$

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
$\endgroup$
2
  • $\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, 2017 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, 2017 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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