Reconsider PRG choice

[simon-friedberger]

If we reconsider our choice of PRG we should take into account that:

• The RNG is modeled as a random oracle in the proofs but this does not necessarily mean that we need a XOF. It might be more efficient to create a seed using something like SHA-3 (or -2) and then applying a fast AES based stream derivation.
• cSHAKE (which we are currently using) was only defined in NIST SP 800-185 not the original SHA-3 standard (FIPS 202) so it might not be available in some implementations. FIPS 202 has SHAKE which is also a XOF and we are already defining how to encode the binding string. We could simply define something similar to cSHAKE based on SHAKE. (Exact match is not possible due to non-matching constants.)

[cjpatton]

Thanks for kicking off this discussion, Simon! Here are my personal views on these points at the moment.

* The RNG is modeled as a random oracle in the proofs but this does not necessarily mean that we need a XOF. It might be more efficient to create a seed using something like SHA-3 (or -2) and then applying a fast AES based stream derivation.

In my opinion, more security analysis is required before we consider this change. I think it would be sufficient to prove that PrgFixedKeyAes128 is indifferentiable from a random oracle when SHA-3 (or SHA-2) is modeled as a random oracle and fixed-key AES is modeled as a random permutation (or perhaps ideal cipher). Currently this is is only known to be correlation-robust (see Section 7.4 of this paper). Alternatively, we could revisit the security proofs for Prio3 and see if we can push through the reduction with a function that is only correlation-robust.

Regarding performance: PrgFixedKeyAes128 is much faster than PrgSha3. (Incidentally, @divergentdave it would be great to have libprio benchmarks for this, if we don't already!) However, whether we need this speed up depends on how we use the PRG: for Prio3 the sharding/prep times are very similar with both, since the runtime is dominated by finite finite arithmetic; but for things that use the IDPF, like Poplar1, the performance difference is quite significant, since the runtime is dominated by the PRG. (See preliminary benchmarks in #106 for details.) In fact, this is exactly why we wanted FixedKeyAes128. (See #32.)

* cSHAKE (which we are currently using) was only defined in NIST SP 800-185 not the original SHA-3 standard (FIPS 202) so it might not be available in some implementations. FIPS 202 has SHAKE which is also a XOF and we are already defining how to encode the binding string. We could simply define something similar to cSHAKE based on SHAKE. (Exact match is not possible due to non-matching constants.)

This sounds reasonable. We used cSHAKE128 because (1) we need an XOF and (2) there is baked in domain separation for the customization and binder strings. All we would need to do to go to SHAKE128 is roll this domain separation bit ourselves.

[cjpatton]

A couple of additional options to flag here:

1. David Benjamin reminded me of expand_message_xmd from the hash-to-curve draft, which seems fine at least from a security perspective: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#section-5.3.1
2. TurboSHAKE has recently been endorsed for use in Kyber. If this becomes the standard, then most, if not all, cryptographic libraries are going to need first class support for it: https://mailarchive.ietf.org/arch/msg/cfrg/bwSH21YPUgdten9ztsuNrL7XfZI/

[cjpatton]

I'd like to plan to replace cSHAKE128 with SHAKE128 in the next draft (draft-07). I think I'd like to get feedback from CFRG on whether to use SHA2 (via expand_message_xmd), stick with SHA3, or use TurboSHAKE.

[cjpatton]

This is superseded by #299.