CFRG C. Patton Internet-Draft Cloudflare, Inc. Intended status: Informational R.L. Barnes Expires: 28 April 2022 Cisco P. Schoppmann Google 25 October 2021 Verifiable Distributed Aggregation Functions draft-patton-cfrg-vdaf-00 Abstract This document describes Verifiable Distributed Aggregation Functions (VDAFs), a family of multi-party protocols for computing aggregate statistics over user measurements. These protocols are designed to ensure that, as long as at least one aggregation server executes the protocol honestly, individual measurements are never seen by any server in the clear. At the same time, VDAFs allow the servers to detect if a malicious or misconfigured client submitted an input that would result in an incorrect aggregate result. Discussion Venues This note is to be removed before publishing as an RFC. Discussion of this document takes place on the Crypto Forum Research Group mailing list (cfrg@ietf.org), which is archived at https://mailarchive.ietf.org/arch/search/?email_list=cfrg. Source for this draft and an issue tracker can be found at https://github.com/cjpatton/vdaf. Status of This Memo 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." Patton, et al. Expires 28 April 2022 [Page 1] Internet-Draft VDAF October 2021 This Internet-Draft will expire on 28 April 2022. Copyright Notice Copyright (c) 2021 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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 6 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4. Definition of VDAFs . . . . . . . . . . . . . . . . . . . . . 9 4.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2. Sharding . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3. Preparation . . . . . . . . . . . . . . . . . . . . . . . 11 4.4. Aggregation . . . . . . . . . . . . . . . . . . . . . . . 13 4.5. Unsharding . . . . . . . . . . . . . . . . . . . . . . . 14 4.6. Execution of a VDAF . . . . . . . . . . . . . . . . . . . 14 5. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 16 5.1. Key Derivation . . . . . . . . . . . . . . . . . . . . . 16 5.2. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17 5.2.1. Deriving a Pseudorandom Vector . . . . . . . . . . . 17 5.2.2. Inner product of Vectors . . . . . . . . . . . . . . 18 6. prio3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6.1. Fully Linear Proof (FLP) Systems . . . . . . . . . . . . 19 6.1.1. Encoding the Input . . . . . . . . . . . . . . . . . 21 6.2. Construction . . . . . . . . . . . . . . . . . . . . . . 22 6.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 22 6.2.2. Sharding . . . . . . . . . . . . . . . . . . . . . . 22 6.2.3. Preparation . . . . . . . . . . . . . . . . . . . . . 24 6.2.4. Aggregation . . . . . . . . . . . . . . . . . . . . . 26 6.2.5. Unsharding . . . . . . . . . . . . . . . . . . . . . 26 6.2.6. Helper Functions . . . . . . . . . . . . . . . . . . 27 7. hits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7.1. Incremental Distributed Point Functions (IDPFs) . . . . . 28 7.2. Construction . . . . . . . . . . . . . . . . . . . . . . 29 7.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 30 7.2.2. Preparation . . . . . . . . . . . . . . . . . . . . . 31 Patton, et al. Expires 28 April 2022 [Page 2] Internet-Draft VDAF October 2021 7.2.3. Aggregation . . . . . . . . . . . . . . . . . . . . . 33 7.2.4. Unsharding . . . . . . . . . . . . . . . . . . . . . 33 7.2.5. Helper Functions . . . . . . . . . . . . . . . . . . 33 8. Security Considerations . . . . . . . . . . . . . . . . . . . 34 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 35 10.1. Normative References . . . . . . . . . . . . . . . . . . 35 10.2. Informative References . . . . . . . . . . . . . . . . . 35 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 37 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 37 1. Introduction The ubiquity of the Internet makes it an ideal platform for measurement of large-scale phenomena, whether public health trends or the behavior of computer systems at scale. There is substantial overlap, however, between information that is valuable to measure and information that users consider private. For example, consider an application that provides health information to users. The operator of an application might want to know which parts of their application are used most often, as a way to guide future development of the application. Specific users' patterns of usage, though, could reveal sensitive things about them, such as which users are researching a given health condition. In many situations, the measurement collector is only interested in aggregate statistics, e.g., which portions of an application are most used or what fraction of people have experienced a given disease. Thus systems that provide aggregate statistics while protecting individual measurements can deliver the value of the measurements while protecting users' privacy. Most prior approaches to this problem fall under the rubric of "differential privacy (DP)" [Dwo06]. Roughly speaking, a data aggregation system that is differentially private ensures that the degree to which any individual measurement influences the value of the aggregated output can be precisely controlled. For example, in systems like RAPPOR [EPK14], each user samples noise from a well- known distribution and adds it to their input before submitting to the aggregation server. The aggregation server then adds up the noisy inputs, and because it knows the distribution from whence the noise was sampled, it can estimate the true sum with reasonable precision. Differentially private systems like RAPPOR are easy to deploy and provide a useful guarantee. On its own, however, DP falls short of the strongest privacy property one could hope for. Specifically, Patton, et al. Expires 28 April 2022 [Page 3] Internet-Draft VDAF October 2021 depending on the "amount" of noise a client adds to its input, it may be possible for a curious aggregator to make a reasonable guess of the input's true value. Indeed, the more noise the clients add, the less reliable will be the server's estimate of the output. Thus systems employing DP techniques alone must strike a delicate balance between privacy and utility. The ideal goal for a privacy-preserving measurement system is that of secure multi-party computation: No participant in the protocol should learn anything about an individual input beyond what it can deduce from the aggregate. In this document, we describe Verifiable Distributed Aggregation Functions (VDAFs) as a general class of protocols that achieve this goal. VDAF schemes achieve their privacy goal by distributing the computation of the aggregate among a number of non-colluding aggregation servers. As long as a subset of the servers executes the protocol honestly, VDAFs guarantee that no input is ever accessible to any party besides the client that submitted it. At the same time, VDAFs are "verifiable" in the sense that malformed inputs that would otherwise garble the output of the computation can be detected and removed from the set of inputs. The cost of achieving these security properties is the need for multiple servers to participate in the protocol, and the need to ensure they do not collude to undermine the VDAF's privacy guarantees. Recent implementation experience has shown that practical challenges of coordinating multiple servers can be overcome. The Prio system [CGB17] (essentially a VDAF) has been deployed in systems supporting hundreds of millions of users: The Mozilla Origin Telemetry project [OriginTelemetry] and the Exposure Notification Private Analytics collaboration among the Internet Security Research Group (ISRG), Google, Apple, and others [ENPA]. The VDAF abstraction laid out in Section 4 represents a class of multi-party protocols for privacy-preserving measurement proposed in the literature. These protocols vary in their operational and security considerations, sometimes in subtle but consequential ways. This document therefore has two important goals: 1. Providing applications like [I-D.draft-gpew-priv-ppm] with a simple, uniform interface for accessing privacy-preserving measurement schemes, and documenting relevant operational and security bounds for that interface: 1. General patterns of communications among the various actors involved in the system (clients, aggregators, and measurement collectors); Patton, et al. Expires 28 April 2022 [Page 4] Internet-Draft VDAF October 2021 2. Capabilities of a malicious coalition of servers attempting divulge information about client inputs; and 3. Conditions that are necessary to ensure that malicious clients cannot corrupt the computation. 2. Providing cryptographers with design criteria that allow new constructions to be easily used by applications. This document also specifies two concrete VDAF schemes, each based on a protocol from the literature. * The aforementioned Prio system [CGB17] allows for the privacy- preserving computation of a variety aggregate statistics. The basic idea underlying Prio is fairly simple: 1. Each client shards its input into a sequence of additive shares and distributes the shares among the aggregation servers. 2. Next, each server adds up its shares locally, resulting in an additive share of the aggregate. 3. Finally, the aggregators combine their additive shares to obtain the final aggregate. The difficult part of this system is ensuring that the servers hold shares of a valid input, e.g., the input is an integer in a specific range. Thus Prio specifies a multi-party protocol for accomplishing this task. In Section 6 we describe prio3, a VDAF that follows the same overall framework as the original Prio protocol, but incorporates techniques introduced in [BBCGGI19] that result in significant performance gains. Patton, et al. Expires 28 April 2022 [Page 5] Internet-Draft VDAF October 2021 * More recently, Boneh et al. [BBCGGI21] described a protocol for solving the t-heavy-hitters problem in a privacy-preserving manner. Here 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 generalization of a Distributed Point Function (DPF) [GI14] 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. In Section 7 we describe a VDAF called hits that implements this functionality. The remainder of this document is organized as follows: Section 3 gives a brief overview of VDAFs; Section 4 defines the syntax for VDAFs; Section 5 defines various functionalities that are common to our constructions; Section 7 describes the hits construction; Section 6 describes the prio3 construction; and Section 8 enumerates the security considerations for VDAFs. 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. Algorithms in this document are written in Python 3. Type hints are used to define input and output types. Function parameters without type hints implicitly have type Bytes, an arbitrary byte string. A fatal error in a program (e.g., failure to parse one of the function parameters) is usually handled by raising an exception. Some common functionalities: * zeros(len: Unsigned) -> output: Bytes returns an array of zero bytes. The length of output MUST be len. * gen_rand(len: Unsigned) -> output: Bytes returns an array of random bytes. The length of output MUST be len. * byte(int: Unsigned) -> Byte returns the representation of int as a byte. The value of int MUST be in range [0,256). Patton, et al. Expires 28 April 2022 [Page 6] Internet-Draft VDAF October 2021 3. Overview In a VDAF-based private measurement system, we distinguish three types of actors: Clients, Aggregators, and Collectors. The overall flow of the measurement process is as follows: * Clients are configured with public parameters for a set of aggregators. * To submit an individual measurement, a client shards the measurement into "input shares" and sends one input share to each Aggregator. * The aggregators verify the validity of the input shares, producing a set of "output shares". - Output shares are in one-to-one correspondence with the input shares. - Just as each Aggregator receives one input share of each input, at the end of the validation process, each aggregator holds one output share. - In most VDAFs, aggregators will need to exchange information among themselves as part of the validation process. * Each aggregator combine the output shares across inputs in the batch to compute "aggregate shares", i.e., shares of the desired aggregate result. * The aggregators submit their aggregate shares to the collector, who combines them to obtain the aggregate result over the batch. Patton, et al. Expires 28 April 2022 [Page 7] Internet-Draft VDAF October 2021 +--------------+ +---->| Aggregator 0 |----+ | +--------------+ | | ^ | | | | | V | | +--------------+ | | +-->| Aggregator 1 |--+ | | | +--------------+ | | +--------+-+ | ^ | +->+-----------+ | Client |---+ | +--->| Collector |--> Aggregate +--------+-+ +->+-----------+ | ... | | | | | | | V | | +----------------+ | +--->| Aggregator N-1 |---+ +----------------+ Input shares Aggregate shares Figure 1: Overall data flow of a VDAF Aggregators are a new class of actor relative to traditional measurement systems where clients submit measurements to a single server. They are critical for both the privacy properties of the system and the correctness of the measurements obtained. The privacy properties of the system are assured by non-collusion among aggregators, and aggregators are the entities that perform validation of client inputs. Thus clients trust Aggregators not to collude (typically it is required that at least one Aggregator is honest), and Collectors trust Aggregators to properly verify Client inputs. Within the bounds of the non-collusion requirements of a given VDAF instance, it is possible for the same entity to play more than one role. For example, the Collector could also act as an Aggregator, effectively using the other Aggregators to augment a basic client- server protocol. In this document, we describe the computations performed by the actors in this system. It is up to applications to arrange for the required information to be delivered to the proper actors in the proper sequence. In general, we assume that all communications are confidential and mutually authenticated, with the exception that Clients submitting measurements may be anonymous. Patton, et al. Expires 28 April 2022 [Page 8] Internet-Draft VDAF October 2021 4. Definition of VDAFs A concrete VDAF specifies the algorithms involved in evaluating an aggregation function across a batch of inputs. This section specifies the interfaces of these algorithms as they would be exposed to applications. The overall execution of a VDAF comprises the following steps: * Setup - Generating shared parameters for the aggregators * Sharding - Computing input shares from an individual measurement * Preparation - Conversion and verification of input shares to output shares compatible with the aggregation function being computed * Aggregation - Combining a set of output shares into an aggregate share * Unsharding - Combining a set of aggregate shares into an aggregate result The setup algorithm is performed once for a given collection of Aggregators. Sharding and preparation are done once per measurement input. Aggregation and unsharding are done over a batch of inputs (more precisely, over the output shares recovered from those inputs). Note that the preparation step performs two functions: Verification and conversion. Conversion translates input shares into output shares that are compatible with the aggregation function. Verification ensures that aggregating the recovered output shares will not lead to a garbled aggregate result. A concrete VDAF scheme specifies implementations of these algorithms. In addition, a VDAF specifies the following constants: * SHARES: Unsigned is the number of Aggregators for which the VDAF is defined. * ROUNDS: Unsigned is the number of rounds of communication among the Aggregators before they recover output shares from a single set of input shares. Patton, et al. Expires 28 April 2022 [Page 9] Internet-Draft VDAF October 2021 4.1. Setup Before execution of the VDAF can begin, it is necessary to distribute long-lived parameters to the Client and Aggregators. The long-lived parameters are generated by the following algorithm: * vdaf_setup() -> (public_param, verify_params: Vec[Bytes]) is the randomized setup algorithm used to generate the public parameter used by the Clients (public_param) and the verification parameters used by the Aggregators (verify_params). The length of the latter MUST be SHARES. The parameters are generated once and reused across multiple VDAF evaluations. In general, an Aggregator's verification parameter is considered secret and MUST NOT be revealed to the Clients, Collector or other Aggregators. 4.2. Sharding In order to protect the privacy of its measurements, a VDAF client divides its measurements into "input shares". The measurement_to_input_shares method is executed by the client to produce these shares. One share is sent to each aggregator. * measurement_to_input_shares(public_param, input) -> input_shares: Vec[Bytes] is the randomized input-distribution algorithm run by each Client. It consumes the public parameter and input measurement and produces a sequence of input shares, one for each Aggregator. The length of input_shares MUST be SHARES. Client ====== measurement | V +----------------------------------------------+ | measure_to_input_shares | +----------------------------------------------+ | | ... | V V V input_share_0 input_share_1 input_share_[SHARES-1] | | ... | V V V Aggregator 0 Aggregator 1 Aggregator SHARES-1 Figure 2: The Client divides its measurement input into input shares and distributes them to the Aggregators. Patton, et al. Expires 28 April 2022 [Page 10] Internet-Draft VDAF October 2021 4.3. Preparation To recover and verify the validity of output shares, the Aggregators interact with one another over ROUND rounds. In the first round, each aggregator produces a single output based on its input share. In subsequent rounds, each aggregator is given the outputs from all aggregators in the previous round. After the final round, either all aggregators hold an output share (if the output shares are valid) or all aggregators report an error (if they are not). This process involves a value called the "aggregation parameter" used to map the input shares to output shares. The Aggregators need to agree on this parameter before they can begin preparing inputs for aggregation. Aggregator 0 Aggregator 1 Aggregator SHARES-1 ============ ============ =================== input_share_0 input_share_1 input_share_[SHARES-1] | | ... | V V V +-----------+ +-----------+ +-----------+ | prep init | | prep init | | prep init | +-----------+ +------------+ +-----------+ | | ... | V V V +-----------+ +-----------+ +-----------+ | prep next | | prep next | | prep next | +-----------+ +-----------+ +-----------+ | | ... | ==================================== | | | V V V ... ... ... | | | V V V +-----------+ +-----------+ +-----------+ | prep next | | prep next | | prep next | +-----------+ +-----------+ +-----------+ | | ... | V V V out_share_0 out_share_1 out_share_[SHARES-1] Figure 3: VDAF preparation process on the input shares for a single input. The === lines indicate the sharing of one round's outputs as the inputs to the next round. At the end of the protocol, each aggregator holds an output share or an error. Patton, et al. Expires 28 April 2022 [Page 11] Internet-Draft VDAF October 2021 * PrepState(verify_param, agg_param, nonce, input_share) is the deterministic preparation-state initialization algorithm run by each Aggregator to begin processing its input share into an output share. Its inputs are the aggregator's verification parameter (verify_param), the aggregation parameter (agg_param), the nonce provided by the environment (nonce, see Figure 6), and one of the input shares generated by the client (input_share). Its outputs is the Aggregator's initial preparation state. * PrepState.next(inbound: Vec[Bytes]) -> outbound is the deterministic preparation-state update algorithm run by each Aggregator. It updates the Aggregator's preparation state (an instance of PrepState) and returns either its outbound message for the current round or, if this is the last round, its output share. An exception is raised if a valid output share could not be recovered. The input of this algorithm is the sequence of inbound messages from the previous round or, if this is the first round, an empty vector. In effect, each Aggregator moves through a linear state machine with ROUNDS+1 states. The Aggregator enters the first state on using the initialization algorithm, and the update algorithm advances the Aggregator to the next state. Thus, in addition to defining the number of rounds (ROUNDS), a VDAF instance defines the state of the aggregator after each round. TODO Consider how to bake this "linear state machine" condition into the syntax. Given that Python 3 is used as our pseudocode, it's easier to specify the preparation state using a class. The preparation-state update accomplishes two tasks that are essential to most schemes: recovery of output shares from the input shares, and a multi-party computation carried out by the Aggregators to ensure that their output shares are valid. The VDAF abstraction boundary is drawn so that an Aggregator only recovers an output share if it is deemed valid (at least, based on the Aggregator's view of the protocol). Another way to draw this boundary woulds be to have the Aggregators recover output shares first, then verify that they are valid. However, this would allow the possibility of misusing the API by, say, aggregating an invalid output share. Moreover, in some protocols, like Prio+ [AGJOP21] it is necessary for the Aggregators to interact in order to recover output shares at all. Patton, et al. Expires 28 April 2022 [Page 12] Internet-Draft VDAF October 2021 Note that it is possible for a VDAF to specify ROUNDS == 0, in which case each Aggregator runs the preparation-state update algorithm once and immediately recovers its output share without interacting with the other Aggregators. However, most, if not all, constructions will require some amount of interaction in order to ensure validity of the output shares (while also maintaining privacy). 4.4. Aggregation Once an aggregator holds validated output shares for a batch of measurements (where batches are defined by the application), it combines them into a share of the desired aggregate result. This algorithm is performed locally at each Aggregator, without communication with the other Aggregators. * output_to_aggregate_shares(agg_param, output_shares) is the deterministic aggregation algorithm. It is run by each Aggregator over the output shares it has computed over a batch of measurement inputs. Aggregator 0 Aggregator 1 Aggregator SHARES-1 ============ ============ =================== out_share_0_0 out_share_1_0 out_share_[SHARES-1]_0 out_share_0_1 out_share_1_1 out_share_[SHARES-1]_1 out_share_0_2 out_share_1_2 out_share_[SHARES-1]_2 ... ... ... out_share_0_B out_share_1_B out_share_[SHARES-1]_B | | | V V V +-----------+ +-----------+ +-----------+ | out2agg | | out2agg | ... | out2agg | +-----------+ +-----------+ +-----------+ | | | V V V agg_share_0 agg_share_1 agg_share_[SHARES-1] Figure 4: Aggregation of output shares. `B` indicates the number of measurements in the batch. For simplicity, we have written this algorithm and the unsharding algorithm below in "one-shot" form, where all shares for a batch are provided at the same time. Some VDAFs may also support a "streaming" form, where shares are processed one at a time. Patton, et al. Expires 28 April 2022 [Page 13] Internet-Draft VDAF October 2021 4.5. Unsharding After the Aggregators have aggregated a sufficient number of output shares, each sends its aggregate share to the Collector, who runs the following algorithm to recover the following output: * aggregate_shares_to_result(agg_param, agg_shares: Vec[Bytes]) -> agg_result is run by the Collector in order to compute the aggregate result from the Aggregators' shares. The length of agg_shares MUST be SHARES. This algorithm is deterministic. Aggregator 0 Aggregator 1 Aggregator SHARES-1 ============ ============ =================== agg_share_0 agg_share_1 agg_share_[SHARES-1] | | | V V V +-----------------------------------------------+ | aggregate_shares_to_result | +-----------------------------------------------+ | V agg_result Collector ========= Figure 5: Computation of the final aggregate result from aggregate shares. QUESTION Maybe the aggregation algorithms should be randomized in order to allow the Aggregators (or the Collector) to add noise for differential privacy. (See the security considerations of [I-D.draft-gpew-priv-ppm].) Or is this out-of-scope of this document? 4.6. Execution of a VDAF Executing a VDAF involves the concurrent evaluation of the VDAF on individual inputs and aggregation of the recovered output shares. This is captured by the following example algorithm: Patton, et al. Expires 28 April 2022 [Page 14] Internet-Draft VDAF October 2021 def run_vdaf(agg_param, nonces: Vec[Bytes], input_batch: Vec[Bytes]): # Distribute long-lived parameters. (public_param, verify_params) = vdaf_setup() output_shares = [] for (nonce, input) in zip(nonces, input_batch): # Each client shards its input into shares. input_shares = measurement_to_input_shares(public_param, input) # Each aggregator initializes its preparation state. prep_states = [] for j in range(SHARES): prep_states.append(validation_init( verify_params[j], agg_param, nonce, input_shares[j])) # Aggregators recover their output shares. inbound = [] for i in range(ROUNDS+1): outbound = [] for j in range(SHARES): outbound.append(prep_states[j].next(inbound)) # This is where we would send messages over the network # in a distributed VDAF computation. inbound = outbound # The final outputs of validation are the output shares # for this input. output_shares.append(outbound) # Each aggregator aggregates its output shares into an # aggregate share. agg_shares = [] for j in range(SHARES): my_output_shares = [out[j] for out in output_shares] my_agg_share = output_to_aggregate_shares(my_output_shares) agg_shares.append(my_agg_share) # Collector unshards the aggregate. return aggregate_shares_to_result(agg_shares) Figure 6: Execution of a VDAF. Patton, et al. Expires 28 April 2022 [Page 15] Internet-Draft VDAF October 2021 The inputs to this algorithm are the aggregation parameter agg_param, a list of nonces nonces, and a batch of Client inputs input_batch. The aggregation parameter is chosen by the aggregators prior to executing the VDAF. This document does not specify how the nonces are chosen, but some of our security considerations require that the nonces be unique for each VDAF evaluation. See Section 8 for details. Another important question this document leaves out of scope is how a VDAF is to be executed by aggregators distributed over a real network. Algorithm run_vdaf prescribes the protocol's execution in a "benign" environment in which there is no adversary and messages are passed among the protocol participants over secure point-to-point channels. In reality, these channels need to be instantiated by some "wrapper protocol" that implements suitable cryptographic functionalities. Moreover, some fraction of the Aggregators (or Clients) may be malicious and diverge from their prescribed behaviors. Section 8 describes the execution of the VDAF in various adversarial environments and what properties the wrapper protocol needs to provide in each. 5. Preliminaries This section describes the cryptographic primitives that are common to the VDAFs specified in this document. 5.1. Key Derivation A key-derivation scheme defines a method for deriving symmetric keys and a method for expanding a symmetric into an arbitrary length key stream are required. This scheme consists of the following algorithms: * get_key(init_key, aux_input) -> key derives a fresh key key from an initial key init_key and auxiliary input aux_input. The length of init_key and key MUST be equal to KEY_SIZE. * key_stream_init(key) -> state: KeyStream returns a key stream generator that is used to generate an arbitrary length stream of pseudorandom bytes. The length of key MUST be KEY_SIZE. * KeyStream.next(len: Unsigned) -> (new_state: KeyStream, output) returns the next len bytes of the key stream and updates the key stream generator state. The length of the output MUST be len. TODO This functionality closely resembles what people usually think of as an extract-then-expand KDF, but differs somewhat in its syntax and, also, its required security properties. Can we Patton, et al. Expires 28 April 2022 [Page 16] Internet-Draft VDAF October 2021 get the same functionality from something that's more commonplace? HKDF doesn't fit the bill, unfortunately, because keys can only be expanded to a fairly short length. Our application requires a rather long key stream. Associated types: * KeyStream represents the state of the key stream generator. Associated constants: * KEY_SIZE is the size of keys for the key-derivation scheme. 5.2. Finite Fields In this document we only consider finite fields of the form GF(p) for prime p. Finite field elements are represented by a type Field that defines binary operators for addition and multiplication in the field. The type also defines the following associated functions: * Field.zeros(len: Unsigned) -> output: Vec[Field] returns a vector of zeros. The length of output MUST be len. * Field.rand_vec(len: Unsigned) -> output: Vec[Field] returns a vector of random field elements. The length of output MUST be len. NOTE In reality this would be achieved by generating a random key and expanding it into a sequence of field elements using a key derivation scheme. This should probably be made explicit. * Field.encode_vec(data: Vec[Field]) -> encoded_data: Bytes represents the input data as a byte string encoded_data. * Field.decode_vec(encoded_data: Bytes) -> data: Vec[Field] reverse encoded_vec, returning the vector of field elements encoded by encoded_data. Raises an exception if the input does not encode a valid vector of field elements. 5.2.1. Deriving a Pseudorandom Vector TODO Specify the following function in terms of a key-derivation scheme. It'll use key_stream_init to create a KeyStream object and read from it multiple times. * expand(Field, key: Bytes, len: Unsigned) -> output: Vec[Field] expands a key into a pseudorandom sequence of field elements. Patton, et al. Expires 28 April 2022 [Page 17] Internet-Draft VDAF October 2021 5.2.2. Inner product of Vectors TODO Specify the following: * inner_product(left: Vec[Field], right: Vec[Field]) -> Field computes the inner product of left and right. 6. prio3 NOTE This construction has not undergone significant security analysis. NOTE An implementation of this VDAF can be found here (https://github.com/abetterinternet/libprio-rs/blob/main/src/vdaf/ prio3.rs). This section describes a VDAF suitable for the following data aggregation task. Each Client measurement is encoded as a vector over a finite field, and the aggregate is computed by summing the vectors element-wise. Validity is defined by an arithmetic circuit C that takes as input a vector of field elements x: if C(x) == 0, then we say that x is valid; otherwise, we say that x is invalid. A number of useful measurement types can be defined this way: * Simples statistics, like sum, average, and standard deviation; * Estimation of quantiles, via a histogram; and * Linear regression. This VDAF does not have an aggregation parameter. Instead, the output share is derived from an input share by applying a fixed map. See Section 7 for an example of a VDAF that makes meaningful use of the aggregation parameter. While the construction is derived from the original Prio system [CGB17], prio3 takes advantage of optimizations described later in [BBCGGI19] that improve communication complexity significantly. The etymology of the term prio3 is that it descends from the original Prio construction. A second iteration was deployed in the [ENPA] system, and like the VDAF described here, the ENPA system was built from techniques introduced by [BBCGGI19]. However, was specialized for a particular measurement type. The goal of prio3 is to provide the same level of generality as the original system. The way prio3 ensures privacy is quite simple: the Client shards its encoded input vector x into a number of additive secret shares, one for each Aggregator. Aggregators sum up their vector shares locally, Patton, et al. Expires 28 April 2022 [Page 18] Internet-Draft VDAF October 2021 and once enough shares have been aggregated, each sends its share of the result to the Collector, who recovers the aggregate result by adding up the vectors. The main problem that needs to be solved is to verify that the additive shares generated by the Client add up to a valid input, i.e., that C(x)=0. The solution introduced by [BBCGGI19] is what they call a zero-knowledge proof system on distributed data. Viewing the Client as the prover and the Aggregators as the (distributed) verifier, the goal is to devise a protocol by which the Client convinces the Aggregators that they hold secret shares of a valid input, without revealing the input itself. The core tool for accomplishing this task is a refinement of Probabilistically Checkable Proof (PCP) systems called a Fully Linear Proof (FLP) system. We describe FLPs in detail below. Briefly, the Client generates a "proof" of its input's validity and distributes additive shares of the proof among the Aggregators. Each Aggregator then performs a computation on its input share and proof share locally and sends the result to the other Aggregators. Combining the results yields allows each Aggregator to decide if the input shares are valid. prio3 can be viewed as a transformation of a particular class of FLP systems into a VDAF. The next section describes FLPs in detail, and the construction is given in Section 6.2. 6.1. Fully Linear Proof (FLP) Systems Conceptually, an FLP system is a two-party protocol executed by a prover and a verifier. In actual use, however, the prover's computation is carried out by the Client, and the verifier's computation is distributed among the Aggregators. (More on this in Section 6.2.) An FLP specifies the following core algorithms (encoding of inputs is described in Section 6.1.1: * flp_prove(input: Vec[Field], prove_rand: Vec[Field], joint_rand: Vec[Field]) -> proof: Vec[Field] is the deterministic proof- generation algorithm run by the prover. Its inputs are the encoded input, the "prover randomness" prove_rand, and the "joint randomness" joint_rand. The proof randomness is used only by the prover, but the joint randomness is shared by both the prover and verifier. Type Field is a finite field as defined in Section 5.2. * flp_query(input: Vec[Field], proof: Vec[Field], query_rand: Vec[Field], joint_rand: Vec[Field]) -> verifier: Vec[Field] is the query-generation algorithm run by the verifier. This is is used to "query" the input and proof. The result of the query (i.e., Patton, et al. Expires 28 April 2022 [Page 19] Internet-Draft VDAF October 2021 the output of this function) is called the "verifier message". In addition to the input and proof, this algorithm takes as input the query randomness query_rand and the joint randomness joint_rand. The former is used only by the verifier, but the latter is the same randomness used by the prover. * flp_decide(verifier: Vec[Field]) -> decision: Boolean is the deterministic decision algorithm run by the verifier. It takes as input the verifier message and outputs a boolean indicating if the input from whence it was generated is valid. A concrete FLP defines the following constants: * JOINT_RAND_LEN: Unsigned is the length of the joint randomness in number of field elements. * PROVE_RAND_LEN: Unsigned is the length of the prover randomness. * QUERY_RAND_LEN: Unsigned is the length of the query randomness. * INPUT_LEN: Unsigned is the length of the input. * OUTPUT_LEN: Unsigned is the length of the aggregable output. * PROOF_LEN: Unsigned is the length of the proof. * VERIFIER_LEN: Unsigned is the length of the verifier message. Our application requires that the FLP is "fully linear" in the sense defined in [BBCGGI19]. As a practical matter, what this property implies is that the query-generation algorithm can be run by each aggregator locally on its share of the input and proof, and the results can be combined to recover the verifier message. In the remainder, the result generated by an aggregator will be referred to as its "verifier share". An FLP is executed by the prover and verifier as follows: Patton, et al. Expires 28 April 2022 [Page 20] Internet-Draft VDAF October 2021 def run_flp(input: Vec[Field]): joint_rand = Field.rand_vec(JOINT_RAND_LEN) prove_rand = Field.rand_vec(PROVE_RAND_LEN) query_rand = Field.rand_vec(QUERY_RAND_LEN) # Prover generates the proof. proof = flp_prove(input, prove_rand, joint_rand) # Verifier queries the input and proof. verifier = flp_query(input, proof, query_rand, joint_rand) # Verifier decides if the input is valid. return flp_decide(verifier) Figure 7: Execution of an FLP. The proof system is constructed so that, if input is a valid input, then run_flp(input) always returns True. On the other hand, if input is invalid, then as long as joint_rand and query_rand are generated uniform randomly, the output is False with overwhelming probability. In addition, the proof system is designed so that the verifier message leaks nothing about the input (in an information theoretic sense). See Definition 3.9 from [BBCGGI19] for details. An FLP is typically constructed from an arithmetic circuit that in turn defines validity. However, in the remainder we do not explicitly mention this circuit and allow validity to be defined by the set of inputs recognized by the FLP when run as described above. Note that [BBCGGI19] defines a much larger class of fully linear proof systems; what is called a FLP here is called a 1.5-round, public-coin, interactive oracle proof system in their paper. 6.1.1. Encoding the Input The type of measurement being aggregated is defined by the FLP. Hence, the FLP also specifies a method of encoding raw measurements as a vector of field elements: * flp_encode(measurement: Bytes) -> input: Vec[Field] encodes a raw measurement as a vector of field elements. The returned input MUST be of length INPUT_LEN. An error is raised if the measurement cannot be represented as a valid input. Patton, et al. Expires 28 April 2022 [Page 21] Internet-Draft VDAF October 2021 In addition, for some FLPs, the encoded input includes redundant field elements that are useful for checking the proof, but which are not needed after the proof has been checked. Thus the FLP defines an algorithm for truncating the input to the length of the aggregated output: * flp_truncate(input: Vec[Field]) -> output: Vec[Field] maps an encoded input to an aggregable output. The length of the input MUST be INPUT_LEN and the length of the output MUST be OUTPUT_LEN. Note that, taken together, these two functionalities correspond roughly to the notion of Affine-aggregatable encodings (AFEs) from [CGB17]. 6.2. Construction This VDAF involves a single round of communication (ROUNDS == 1). It is defined for at least two Aggregators, but no more than 255. (2 <= SHARES <= 255). 6.2.1. Setup The setup algorithm generates a symmetric key shared by all of the aggregators. The key is used to derive unique joint randomness for the FLP query-generation algorithm run by the aggregators during preparation. def vdaf_setup(): k_query_init = gen_rand(KEY_SIZE) verify_param = [ (j, k_query_init) for j in range(SHARES) ] return (None, verify_param) Figure 8: The setup algorithm for prio3. 6.2.2. Sharding Recall from Section 6.1 that the syntax for FLP systems calls for "joint randomness" shared by the prover (i.e., the Client) and the verifier (i.e., the Aggregators). VDAFs have no such notion. Instead, the Client derives the joint randomness from its input in a way that allows the Aggregators to reconstruct it from their input shares. (Note that this idea comes from Section 6.2.3 of [BBCGGI19].) The input-distribution algorithm involves the following steps: 1. Encode the Client's raw measurement as an input for the FLP Patton, et al. Expires 28 April 2022 [Page 22] Internet-Draft VDAF October 2021 2. Shard the input into a sequence of input shares. 3. Derive the joint randomness from the input shares. 4. Run the FLP proof-generation algorithm using prover randomness generated locally. 5. Shard the proof into a sequence of input shares. The input and proof shares of one Aggregator (below we call it the "leader") are vectors of field elements. For shares of the other aggregators (below we call them the "helpers") as constant-sized symmetric keys. This is accomplished by mapping the key to a key stream and expanding the key stream into a pseudorandom vector of field elements. This involves a key-derivation scheme described in Section 5 and the helper function expand described in the same section. This algorithm also makes use of a pair of helper functions for encoding the leader share and helper share. These are called encode_leader_share and encode_helper_share respectively and they are described in Section 6.2.6. def measurement_to_input_shares(_, measurement): input = flp_encode(measurement) k_joint_rand = zeros(SEED_SIZE) # Generate input shares. leader_input_share = input k_helper_input_shares = [] k_helper_blinds = [] k_helper_hints = [] for j in range(SHARES-1): k_blind = gen_rand(KEY_SIZE) k_share = gen_rand(KEY_SIZE) helper_input_share = expand(Field, k_share, INPUT_LEN) leader_input_share -= helper_input_share k_hint = get_key(k_blind, byte(j+1) + Field.encode_vec(helper_input_share)) k_joint_rand ^= k_hint k_helper_input_shares.append(k_share) k_helper_blinds.append(k_blind) k_helper_hints.append(k_hint) k_leader_blind = gen_rand(KEY_SIZE) k_leader_hint = get_key(k_leader_blind, byte(0) + Field.encode_vec(leader_input_share)) k_joint_rand ^= k_leader_hint Patton, et al. Expires 28 April 2022 [Page 23] Internet-Draft VDAF October 2021 # Finish joint randomness hints. for j in range(SHARES-1): k_helper_hints[i] ^= k_joint_rand k_leader_hint ^= k_joint_rand # Generate the proof shares. joint_rand = expand(Field, k_joint_rand, JOINT_RAND_LEN) prove_rand = expand(Field, gen_rand(KEY_SIZE), PROVE_RAND_LEN) proof = flp_prove(input, prove_rand, joint_rand) leader_proof_share = proof k_helper_proof_shares = [] for j in range(SHARES-1): k_share = gen_rand(KEY_SIZE) k_helper_proof_shares.append(k_share) helper_proof_share = expand(Field, k_share, PROOF_LEN) leader_proof_share -= helper_proof_share input_shares = [] input_shares.append(encode_leader_share( leader_input_share, leader_proof_share, k_leader_blind, k_leader_hint, )) for j in range(SHARES-1): input_shares.append(encode_helper_share( k_helper_input_share[j], k_helper_proof_share[j], k_helper_blinds[j], k_helper_hints[j], )) return input_shares Figure 9: Input-distribution algorithm for prio3. 6.2.3. Preparation This section describes the process of recovering output shares from the input shares. The high-level idea is that each of the Aggregators runs the FLP query-generation algorithm on its share of the input and proof and exchange shares of the verifier message. Once they've done that, each runs the FLP decision algorithm on the verifier message locally to decide whether to accept. In addition, the Aggregators must ensure that they have all used the same joint randomness for the query-generation algorithm. The joint randomness is generated by a symmetric key. Each Aggregator derives an XOR secret share of this key from its input share and the "blind" Patton, et al. Expires 28 April 2022 [Page 24] Internet-Draft VDAF October 2021 generated by the client. Before it can run the query-generation algorithm, it must first gather the XOR secret shares derived by the other Aggregators. So that the Aggregators can avoid an extra round of communication, the client sends each Aggregator a "hint" equal to the XOR of the other Aggregators' shares of the joint randomness key. However, this leaves open the possibility that the client cheated by, say, forcing the Aggregators to use joint randomness the biases the proof check procedure some way in its favor. To mitigate this, the Aggregators also check that they have all computed the same joint randomness key before accepting their output shares. NOTE This optimization somewhat diverges from Section 6.2.3 of [BBCGGI19]. We'll need to understand better how this impacts security. The preparation state is defined as follows. It involves two additional helper functions, encode_verifer_share and decode_verifier_share, both of which are defined in Section 6.2.6. class PrepState: def __init__(verify_param, _, nonce, r_input_share): (j, k_query_init) = verify_param if j == 0: # leader (self.input_share, self.proof_share, k_blind, k_hint) = decode_leader_share(r_input_share) else: (k_input_share, k_proof_share, k_blind, k_hint) = decode_helper_share(r_input_share) self.input_share = expand(Field, k_input_share, INPUT_LEN) self.proof_share = expand(Field, k_proof_share, PROOF_LEN) self.k_joint_rand_share = get_key( k_blind, byte(j) + self.input_share) self.k_joint_rand = k_hint ^ self.k_joint_rand_share self.k_query_rand = get_key(k_query_init, byte(255) + nonce) self.step = "ready" def next(self, inbound: Vec[Bytes]): if self.step == "ready" and len(inbound) == 0: joint_rand = expand(Field, self.k_joint_rand, JOINT_RAND_LEN) query_rand = expand(Field, self.k_query_rand, QUERY_RAND_LEN) verifier_share = flp_query( self.input_share, self.proof_share, query_rand, joint_rand) self.output_share = flp_truncate(input_share) Patton, et al. Expires 28 April 2022 [Page 25] Internet-Draft VDAF October 2021 self.step = "waiting" return encode_verifier_share( self.k_joint_rand_share, self.verifier_share, ) elif self.step == "waiting" and len(inbound) == SHARES: k_joint_rand = zeros(KEY_SIZE) verifier = vec_zeros(VERIFIER_LEN) for r_share in inbound: (k_joint_rand_share, verifier_share) = decode_verifier_share(r_share) k_joint_rand ^= k_joint_rand_share verifer += verifier_share if k_joint_rand != self.k_joint_rand: raise ERR_INVALID if not flp_decide(verifier): raise ERR_INVALID return Field.encode_vec(self.output_share) else: raise ERR_INVALID_STATE Figure 10: Preparation state for prio3. NOTE JOINT_RAND_LEN may be 0, in which case the joint randomness computation is not necessary. Should we bake this option into the spec? 6.2.4. Aggregation def output_to_aggregate_shares(_, output_shares: Vec[Bytes]): agg_share = vec_zeros(OUTPUT_LEN) for output_share in output_shares: agg_share += Field.decode_vec(output_share) return Field.encode_vec(agg_share) Figure 11: Aggregation algorithm for prio3. 6.2.5. Unsharding def aggregate_shares_to_result(_, agg_shares: Vec[Bytes]): agg = vec_zeros(OUTPUT_LEN) for agg_share in agg_shares: agg += Field.decode_vec(agg_share) return Field.encode_vec(agg) Figure 12: Computation of the aggregate result for prio3. Patton, et al. Expires 28 April 2022 [Page 26] Internet-Draft VDAF October 2021 6.2.6. Helper Functions TODO Specify the following functionalities. * encode_leader_share(input_share: Vec[Field], proof_share: Vec[Field], blind, hint) -> encoded: Bytes encodes a leader share as a byte string. * encode_helper_share(input_share, proof_sahre, blind, hint) -> encoded: Bytes encodes a helper share as a byte string. * decode_leader_share and decode_helper_share decode a leader and helper share respectively. * encode_verifier_share(hint, verifier_share: Vec[Field]) -> encoded encodes a hint and verifier share as a byte string. * decode_verifier_share decodes a verifier share. 7. hits NOTE An implementation of this VDAF can be found here (https://github.com/abetterinternet/libprio-rs/blob/main/src/vdaf/ hits.rs). This section specifies hits, a VDAF for the following task. Each Client holds a BITS-bit string and the Aggregators hold a set of l-bit strings, where l <= BITS. We will refer to the latter as the set of "candidate prefixes". The Aggregators' goal is to count how many inputs are prefixed by each candidate prefix. This functionality is the core component of the privacy-preserving t- heavy-hitters protocol of [BBCGGI21]. At a high level, the protocol works as follows. 1. Each Clients runs the input-distribution algorithm on its n-bit string and sends an input share to each Aggregator. 2. The Aggregators agree on an initial set of candidate prefixes, say 0 and 1. 3. The Aggregators evaluate the VDAF on each set of input shares and aggregate the recovered output shares. The aggregation parameter is the set of candidate prefixes. 4. The Aggregators send their aggregate shares to the Collector, who combines them to recover the counts of each candidate prefix. Patton, et al. Expires 28 April 2022 [Page 27] Internet-Draft VDAF October 2021 5. Let H denote the set of prefixes that occurred at least t times. If the prefixes all have length BITS, then H is the set of t- heavy-hitters. Otherwise compute the next set of candidate prefixes as follows. For each p in H, add add p || 0 and p || 1 to the set. Repeat step 3 with the new set of candidate prefixes. hits is constructed from an "Incremental Distributed Point Function (IDPF)", a primitive described by [BBCGGI21] that generalizes the notion of a Distributed Point Function (DPF) [GI14]. Briefly, a DPF is used to distribute the computation of a "point function", a function that evaluates to zero on every input except at a programmable "point". The computation is distributed in such a way that no one party knows either the point or what it evaluates to. An IDPF generalizes this "point" to a path on a full binary tree from the root to one of the leaves. It is evaluated on an "index" representing a unique node of the tree. If the node is on the path, then function evaluates to to a non-zero value; otherwise it evaluates to zero. This structure allows an IDPF to provide the functionality required for the above protocol, while at the same time ensuring the same degree of privacy as a DPF. Our VDAF composes an IDPF with the "secure sketching" protocol of [BBCGGI21]. This protocol ensures that evaluating a set of input shares on a unique set of candidate prefixes results in shares of a "one-hot" vector, i.e., a vector that is zero everywhere except for one element, which is equal to one. The name hits is an anagram of "hist", which is short for "histogram". It is a nod toward the "subset histogram" problem formulated by [BBCGGI21] and for which the hits is a solution. 7.1. Incremental Distributed Point Functions (IDPFs) NOTE An implementation of IDPFs can be found here (https://github.com/google/distributed_point_functions/). An IDPF is defined over a domain of size 2^BITS, where BITS is constant defined by the IDPF. The Client specifies an index alpha and values beta, one for each "level" 1 <= l <= BITS. The key generation generates two IDPF keys, one for each Aggregator. When evaluated at index 0 <= x < 2^l, each IDPF share returns an additive share of beta[l] if x is the l-bit prefix of alpha and shares of zero otherwise. CP What does it mean for x to be the l-bit prefix of alpha? We need to be a bit more precise here. Patton, et al. Expires 28 April 2022 [Page 28] Internet-Draft VDAF October 2021 CP Why isn't the domain size actually 2^(BITS+1), i.e., the number of nodes in a binary tree of height BITS (excluding the root)? Each beta[l] is a pair of elements of a finite field. Each level MAY have different field parameters. Thus a concrete IDPF specifies associated types Field[1], Field[2], ..., and Field[BITS] defining, respectively, the field parameters at level 1, level 2, ..., and level BITS. An IDPF is comprised of the following algorithms (let type Value[l] denote (Field[l], Field[l]) for each level l): * idpf_gen(alpha: Unsigned, beta: (Value[1], ..., Value[BITS])) -> key: (IDPFKey, IDPFKey) is the randomized key-generation algorithm run by the client. Its inputs are the index alpha and the values beta. The value of alpha MUST be in range [0, 2^BITS). * IDPFKey.eval(l: Unsigned, x: Unsigned) -> value: Value[l]) is deterministic, stateless key-evaluation algorithm run by each Aggregator. It returns the value corresponding to index x. The value of l MUST be in [1, BITS] and the value of x MUST be in range [2^(l-1), 2^l). A concrete IDPF specifies a single associated constant: * BITS: Unsigned is the length of each Client input. A concrete IDPF also specifies the following associated types: * Field[l] for each level 1 <= l <= BITS. Each defines the same methods and associated constants as Field in Section 6. Note that IDPF construction of [BBCGGI21] uses one field for the inner nodes of the tree and a different, larger field for the leaf nodes. See [BBCGGI21], Section 4.3. Finally, an implementation note. The interface for IPDFs specified here is stateless, in the sense that there is no state carried between IPDF evaluations. This is to align the IDPF syntax with the VDAF abstraction boundary, which does not include shared state across across VDAF evaluations. In practice, of course, it will often be beneficial to expose a stateful API for IDPFs and carry the state across evaluations. 7.2. Construction The VDAF involves two rounds of communication (ROUNDS == 2) and is defined for two Aggregators (SHARES == 2). Patton, et al. Expires 28 April 2022 [Page 29] Internet-Draft VDAF October 2021 7.2.1. Setup The verification parameter is a symmetric key shared by both Aggregators. This VDAF has no public parameter. def vdaf_setup(): k_verify_init = gen_rand(KEY_SIZE) return (None, [(0, k_verify_init), (1, k_verify_init)]) Figure 13: The setup algorithm for hits. 7.2.1.1. Client The client's input is an IDPF index, denoted alpha. The values are pairs of field elements (1, k) where each k is chosen at random. This random value is used as part of the secure sketching protocol of [BBCGGI21]. After evaluating their IDPF key shares on the set of candidate prefixes, the sketching protocol is used by the Aggregators to verify that they hold shares of a one-hot vector. In addition, for each level of the tree, the prover generates random elements a, b, and c and computes A = -2*a + k B = a*a + b - k*a + c and sends additive shares of a, b, c, A and B to the Aggregators. Putting everything together, the input-distribution algorithm is defined as follows. Function encode_input_share is defined in Section 7.2.5. Patton, et al. Expires 28 April 2022 [Page 30] Internet-Draft VDAF October 2021 def measurement_to_input_shares(_, alpha): if alpha < 2**BITS: raise ERR_INVALID_INPUT # Prepare IDPF values. beta = [] correlation_shares_0, correlation_shares_1 = [], [] for l in range(1,BITS+1): (k, a, b, c) = Field[l].rand_vec(4) # Construct values of the form (1, k), where k # is a random field element. beta += [(1, k)] # Create secret shares of correlations to aid # the Aggregators' computation. A = -2*a+k B = a*a + b - a * k + c correlation_share = Field[l].rand_vec(5) correlation_shares_1.append(correlation_share) correlation_shares_0.append( [a, b, c, A, B] - correlation_share) # Generate IDPF shares. (key_0, key_1) = idpf_gen(input, beta) input_shares = [ encode_input_share(key_0, correlation_shares_0), encode_input_share(key_1, correlation_shares_1), ] return input_shares Figure 14: The input-distribution algorithm for hits. TODO It would be more efficient to represent the correlation shares using PRG seeds as suggested in [BBCGGI21]. 7.2.2. Preparation The aggregation parameter encodes a sequence of candidate prefixes. When an Aggregator receives an input share from the Client, it begins by evaluating its IDPF share on each candidate prefixe, recovering a pair of vectors of field elements data_share and auth_share, The Aggregators use auth_share and the correlation shares provided by the Client to verify that their data_share vectors are additive shares of a one-hot vector. Patton, et al. Expires 28 April 2022 [Page 31] Internet-Draft VDAF October 2021 class PrepState: def __init__(verify_param, agg_param, nonce, input_share): (self.l, self.candidate_prefixes) = decode_indexes(agg_param) (self.idpf_key, self.correlation_shares) = decode_input_share(input_share) (self.party_id, k_verify_init) = verify_param self.k_verify_rand = get_key(k_verify_init, nonce) self.step = "ready" def next(self, inbound: Vec[Bytes]): l = self.l (a_share, b_share, c_share, A_share, B_share) = correlation_shares[l-1] if self.step == "ready" and len(inbound) == 0: # Evaluation IPPF on candidate prefixes. data_share, auth_share = [], [] for x in self.candiate_prefixes: value = kdpf_key.eval(l, x) data_share.append(value[0]) auth_share.append(value[1]) # Prepare first sketch verification message. r = expand(Field[l], self.k_verify_rand, len(data_share)) verifier_share_1 = [ a_share + inner_product(data_share, r), b_share + inner_product(data_share, r * r), c_share + inner_product(auth_share, r), ] self.output_share = data_share self.step = "sketch round 1" return verifier_share_1 elif self.step == "sketch round 1" and len(inbound) == 2: verifier_1 = Field[l].deocde_vec(inbound[0]) + \ Field[l].deocde_vec(inbound[1]) verifier_share_2 = [ (verifier_1[0] * verifier_1[0] \ - verifier_1[1] \ - verifier_1[2]) * self.party_id \ + A_share * verifer_1[0] \ + B_share ] self.step = "sketch round 2" return Field[l].encode_vec(verifier_share_2) Patton, et al. Expires 28 April 2022 [Page 32] Internet-Draft VDAF October 2021 elif self.step == "sketch round 2" and len(inbound) == 2: verifier_2 = Field[l].decode_vec(inbound[0]) + \ Field[l].decode_vec(inbound[1]) if verifier_2 != 0: raise ERR_INVALID return Field[l].encode_vec(self.output_share) else: raise ERR_INVALID_STATE Figure 15: Preparation state for hits. 7.2.3. Aggregation def output_to_aggregate_shares(agg_param, output_shares: Vec[Bytes]): (l, candidate_prefixes) = decode_indexes(agg_param) if len(output_shares) != len(candidate_prefixes): raise ERR_INVALID_INPUT agg_share = Field[l].vec_zeros(len(candidate_prefixes)) for output_share in output_shares: agg_share += Field[l].decode_vec(output_share) return Field[l].encode_vec(agg_share) Figure 16: Aggregation algorithm for hits. 7.2.4. Unsharding def aggregate_shares_to_result(agg_param, agg_shares: Vec[Bytes]): (l, _) = decode_indexes(agg_param) if len(agg_shares) != 2: raise ERR_INVALID_INPUT agg = Field[l].decode_vec(agg_shares[0]) + \ Field[l].decode_vec(agg_shares[1]J) return Field[l].encode_vec(agg) Figure 17: Computation of the aggregate result for hits. 7.2.5. Helper Functions TODO Specify the following functionalities: * encode_input_share is used to encode an input share, consisting of an IDPF key share and correlation shares. * decode_input_share is used to decode an input share. Patton, et al. Expires 28 April 2022 [Page 33] Internet-Draft VDAF October 2021 * decode_indexes(encoded: Bytes) -> (l: Unsigned, indexes: Vec[Unsigned]) decodes a sequence of indexes, i.e., candidate indexes for IDFP evaluation. The value of l MUST be in range [1, BITS] and indexes[i] MUST be in range [2^(l-1), 2^l) for all i. An error is raised if encoded cannot be decoded. 8. Security Considerations NOTE: This is a brief outline of the security considerations. This section will be filled out more as the draft matures and security analyses are completed. Multi-party protocols for privacy-preserving measurement have two essential security gaols: 1. Privacy: An attacker that controls the network, the Collector, and a subset of Clients and Aggregators learns nothing about the measurements of honest Clients beyond what it can deduce from the aggregate result. 2. Robustness: An attacker that controls the network and a subset of Clients cannot cause the Collector to compute anything other than the aggregate of the measurements of honest Clients. (Note that it is also possible to consider a stronger form of robustness, where the attacker also controls a subset of Aggregators. See [BBCGGI19], Section 6.3.) A VDAF is the core cryptographic primitive of a protocol that achieves these goals. It is not sufficient on its own, however. The application will need to assure a few security properties, for example: * Securely distributing the long-lived parameters. * Establishing secure channels: - Confidential and authentic channels among Aggregators, and between the Aggregators and the Collector; and - Confidential and Aggregator-authenticated channels between Clients and Aggregators. * Enforcing the non-collusion properties required of the specific VDAF in use. In such an environment, a VDAF provides the high-level privacy property described above: The collector learns only the aggregate measurement, and nothing about individual measurements aside from what can be inferred from the aggregate result. The aggregators Patton, et al. Expires 28 April 2022 [Page 34] Internet-Draft VDAF October 2021 learn neither individual measurements nor the aggregate result. The collector is assured that the aggregate statistic accurately reflects the inputs as long as the Aggregators correctly executed their role in the VDAF. On their own, VDAFs do not mitigate Sybil attacks [Dou02]. In this attack, the adversary observes a subset of input shares transmitted by a Client it is interested in. It allows the input shares to be processed, but corrupts and picks bogus inputs for the remaining Clients. Applications can guard against these risks by adding additional controls on measurement submission, such as client authentication and rate limits. VDAFs do not inherently provide differential privacy [Dwo06]. The VDAF approach to private measurement can be viewed as complementary to differential privacy, relying on non-collusion instead of statistical noise to protect the privacy of the inputs. It is possible that a future VDAF could incorporate differential privacy features, e.g., by injecting noise before the sharding stage and removing it after unsharding. 9. IANA Considerations This document makes no request of IANA. 10. References 10.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, . 10.2. Informative References [AGJOP21] Addanki, S., Garbe, K., Jaffe, E., Ostrovsky, R., and A. Polychroniadou, "Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares", 2021, . Patton, et al. Expires 28 April 2022 [Page 35] Internet-Draft VDAF October 2021 [BBCGGI19] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and Y. Ishai, "Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs", CRYPTO 2019 , 2019, . [BBCGGI21] Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and Y. Ishai, "Lightweight Techniques for Private Heavy Hitters", IEEE S&P 2021 , 2021, . [CGB17] Corrigan-Gibbs, H. and D. Boneh, "Prio: Private, Robust, and Scalable Computation of Aggregate Statistics", NSDI 2017 , 2017, . [Dou02] Douceur, J., "The Sybil Attack", IPTPS 2002 , 2002, . [Dwo06] Dwork, C., "Differential Privacy", ICALP 2006 , 2006, . [ENPA] "Exposure Notification Privacy-preserving Analytics (ENPA) White Paper", 2021, . [EPK14] Erlingsson, Ú., Pihur, V., and A. Korolova, "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response", CCS 2014 , 2014, . [GI14] Gilboa, N. and Y. Ishai, "Distributed Point Functions and Their Applications", EUROCRYPT 2014 , 2014, . [I-D.draft-gpew-priv-ppm] Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood, "Privacy Preserving Measurement", Work in Progress, Internet-Draft, draft-gpew-priv-ppm-00, 25 October 2021, . [OriginTelemetry] "Origin Telemetry", 2020, . Patton, et al. Expires 28 April 2022 [Page 36] Internet-Draft VDAF October 2021 [Vad16] Vadhan, S., "The Complexity of Differential Privacy", 2016, . Acknowledgments Thanks to Henry Corrigan-Gibbs, Mariana Raykova, and Christopher Wood for useful feedback on the syntax of VDAF schemes. Authors' Addresses Christopher Patton Cloudflare, Inc. Email: cpatton@cloudflare.com Richard L. Barnes Cisco Email: rlb@ipv.sx Phillipp Schoppmann Google Email: schoppmann@google.com Patton, et al. Expires 28 April 2022 [Page 37]