# It is possible to prove that two private keys are related?

Say Alice owns two keypairs: ($$Pub_1$$, $$Priv_1$$) and ($$Pub_2$$, $$Priv_2$$).

The pair ($$Pub_1$$, $$Priv_1$$) is pretty mundane.

$$Priv_2$$ was intentionally created by Alice by concatenating $$Priv_1$$ and the word "banana" (and then she derived $$Pub_2$$ out of $$Priv_2$$ the usual way).

Bob knows the public keys.

In any asymmetric key algorithm, is it possible for Alice to prove that $$Priv_2$$ = $$Priv_1$$ + "banana"? — without revealing the private keys?

• Apple did this for diversifying and anonymity as twin diversify Jan 11 at 6:18
• @knaccc The problem is described here. You're very welcome to comment on it and make suggestions. Jan 11 at 23:25

Let's say you use Curve25519, which has a well-known generator point $$G$$ which forms a cyclic group of size $$\ell$$. Valid scalars (private keys) are usually expressed as unsigned little-endian 32-byte sequences.
The ASCII bytes of $$\texttt{banana}$$ interpreted as a little-endian number is $$107126708920674$$.
If you append the ASCII bytes of $$\texttt{banana}$$ to a 32-byte (256-bit) little-endian private key, what you are mathematically doing is adding $$x$$ where $$x = 107126708920674 \cdot 2^{256}$$. Because this private key will exceed the group size $$\ell$$, an elliptic curve library will only accept it as a private key after it has been reduced $$mod\ \ell$$.
Therefore the concatenation with $$\texttt{banana}$$ means you have $$priv_2 = priv_1 + x\ mod\ \ell$$.
Anyone can easily observe that $$pub_2 == pub_1 + x \cdot G$$, which could only have happened if you had either added $$x$$ to $$priv_1$$, or added $$x + n \cdot \ell$$ for some value of $$n$$.