Crypto Forum D. Mouris Internet-Draft University of Delaware Intended status: Informational C. Patton Expires: 15 April 2024 Cloudflare P. Sarkar Boston University N. G. Tsoutsos University of Delaware 13 October 2023 The Mastic VDAF draft-mouris-cfrg-mastic-00 Abstract 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. About This Document 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. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Mouris, et al. Expires 15 April 2024 [Page 1] Internet-Draft Mastic October 2023 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 Notice 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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Verifiable IDPF (VIDPF) . . . . . . . . . . . . . . . . . 3 3.2. Interactive Aggregation for VDAFs . . . . . . . . . . . . 4 4. The Plabels VDAF . . . . . . . . . . . . . . . . . . . . . . 4 5. Reducing Communication Cost via Interactive Aggregation . . . 4 6. Improved Robustness via . . . . . . . . . . . . . . . . . . . 4 7. Security Considerations . . . . . . . . . . . . . . . . . . . 4 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 5 9.1. Normative References . . . . . . . . . . . . . . . . . . 5 9.2. Informative References . . . . . . . . . . . . . . . . . 5 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 6 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 6 1. Introduction 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] Mouris, et al. Expires 15 April 2024 [Page 2] Internet-Draft Mastic October 2023 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. 2. Conventions and Definitions 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. 3. Preliminaries 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. 3.1. Verifiable IDPF (VIDPF) 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) Mouris, et al. Expires 15 April 2024 [Page 3] Internet-Draft Mastic October 2023 3.2. Interactive Aggregation for VDAFs 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. 4. The Plabels VDAF TODO(Hannah) Describe the implementation of the base Vdaf interface. 5. Reducing Communication Cost via Interactive Aggregation TODO(Dimitris) Describe the implementation of the interface in Section 3.2 6. Improved Robustness via TODO Describe 3-party PLASMA 7. Security Considerations TODO Security Mouris, et al. Expires 15 April 2024 [Page 4] Internet-Draft Mastic October 2023 8. IANA Considerations This document has no IANA actions. 9. References 9.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 9.2. Informative References [BBCGGI21] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and Y. Ishai, "Lightweight Techniques for Private Heavy Hitters", IEEE S&P 2021 , 2021, . [CP22] Leo de Castro and Anitgoni Polychroniadou, "Lightweight, Maliciously Secure Verifiable Function Secret Sharing", EUROCRYPT 2022 , . [DPRS23] Davis, H., Patton, C., Rosulek, M., and P. Schoppmann, "Verifiable Distributed Aggregation Functions", n.d., . [GI14] Gilboa, N. and Y. Ishai, "Distributed Point Functions and Their Applications", EUROCRYPT 2014 , 2014, . [MST23] Dimitris Mouris, Pratik Sarkar, and Nektarios Georgios Tsoutsos, "PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries", . [VDAF] Barnes, R., Cook, D., Patton, C., and P. Schoppmann, "Verifiable Distributed Aggregation Functions", Work in Progress, Internet-Draft, draft-irtf-cfrg-vdaf-07, 31 August 2023, . Mouris, et al. Expires 15 April 2024 [Page 5] Internet-Draft Mastic October 2023 Acknowledgments TODO(Dimitris) Authors' Addresses Dimitris Mouris University of Delaware Email: jimouris@udel.edu Christopher Patton Cloudflare Email: chrispatton+ietf@gmail.com Pratik Sarkar Boston University Email: pratik93@bu.edu Nektarios G. Tsoutsos University of Delaware Email: tsoutsos@udel.edu Mouris, et al. Expires 15 April 2024 [Page 6]