| Internet-Draft | Mastic | October 2023 |
| Mouris, et al. | Expires 15 April 2024 | [Page] |
This document describes Plabels, a two-party VDAF for the following aggregation task: each Client holds a bit string, and the Collector wishes to count how many of these strings begin with a candidate prefix. Such a VDAF can be used to solve the heavy hitters problem, where the goal is compute the subset of the measurements that occur most frequently. This document also describes various modes of operation for Plabels. First, its output type can be enriched to support aggregation functions beyond prefix counts. Second, an extension to the aggregation phase is described that significantly reduces communication cost compared to existing techniques. Third, a three-party variant is described that is robust in the honest majority setting.¶
This note is to be removed before publishing as an RFC.¶
Status information for this document may be found at https://datatracker.ietf.org/doc/draft-mouris-cfrg-mastic/.¶
Discussion of this document takes place on the Crypto Forum Research Group mailing list (mailto:cfrg@ietf.org), which is archived at https://mailarchive.ietf.org/arch/search/?email_list=cfrg. Subscribe at https://www.ietf.org/mailman/listinfo/cfrg/.¶
Source for this draft and an issue tracker can be found at https://github.com/jimouris/draft-mouris-cfrg-mastic.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 15 April 2024.¶
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶
TODO Introduction. Outline: - Recall the heavy hitters problem - Describe Poplar [BBCGGI21], IDPF, and how the VDAF abstraction relates to IDPF - Say that Poplar isn't ideal for solving this problem - Introduce [MST23]¶
Poplar [BBCGGI21] described a protocol for solving the t-heavy-hitters
problem in a privacy-preserving manner. Each client holds a bit-string of
length n, and the goal of the aggregation servers is to compute the set of
inputs that occur at least t times. The core primitive used in their protocol
is a specialized Distributed Point Function (DPF) [GI14], called Incremental
DPF (IDPF), that allows the servers to "query" their DPF shares on any
bit-string of length shorter than or equal to n. As a result of this query,
each of the servers has an additive share of a bit indicating whether the
string is a prefix of the client's input. The protocol also specifies a
multi-party computation for verifying that at most one string among a set of
candidates is a prefix of the client's input.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
This document makes use of Fully Linear Proofs (FLPs) and eXtendable Output Functions (XOFs) as described in [VDAF]. It also makes use of an extension of Incremental Distributed Point Functions (IDPFs), known as "Verifiable IDPFs (VIDFS)" first described by [MST23]. VIDPFs are specified below.¶
De Castro and Polychroniadou [CP22] introduced Verifiable DPF (VDPF), a DPF scheme that supports a well-formedness check. More specifically, VDPFs allows verifying that the client’s inputs are well-formed, meaning that the client will not learn any unauthorized information about the servers' database or modify the database in an unauthorized way.¶
PLASMA [MST23] introduced the notion of Verifiable Incremental DPF (VIDPF) that builds upon IDPF [BBCGGI21] and VDPF [CP22]. VIDPF is an IDPF that allows verifying that clients’ inputs are valid by relying on hashing while preserving the client’s input privacy.¶
TODO(Dimitris)¶
In order to accommadating Plabel's improvemnt in communication cost require, it
is necessary to replace the non-interactive aggregation algorithm
Vdaf.aggregate() with a 1-round, interactive protocol implemented by the
following methods:¶
Vdaf.aggregate_init(agg_info: AggInfo, out_shares: list[OutShare]) ->
tuple[AggState, AggMessage] is the deterministic aggregation initialization
algorithm called by each Aggregator. It takes as input the set output shares
to be aggregated and a parameter called the "aggregation information". Its
outputs are the Aggregator's state and broadcast message.¶
Vdaf.aggregate_finish(agg_state: AggState, agg_msgs: list[AggMessage]) ->
AggShare. is the deterministic aggregation finalization aglorithm called by
each Aggregator on its aggregation state and the sequence of messages
broadcast by each Aggregator.¶
CP: The binary search described in [MST23] obviously doesn't fit into a
1-round protocol, as the number of rounds required depends on how deep down
the Merkle we have to before we've identified all bad reports. The idea is
that aggregation protocol would be invoked multiple times, each time with a
different agg_info.¶
CP: Let's try to come up with a better name than agg_info.¶
TODO(Hannah) Describe the implementation of the base Vdaf interface.¶
TODO(Dimitris) Describe the implementation of the interface in Section 3.2¶
TODO Describe 3-party PLASMA¶
TODO Security¶
This document has no IANA actions.¶
TODO(Dimitris)¶