The Mastic VDAF
draft-mouris-cfrg-mastic-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Expired".
|
|
|---|---|---|---|
| Authors | Dimitris Mouris , Christopher Patton , Pratik Sarkar , Nektarios Georgios Tsoutsos | ||
| Last updated | 2023-10-13 | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-mouris-cfrg-mastic-00
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,
<https://www.rfc-editor.org/rfc/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.
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, <https://ia.cr/2021/017>.
[CP22] Leo de Castro and Anitgoni Polychroniadou, "Lightweight,
Maliciously Secure Verifiable Function Secret Sharing",
EUROCRYPT 2022 ,
<https://iacr.org/cryptodb/data/paper.php?pubkey=31935>.
[DPRS23] Davis, H., Patton, C., Rosulek, M., and P. Schoppmann,
"Verifiable Distributed Aggregation Functions", n.d.,
<https://ia.cr/2023/130>.
[GI14] Gilboa, N. and Y. Ishai, "Distributed Point Functions and
Their Applications", EUROCRYPT 2014 , 2014,
<https://link.springer.com/
chapter/10.1007/978-3-642-55220-5_35>.
[MST23] Dimitris Mouris, Pratik Sarkar, and Nektarios Georgios
Tsoutsos, "PLASMA: Private, Lightweight Aggregated
Statistics against Malicious Adversaries",
<https://ia.cr/2023/080>.
[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, <https://datatracker.ietf.org/doc/html/draft-
irtf-cfrg-vdaf-07>.
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]