daira
commented
4 years ago Section 3 of the Curve25519 paper is relevant:
Choice of key-derivation function. There are no theorems guaranteeing the safety of any particular key-derivation function H with, e.g., 512-bit output. Some silly choices of H are breakable. As an extreme example, if H outputs just 64 bits followed by all zeros, then an attacker can perform a brute-force [Daira: or Pollard lambda] search for those 64 bits. On the other hand, from the perspective of a secret-key cryptographer, it seems very easy to design a safe function H. A small amount of mixing, far less than necessary to make a safe secret-key cipher, stops all known attacks.
(The paper goes on to define a KDF based on Salsa20.)
In terms of attacks, the main threat seems to be generalized Pollard lambda attacks, based on using the structure of the resulting scalar (possibly in combination with endomorphisms) for a meet-in-the-middle attack. Here we have the advantage that the input to CRHivk is the representation of a tuple of random points (ak, nk), so for Tweedledee in place of Jubjub it would have roughly 508 bits of entropy, from the point of view of someone who does not have the full viewing key.
It's worth pointing out that CRH^ivk needs to be preimage-resistant if-and-only-if we require an authority separation between incoming viewing keys and full viewing keys. I think the intention is that the implementation of Sapling-on-Halo-2 in zcashd will only support full viewing keys.
The reason why we required a full cryptographic hash, BLAKE2s, for CRHivk in Sapling, was that:
- it's a conservative choice that is easy to prove secure (since the security argument can just treat it as a random oracle);
- we already required a collision-resistant PRF in the circuit for PRFnfSapling.
In Sapling-on-Halo-2 we want to make the circuit much smaller. That is, it should have many fewer rows than the Sapling circuit had R1CS constraints. This is expected to more than compensate for the fact that the cost per row to prove a circuit in Halo 2 will be higher than the cost per R1CS constraint in Groth16. (Also, the unbatched verification cost will be linear in the number of rows, although with a fairly small constant.) While it would be possible to improve the size of a BLAKE2s circuit using lookups, it's still not competitive with algebraic hashes.
We don't just need collision resistance, we also need pseudorandomness (i.e. suitability of the output as a Jubjub private scalar).