Re: [Ppm] [CFRG] Next steps for heavy hitters with VDAFs

[Eric Rescorla <[e-mail]>]

On Mon, Mar 4, 2024 at 5:20 PM Christopher Patton <cpatton=
[e-mail]> wrote:

> Thanks PPM and CFRG, this has been helpful.
>
> So far it seems like there is a plurality in favor of adopting a separate
> draft for Mastic and only consider dropping Poplar1 once we're more certain
> about the trade-offs. It would be nice to hear from anyone who is strongly
> opposed to this plan.
>

To restate what I think you said, I think it's fine to adopt Mastic. I
would defer a decision on Poplar until after we know more.

-Ekr

>
> One concern that's been brought up is the editorial effort required to
> maintain both. Speaking as an editor of both Mastic and Poplar1, I think
> there is likely to be some duplicative effort here: most of the low level
> algorithmic bits these protocols have in common (i.e., IDPF) have been
> stable for some time, but there are also some evolving security
> considerations that apply to both (around safe usage of IDPF). I also
> expect there to be some security considerations that apply to Poplar1, but
> not Mastic.
>
> Chris P.
>
> On Mon, Mar 4, 2024 at 2:33 PM Shan Wang <shan_wang=
> [e-mail]> wrote:
>
>> I'm in favour of either
>> 1. Replace Poplar1 with Mastic in the base VDAF draft
>> (draft-irtf-cfrg-vdaf).
>> Or
>> 4. Refactor the base draft so that it spells only the VDAF framework,
>> adopt the Mastic draft, and adopt a new draft for Prio3.
>>
>> If we do 4. The we can cut an individual Poplar RFC too and anyone have
>> implemented Poplar1 can refer to that standard.
>>
>> In my opinion, VDAF should define a common framework. We will have more
>> algorithms in the future and they should be cut as individual drafts that's
>> compatible with VDAF, rather than part of the VDAF text itself.
>>
>> Shan
>>
>>
>> On 4 Mar 2024, at 16:13, Christopher Patton <cpatton=
>> [e-mail]> wrote:
>>
>> Hi all, I'm cross-posting this message to the CFRG mailing list in the
>> hopes that folks who would like to implement heavy hitters in DAP will
>> weigh in. We definitely end to hear from implementers and potential
>> adopters.
>>
>> Thanks,
>> Chris P.
>>
>> ---------- Forwarded message ---------
>> From: Christopher Patton <[e-mail]>
>> Date: Mon, Mar 4, 2024 at 8:07 AM
>> Subject: Next steps for heavy hitters with VDAFs
>> To: CFRG <[e-mail]>
>>
>>
>> Hi CFRG,
>>
>> I've asked the chairs to spend some time at 119 discussing next steps for
>> Mastic:
>> https://datatracker.ietf.org/doc/html/draft-mouris-cfrg-mastic-02
>>
>> The ideal outcome may not be to adopt this draft directly, but to merge
>> it with the existing VDAF draft (draft-irtf-cfrg-vdaf). Our goal for 119
>> is to find consensus on a path forward.
>>
>> Last time (118) we presented Mastic, a new VDAF that we pitched as a
>> drop-in replacement for Poplar1 (
>> https://datatracker.ietf.org/meeting/118/materials/slides-118-cfrg-mastic-vdaf).
>> Since the meeting we have been working on security analysis for Mastic.
>> The theorems in this paper claim that Mastic's composition of its
>> primitives (VIDPF, an extension of IDPF from draft-irtf-cfrg-vdaf) and
>> FLP (from draft-irtf-cfrg-vdaf) into a VDAF is secure. The concrete
>> parameters of VIDPF and FLP are subject to change as analysis continues,
>> but the overall composition seems to be sound:
>> https://eprint.iacr.org/2024/221
>>
>> Mastic is also more efficient in terms of round complexity, is easier to
>> implement securely, and addresses use cases identified in the PPM WG for
>> which Poplar1 falls short. Overall, Mastic reflects improvements that have
>> been made to this paradigm (i.e., function secret sharing for heavy
>> hitters) since the Poplar paper appeared three years ago (
>> https://eprint.iacr.org/2021/017). The only potential advantage of
>> Poplar1 is that, once we finalize the parameters of VIDPF, it may end up
>> having a lower bandwidth cost (at most 50% more, I suspect). However,
>> speaking as an implementer, the lower round complexity of Mastic over
>> Poplar1 makes it the far better option.
>>
>> We (the Mastic designers) would like the CFRG to consider the following
>> outcomes:
>> 1. Replace Poplar1 with Mastic in the base VDAF draft (draft-irtf-cfrg
>> -vdaf).
>> 2. Adopt the Mastic draft (draft-mourics-cfrg-mastic) and remove Poplar1
>> from the base draft.
>> 3. Adopt the Mastic draft, but keep Poplar1 in the base draft.
>> 4. Refactor the base draft so that it spells only the VDAF framework,
>> adopt the Mastic draft, and adopt a new draft for Prio3. Note that there is
>> one primitive (FLP) that would be shared by both Mastic and Prio3.
>>
>> Here are the main considerations we've heard while getting feedback on
>> this question.
>> a. Since the PPM WG can't finish its work until the base VDAF draft is
>> done, we should do everything we can to minimize time to RFC.
>> b. Recommending two protocols (Poplar1 and Mastic) for the same use case
>> (heavy hitters) is probably not a good idea, especially if one is clearly
>> superior to the other.
>> c. If we remove Poplar1, then we could consider restricting the VDAF
>> syntax to 1 round for preparation.
>> d. The base draft should use all features of the VDAF framework.
>> e. Poplar1 involves an MPC paradigm called "arithmetic sketching" (
>> https://eprint.iacr.org/2023/1012) that may be useful for future VDAFs
>> and thus worth specifying.
>>
>> Thanks for your time and we're looking forward to 119,
>> Chris P.
>> --
>> Ppm mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/ppm
>>
>>
>> --
>> Ppm mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/ppm
>>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://mailman.irtf.org/mailman/listinfo/cfrg
>