Can two different hash function create two unlinkable `ed25519` keys from the same randomness?

Question

Assume the following scenario:

1. Alice has access to 32 bytes of true randomness $s$.
2. Alice hashes $s$ with SHA-512, and uses the resulting hash as the secret $d_{A}$ for Ed25519. Assume number-clamping and so on are correctly implemented.
3. Alice hashes $s$ with a different hash function, say BLAKE-2, or hashes $s$ two times with SHA-512, and uses the result as the secret key $d_{A'}$ for Ed25519.

Assume a random oracle model and the hardness of the discrete logarithm. Then:

1. Can the resulting two public keys be linked to both belong to Alice?
2. Can the resulting two public keys somehow be used to retrieve the resulting secret keys?

It seems to me it would be better to use one CSPRNG here and output enough randomness for two Ed25519 keys. But I also cannot identify any issues in the approach above.

Answer 1

Hash functions are candidates for random oracles. SHA-3 and BLAKE2 are close to being one but not SHA-512 since it has a length extension attack that we don't expect from a RO.

The different hash functions already produce different outputs even SHA-512 and its truncated version SHA-512/256 since their initial values are different.

Actually, you don't need two hash functions to achieve what you want. You can use one hash function to separate the domains with initial prefixes. Use BLAKE2 or SHAKE256.

Hashing to Elliptic Curves, ietf draft gives a nice definition of domain separation;

Cryptographic protocols that use random oracles are often analyzed under the assumption that random oracles answer only queries generated by that protocol. In practice, this assumption does not hold if two protocols query the same random oracle. Concretely, consider protocols $P1$ and $P2$ that query random oracle $R$: if $P1$ and $P2$ both query $R$ on the same value $x$, the security analysis of one or both protocols may be invalidated.

A common approach to addressing this issue is called domain separation, which allows a single random oracle to simulate multiple, independent oracles. This is effected by ensuring that each simulated oracle sees queries that are distinct from those seen by all other simulated oracles. For example, to simulate two oracles $R1$ and $R2$ given a single oracle $R$, one might define

$$R1(x) := R(\text{"R1"} \mathbin\| x)$$ $$R2(x) := R(\text{"R2"} \mathbin\| x)$$

In this example, $\text{"R1"}$ and $\text{"R2"}$ are called domain separation tags; they ensure that queries to $R1$ and $R2$ cannot result in identical queries to $R$. Thus, it is safe to treat $R1$ and $R2$ as independent oracles

1. Can the resulting two public keys be linked to both belong to Alice?

No, as long as the hash function is secure like SHA3. BLAKE2/3, SHAKE. Use;

1. $d_A = \operatorname{BLAKE2}(\texttt{Key A}\mathbin\|s)$
2. $d_{A'} = \operatorname{BLAKE2}(\texttt{Key A prime}\mathbin\|s)$

2. Can the resulting two public keys somehow be used to retrieve the resulting secret keys?

Curve25519 is a secure curve against the classical Discrete Log (DLog). It has around 126-bit security against classical DLog.

Note that with a Cryptographic Quantum Computer (CQC) built for Shor's period funding algorithm, elliptic curve discrete logarithm will not be safe. However, hash functions of size larger than 384 output will be secure against Grovers's or Brassard et al.'s method.

Therefore, the secret is secure against classical and CQC, however, the private keys are not secure against CQC.

---

Note that, you also benefit from Twin Diversify to link two public keys to achieve some anonymity and later you can prove that they belong to you without revealing your secret.

Answer 2

In the random oracle model this is safe to do because you can use a single oracle $\mathcal{O}$ and use domain separation to obtain two independent oracles from it (e.g. $\mathcal{O}(1 \parallel \cdot)$ and $\mathcal{O}(2 \parallel \cdot)$, where $\parallel$ denotes concatenation). Then you can consider the outputs to be totally independent from each other.

So in practice, it really comes down to which hash function you use. As long as it is a good RO candidate (like SHA-3 for example), it can be used in the same way: $$x_1 = H(1 \parallel s)\\ x_2 = H(2 \parallel s)$$

Because the two secrets produced are independent, the answer to both questions 1 and 2 is: no. Whether or not the individual secret keys can be retrieved from the public keys (for example, in finite field or elliptic curve crypto) is exactly the DLP, so as long as you use the secrets in a secure scheme, that would not be possible. The only way to link the two would be for the original seed randomness $s$ to be revealed - then anyone could re-compute the two individual keys and see that they did indeed match. Otherwise, even if the two individual secrets were leaked (for example, if the DLP was broken), they couldn't be linked back to $s$ or each other due to the one-wayness (pre-image resistance) of the hash function.