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

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.

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=
40apple.com@dmarc.ietf.org> 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=
> 40cloudflare.com@dmarc.ietf.org> 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 <cpatton@cloudflare.com>
> Date: Mon, Mar 4, 2024 at 8:07 AM
> Subject: Next steps for heavy hitters with VDAFs
> To: CFRG <cfrg@irtf.org>
>
>
> 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
> Ppm@ietf.org
> https://www.ietf.org/mailman/listinfo/ppm
>
>
> --
> Ppm mailing list
> Ppm@ietf.org
> https://www.ietf.org/mailman/listinfo/ppm
>