# EC: How to prevent discovery of base point after commutative operation

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

• Why did you delete your previous (almost identical) question? – yyyyyyy Feb 9 '17 at 18:18
• I realised the last question was a total mess. Hopefully this question makes things much clearer. – 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.

• 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. – knaccc Feb 9 '17 at 18:50
• 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? – knaccc Feb 9 '17 at 18:55
• @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. – poncho Feb 9 '17 at 19:04
• 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. – knaccc Feb 9 '17 at 19:04
• @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... – 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$.

• 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? – knaccc Feb 9 '17 at 23:07
• @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. – CurveEnthusiast Feb 10 '17 at 7:37