[prev in list] [next in list] [prev in thread] [next in thread]
List: cfrg
Subject: Re: [CFRG] Choice of XOF for draft-irtf-cfrg-vdaf
From: Christopher Patton <cpatton=40cloudflare.com () dmarc ! ietf ! org>
Date: 2023-10-10 16:32:34
Message-ID: CAG2Zi23tSoFV71SO8NZdtYDJ_d6CMzZ6Kj2VMDUpkeqwPe=7Dw () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
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=
40divviup.org@dmarc.ietf.org> 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=
> 40cloudflare.com@dmarc.ietf.org> 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
>> CFRG@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
[Attachment #5 (text/html)]
<div dir="ltr"><div>Thanks for the extra data point, David! From a perf perspective \
it seems like TurboSHAKE128 is the right way to go.</div><div><br></div><div>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.<br></div><div><br></div><div>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.</div><div><br></div><div>Best,<br></div><div>Chris \
P.<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On \
Fri, Oct 6, 2023 at 12:03 PM David Cook <dcook=<a \
href="mailto:40divviup.org@dmarc.ietf.org">40divviup.org@dmarc.ietf.org</a>> \
wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>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 <a \
href="https://github.com/divergentdave/libprio-rs/commit/522c10a13098097257a3feb20043eb68ed275784" \
target="_blank">https://github.com/divergentdave/libprio-rs/commit/522c10a13098097257a3feb20043eb68ed275784</a>, \
and running "cargo bench --bench speed_tests -- \
prio3sumvec".</div><div><br></div><div>Sharding:</div><div>
<span></span>
<table cellspacing="0" border="0">
<colgroup span="4"></colgroup>
<tbody><tr>
<td align="left">Measurement length</td>
<td align="left">SHAKE128</td>
<td align="left">TurboSHAKE</td>
<td align="left">SHA-2 tweaked XMD</td>
</tr>
<tr>
<td align="left">10</td>
<td align="left">76.709 µs</td>
<td align="left">60.280 µs</td>
<td align="left">59.984 µs</td>
</tr>
<tr>
<td align="left">30</td>
<td align="left">100.22 µs</td>
<td align="left">80.307 µs</td>
<td align="left">79.026 µs</td>
</tr>
<tr>
<td align="left">100</td>
<td align="left">202.71 µs</td>
<td align="left">169.21 µs</td>
<td align="left">166.60 µs</td>
</tr>
<tr>
<td align="left">300</td>
<td align="left">466.39 µs</td>
<td align="left">398.63 µs</td>
<td align="left">308.37 µs</td>
</tr>
<tr>
<td align="left">1000</td>
<td align="left">1.8078 ms</td>
<td align="left">1.6263 ms</td>
<td align="left">1.4790 ms</td>
</tr>
</tbody></table>
</div><div><br></div><div>Preparation, initial step:</div><div>
<span></span>
<table cellspacing="0" border="0">
<colgroup span="4"></colgroup>
<tbody><tr>
<td align="left">Measurement length</td>
<td align="left">SHAKE128</td>
<td align="left">TurboSHAKE</td>
<td align="left">SHA-2 tweaked XMD</td>
</tr>
<tr>
<td align="left">10</td>
<td align="left">53.616 µs</td>
<td align="left">44.887 µs</td>
<td align="left">44.728 µs</td>
</tr>
<tr>
<td align="left">30</td>
<td align="left">66.061 µs</td>
<td align="left">55.320 µs</td>
<td align="left">54.771 µs</td>
</tr>
<tr>
<td align="left">100</td>
<td align="left">104.70 µs</td>
<td align="left">90.823 µs</td>
<td align="left">89.803 µs</td>
</tr>
<tr>
<td align="left">300</td>
<td align="left">206.79 µs</td>
<td align="left">180.94 µs</td>
<td align="left">175.85 µs</td>
</tr>
<tr>
<td align="left">1000</td>
<td align="left">610.40 µs</td>
<td align="left">539.43 µs</td>
<td align="left">527.80 µs</td>
</tr>
</tbody></table>
</div><div><br></div><div>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).</div><div><br></div><div>--David \
Cook<br></div><div><br></div><div class="gmail_quote"><div dir="ltr" \
class="gmail_attr">On Tue, Sep 26, 2023 at 6:18 PM Christopher Patton \
<cpatton=<a href="mailto:40cloudflare.com@dmarc.ietf.org" \
target="_blank">40cloudflare.com@dmarc.ietf.org</a>> wrote:<br></div><blockquote \
class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid \
rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi \
all,</div><div><br></div><div>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.<br></div><div><br></div><div>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.)</div><div><br></div><div>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].</div><div><br></div><div>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()`).<br></div><div><br></div><div>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.<br></div><div><br></div><div>Thanks on behalf of the editors,</div><div>Chris \
P.</div><div><br></div><div>[1] <a \
href="https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/209" \
target="_blank">https://github.com/cfrg/draft-irtf-cfrg-vdaf/issues/209</a></div><div>[2] \
<a href="https://github.com/divviup/libprio-rs/pull/768" \
target="_blank">https://github.com/divviup/libprio-rs/pull/768</a></div><div>[3] <a \
href="https://eprint.iacr.org/2023/130" \
target="_blank">https://eprint.iacr.org/2023/130</a></div></div> \
_______________________________________________<br> CFRG mailing list<br>
<a href="mailto:CFRG@irtf.org" target="_blank">CFRG@irtf.org</a><br>
<a href="https://www.irtf.org/mailman/listinfo/cfrg" rel="noreferrer" \
target="_blank">https://www.irtf.org/mailman/listinfo/cfrg</a><br> \
</blockquote></div></div> _______________________________________________<br>
CFRG mailing list<br>
<a href="mailto:CFRG@irtf.org" target="_blank">CFRG@irtf.org</a><br>
<a href="https://www.irtf.org/mailman/listinfo/cfrg" rel="noreferrer" \
target="_blank">https://www.irtf.org/mailman/listinfo/cfrg</a><br> \
</blockquote></div>
_______________________________________________
CFRG mailing list
CFRG@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic