ECC twin diversify

During my implementation of CommonCrypto from iOS, I noticed there is a function called CCECCryptorTwinDiversifyKey whose description is:

Diversifies a given EC key by deriving two scalars $$u,v$$ from the given entropy.

But the description left me guessing at what the function does or when it is used. Looking for "EC diversify" and "EC twin diversify" on the internet gave me no hits either. So my question is: What is twin diversifying when talking about EC keys and when is it used?

The Twin Diversify

There is only one source that I could find; the open-source of Apples' CommonCrypto. All from CommonECCryptor.h

@function   CCECCryptorTwinDiversifyKey

@abstract   Diversifies a given EC key by deriving two scalars u,v from the
given entropy.

@discussion entropyLen must be a multiple of two, greater or equal to two
times the bitsize of the order of the chosen curve plus eight
bytes, e.g. 2 * (32 + 8) = 80 bytes for NIST P-256.

Use CCECCryptorTwinDiversifyEntropySize() to determine the
minimum entropy length that needs to be generated and passed.

entropy must be chosen from a uniform distribution, e.g.
random bytes, the output of a DRBG, or the output of a KDF.

u,v are computed by splitting the entropy into two parts of
equal size. For each part t (interpreted as a big-endian number),
a scalar s on the chosen curve will be computed via
s = (t mod (q-1)) + 1, where q is the order of curve's
generator G.

For a public key, this will compute u.P + v.G,
with G being the generator of the chosen curve.

For a private key, this will compute d' = (d * u + v) and
P = d' * G; G being the generator of the chosen curve.


Use cases

Diversification is necessary when we want some level of anonymity, that is like in CryptoCurrencies, if you use the same public key you are linked all the time. If you can diversify your public key with your private/public key, then you are able to use the diversified new identity and you cannot be easily linked with your original identity.

In the above scheme, the new public key that is diversified with $$u$$ and $$v$$ will be $$[u]P + [v]G$$ and the diversified private key will be

$$d' = (d \cdot u + v)$$ and verificatiom the diversified public key

$$P' = [d']G = [d \cdot u + v]G = [d \cdot u]G + [v]G = [u]P + [v]G$$

In short, you have a new identity, but behind the curtain, it is still you.

How many people can safely diversify?

To answer we need some assumptions, let the users can generate $$u,v$$ uniform randomly - that is crucial -, there are $$2^{30}$$ user of the system - little over a billion -, and each user has diversified $$2^{20}$$ times in their lifetime - that is little above a million -.

Now we will use the classical birthday calculation to see the probability of a collision for a curve that can have around $$2^{256}$$ public keys.

We will use the fact that the probability of collision among uniform randomly selected $$k$$ elements in the set of $$n$$ elements can be approximated by

$$(2^{k})^2/2^{n}/2=2^{2k-n-1}$$

Our $$k = 2^{50}$$ and $$n = 2^{256}$$, then;

$$(2^{50})^2/2^{256}/2 = 2^{100 - 256 - 1} = 1/2^{157}.$$

When the collision probability is around $$1/2^{100}$$ we simply say that it is not going to happen. Therefore a collision is not going to happen for 256-bit Curves like P-256 or Curve25519.

What is the advantage of this instead of just creating a new identity?

The main difference is that you can easily prove that this identity is connected to the initial identity by providing the $$u$$ and $$v$$. Connecting a random identity with your initial identity is equal to Dlog problem.

Note: I couldn't find the academic paper behind this idea. I would be glad if anyone tells.

• Is there a limit as to how many times this can be performed? And what should I do with my 'original' key? Should I discard/overwrite it, or should I keep access to all created keys? – Bram Nov 10 '20 at 14:04
• Makes sense. What about the 'storage' of the key. Should I keep track of the old ones, or should I discard/overwrite them? – Bram Nov 10 '20 at 14:35
• @Bram that is depends on your need. If you generate for one time usage than after the usage, no need to store. – kelalaka Nov 10 '20 at 14:37
• @Bram I hope the formalization in the extended answer satisfies your first comment. – kelalaka Nov 10 '20 at 16:33