Re: [CFRG] Choice of XOF for draft-irtf-cfrg-vdaf

[Christopher Patton <[e-mail]>]

Thanks for the extra data point, David! From a perf perspective it seems
like TurboSHAKE128 is the right way to go.

There also doesn't seem to be demand for keeping SHAKE128. If there are no
objections, we'll replace SHAKE128 with TurboSHAKE128 in the next VDAF
draft.

Finally, there seems to be broad support for leaving room for cryptographic
agility in CFRG specs in general, though I didn't hear anyone request
additional algorithms for VDAF in particular. The spec is written in such a
way that adding support for a new XOF is as easy as defining a codepoint.
If someone wants support for SHAKE128, or maybe something built from
SHA256, feel free to send a PR.

Best,
Chris P.

On Fri, Oct 6, 2023 at 12:03 PM David Cook <dcook=
[e-mail]> wrote:

> I re-ran benchmarks of the Prio3SumVec VDAF on an Intel processor (Chris's
> benchmarking results were on ARM), and in this setting, using SHA-2 via a
> tweaked expand_message_xmd came out on top, a hair faster than TurboSHAKE.
> These results are from a "11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz"
> CPU with Turbo Boost turned off, using the commit
> https://github.com/divergentdave/libprio-rs/commit/522c10a13098097257a3feb20043eb68ed275784,
> and running "cargo bench --bench speed_tests -- prio3sumvec".
>
> Sharding:
> Measurement length SHAKE128 TurboSHAKE SHA-2 tweaked XMD
> 10 76.709 µs 60.280 µs 59.984 µs
> 30 100.22 µs 80.307 µs 79.026 µs
> 100 202.71 µs 169.21 µs 166.60 µs
> 300 466.39 µs 398.63 µs 308.37 µs
> 1000 1.8078 ms 1.6263 ms 1.4790 ms
>
> Preparation, initial step:
> Measurement length SHAKE128 TurboSHAKE SHA-2 tweaked XMD
> 10 53.616 µs 44.887 µs 44.728 µs
> 30 66.061 µs 55.320 µs 54.771 µs
> 100 104.70 µs 90.823 µs 89.803 µs
> 300 206.79 µs 180.94 µs 175.85 µs
> 1000 610.40 µs 539.43 µs 527.80 µs
>
> Looking at performance alone, replacing SHAKE128 with this mode of SHA-2
> would be an improvement on x86, and a regression on ARM, while TurboSHAKE
> would be an improvement on both architectures (with the Rust libraries this
> implementation is currently using).
>
> --David Cook
>
> On Tue, Sep 26, 2023 at 6:18 PM Christopher Patton <cpatton=
> [e-mail]> wrote:
>
>> Hi all,
>>
>> The authors of the VDAF draft need feedback on one of our open design
>> questions, first raised in [1]. To summarize: we're currently using
>> SHAKE128 (SHA-3) as an XOF ("eXtendable Output Function"), but we've heard
>> from potential adopters off-list that they'd prefer not to have to support
>> SHAKE128. We'd like to find an alternative that most people are happy with.
>>
>> The most natural alternative that comes to mind is TurboSHAKE128. It's
>> faster, most people are happy with the security margins, and CFRG is
>> working on it (draft-irtf-cfrg-kangarootwelve).  Our benchmarks for Prio3
>> [2] show that TurboSHAKE128 is as much as 20% faster than SHAKE128. (How
>> much improvement we get depends on the Prio3 type. For very large inputs,
>> the runtime is dominated by finite field arithmetic rather than hashing.)
>>
>> SHA-2 could work as well, in the right mode of operation. Our
>> requirements are similar to RFC 9380 in that we need the XOF to behave like
>> a random oracle [3]. In fact `expand_message_xmd()` from RFC 9380 *almost*
>> fits the bill --- we need to tweak it slightly in order to make it work for
>> our application. (We mainly use the XOF to expand a short seed into a long
>> vector of finite field elements. Depending on the data type, the maximum
>> output length for `expand_message_xmd()` may be too short.) However, this
>> tweaked mode for SHA-256 is up to 60% slower than SHAKE128 [2].
>>
>> In terms of performance, TurboSHAKE is the clear winner. The main concern
>> I've heard about moving to TurboSHAKE is that it would add a dependency on
>> an unfinished draft. On the other hand, adopting TurboSHAKE might help
>> build momentum towards completing that work.The performance for SHA-2 could
>> probably be improved (we haven't evaluated SHA-512 for instance --- perhaps
>> the longer output length will yield savings), but unless we have a very
>> compelling reason to do so, we'd like to avoid specifying a new mode for it
>> (i.e., a tweaked version of `expand_message_xmd()`).
>>
>> It would be useful to hear from potential adopters as well as folks who
>> have some experience with these primitives and may have some insights to
>> share. The ideal outcome here is a single choice that most people are happy
>> to implement. We'd prefer to avoid having to specify multiple alternatives
>> here; this is essentially green-field cryptography, and it would be a shame
>> to take on the baggage of agility before we absolutely need to.
>>
>> Thanks on behalf of the editors,
>> Chris P.
>>
>> [1] https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/209
>> [2] https://github.com/divviup/libprio-rs/pull/768
>> [3] https://eprint.iacr.org/2023/130
>> _______________________________________________
>> CFRG mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>