ECC twin diversify

Question

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?

Answer 1

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 $P'$ that is diversified from the current public key $P$ with $u$ and $v$ will be $$P' = [u]P + [v]G$$ and the diversified private key will be

$$d' = (d \cdot u + v)$$ and verification 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 negligible ( it 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$.

Can I connect my identity to another one?

Connecting a random identity with your initial identity is equal to a Discrete logarithm problem since we don't know the private key.

If we know the privates key $d$ and $d'$ then the twin diversity connection is a trivial task. Generate a random $u$ then solve for $v$;

$$v = d' - d \cdot u $$

---

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