< draft-patton-cfrg-vdaf-01.txt   draft-irtf-cfrg-vdaf-00.txt >
CFRG C. Patton CFRG R. L. Barnes
Internet-Draft Cloudflare, Inc. Internet-Draft Cisco
Intended status: Informational R. L. Barnes Intended status: Informational C. Patton
Expires: 6 September 2022 Cisco Expires: 29 October 2022 Cloudflare, Inc.
P. Schoppmann P. Schoppmann
Google Google
5 March 2022 27 April 2022
Verifiable Distributed Aggregation Functions Verifiable Distributed Aggregation Functions
draft-patton-cfrg-vdaf-01 draft-irtf-cfrg-vdaf-00
Abstract Abstract
This document describes Verifiable Distributed Aggregation Functions This document describes Verifiable Distributed Aggregation Functions
(VDAFs), a family of multi-party protocols for computing aggregate (VDAFs), a family of multi-party protocols for computing aggregate
statistics over user measurements. These protocols are designed to statistics over user measurements. These protocols are designed to
ensure that, as long as at least one aggregation server executes the ensure that, as long as at least one aggregation server executes the
protocol honestly, individual measurements are never seen by any protocol honestly, individual measurements are never seen by any
server in the clear. At the same time, VDAFs allow the servers to server in the clear. At the same time, VDAFs allow the servers to
detect if a malicious or misconfigured client submitted an input that detect if a malicious or misconfigured client submitted an input that
skipping to change at page 2, line 4 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on 6 September 2022. This Internet-Draft will expire on 29 October 2022.
Copyright Notice Copyright Notice
Copyright (c) 2022 IETF Trust and the persons identified as the Copyright (c) 2022 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/ Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document. license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
skipping to change at page 2, line 38 skipping to change at page 2, line 38
4.3. Preparation . . . . . . . . . . . . . . . . . . . . . . . 11 4.3. Preparation . . . . . . . . . . . . . . . . . . . . . . . 11
4.4. Aggregation . . . . . . . . . . . . . . . . . . . . . . . 14 4.4. Aggregation . . . . . . . . . . . . . . . . . . . . . . . 14
4.5. Unsharding . . . . . . . . . . . . . . . . . . . . . . . 15 4.5. Unsharding . . . . . . . . . . . . . . . . . . . . . . . 15
4.6. Execution of a VDAF . . . . . . . . . . . . . . . . . . . 15 4.6. Execution of a VDAF . . . . . . . . . . . . . . . . . . . 15
5. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 17 5. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 17
5.1. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17 5.1. Finite Fields . . . . . . . . . . . . . . . . . . . . . . 17
5.1.1. Auxiliary Functions . . . . . . . . . . . . . . . . . 18 5.1.1. Auxiliary Functions . . . . . . . . . . . . . . . . . 18
5.1.2. FFT-Friendly Fields . . . . . . . . . . . . . . . . . 19 5.1.2. FFT-Friendly Fields . . . . . . . . . . . . . . . . . 19
5.1.3. Parameters . . . . . . . . . . . . . . . . . . . . . 19 5.1.3. Parameters . . . . . . . . . . . . . . . . . . . . . 19
5.2. Pseudorandom Generators . . . . . . . . . . . . . . . . . 20 5.2. Pseudorandom Generators . . . . . . . . . . . . . . . . . 20
5.2.1. Constructions . . . . . . . . . . . . . . . . . . . . 21 5.2.1. PrgAes128 . . . . . . . . . . . . . . . . . . . . . . 21
6. Prio3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6. Prio3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.1. Fully Linear Proof (FLP) Systems . . . . . . . . . . . . 23 6.1. Fully Linear Proof (FLP) Systems . . . . . . . . . . . . 23
6.1.1. Encoding the Input . . . . . . . . . . . . . . . . . 26 6.1.1. Encoding the Input . . . . . . . . . . . . . . . . . 26
6.2. Construction . . . . . . . . . . . . . . . . . . . . . . 26 6.2. Construction . . . . . . . . . . . . . . . . . . . . . . 26
6.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 27 6.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 27
6.2.2. Sharding . . . . . . . . . . . . . . . . . . . . . . 28 6.2.2. Sharding . . . . . . . . . . . . . . . . . . . . . . 28
6.2.3. Preparation . . . . . . . . . . . . . . . . . . . . . 30 6.2.3. Preparation . . . . . . . . . . . . . . . . . . . . . 30
6.2.4. Aggregation . . . . . . . . . . . . . . . . . . . . . 32 6.2.4. Aggregation . . . . . . . . . . . . . . . . . . . . . 32
6.2.5. Unsharding . . . . . . . . . . . . . . . . . . . . . 33 6.2.5. Unsharding . . . . . . . . . . . . . . . . . . . . . 33
6.2.6. Auxiliary Functions . . . . . . . . . . . . . . . . . 33 6.2.6. Auxiliary Functions . . . . . . . . . . . . . . . . . 33
6.3. A General-Purpose FLP . . . . . . . . . . . . . . . . . . 35 6.3. A General-Purpose FLP . . . . . . . . . . . . . . . . . . 35
6.3.1. Overview . . . . . . . . . . . . . . . . . . . . . . 35 6.3.1. Overview . . . . . . . . . . . . . . . . . . . . . . 35
6.3.2. Validity Circuits . . . . . . . . . . . . . . . . . . 38 6.3.2. Validity Circuits . . . . . . . . . . . . . . . . . . 38
6.3.3. Construction . . . . . . . . . . . . . . . . . . . . 40 6.3.3. Construction . . . . . . . . . . . . . . . . . . . . 40
6.4. Instantiations . . . . . . . . . . . . . . . . . . . . . 43 6.4. Instantiations . . . . . . . . . . . . . . . . . . . . . 43
6.4.1. Prio3Aes128Count . . . . . . . . . . . . . . . . . . 43 6.4.1. Prio3Aes128Count . . . . . . . . . . . . . . . . . . 44
6.4.2. Prio3Aes128Sum . . . . . . . . . . . . . . . . . . . 44 6.4.2. Prio3Aes128Sum . . . . . . . . . . . . . . . . . . . 45
6.4.3. Prio3Aes128Histogram . . . . . . . . . . . . . . . . 46 6.4.3. Prio3Aes128Histogram . . . . . . . . . . . . . . . . 46
7. Poplar1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7. Poplar1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7.1. Incremental Distributed Point Functions (IDPFs) . . . . . 49 7.1. Incremental Distributed Point Functions (IDPFs) . . . . . 49
7.2. Construction . . . . . . . . . . . . . . . . . . . . . . 50 7.2. Construction . . . . . . . . . . . . . . . . . . . . . . 50
7.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 50 7.2.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 50
7.2.2. Preparation . . . . . . . . . . . . . . . . . . . . . 52 7.2.2. Preparation . . . . . . . . . . . . . . . . . . . . . 52
7.2.3. Aggregation . . . . . . . . . . . . . . . . . . . . . 54 7.2.3. Aggregation . . . . . . . . . . . . . . . . . . . . . 54
7.2.4. Unsharding . . . . . . . . . . . . . . . . . . . . . 54 7.2.4. Unsharding . . . . . . . . . . . . . . . . . . . . . 54
7.2.5. Helper Functions . . . . . . . . . . . . . . . . . . 55 7.2.5. Helper Functions . . . . . . . . . . . . . . . . . . 55
8. Security Considerations . . . . . . . . . . . . . . . . . . . 55 8. Security Considerations . . . . . . . . . . . . . . . . . . . 55
skipping to change at page 6, line 30 skipping to change at page 6, line 30
input. The protocol also specifies a multi-party computation for input. The protocol also specifies a multi-party computation for
verifying that at most one string among a set of candidates is a verifying that at most one string among a set of candidates is a
prefix of the client's input. prefix of the client's input.
In Section 7 we describe a VDAF called Poplar1 that implements In Section 7 we describe a VDAF called Poplar1 that implements
this functionality. this functionality.
The remainder of this document is organized as follows: Section 3 The remainder of this document is organized as follows: Section 3
gives a brief overview of VDAFs; Section 4 defines the syntax for gives a brief overview of VDAFs; Section 4 defines the syntax for
VDAFs; Section 5 defines various functionalities that are common to VDAFs; Section 5 defines various functionalities that are common to
our constructions; Section 7 describes the Poplar1 construction; our constructions; Section 6 describes the Prio3 construction;
Section 6 describes the Prio3 construction; and Section 8 enumerates Section 7 describes the Poplar1 construction; and Section 8
the security considerations for VDAFs. enumerates the security considerations for VDAFs.
2. Conventions and Definitions 2. Conventions and Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in "OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here. capitals, as shown here.
Algorithms in this document are written in Python 3. Type hints are Algorithms in this document are written in Python 3. Type hints are
skipping to change at page 9, line 49 skipping to change at page 9, line 49
Note that the preparation step performs two functions: Verification Note that the preparation step performs two functions: Verification
and conversion. Conversion translates input shares into output and conversion. Conversion translates input shares into output
shares that are compatible with the aggregation function. shares that are compatible with the aggregation function.
Verification ensures that aggregating the recovered output shares Verification ensures that aggregating the recovered output shares
will not lead to a garbled aggregate result. will not lead to a garbled aggregate result.
The remainder of this section defines the VDAF interface in terms of The remainder of this section defines the VDAF interface in terms of
an abstract base class Vdaf. This class defines the set of methods an abstract base class Vdaf. This class defines the set of methods
and attributes a concrete VDAF must provide. The attributes are and attributes a concrete VDAF must provide. The attributes are
listed in [{vdaf-param}}; the methods are defined in the subsections listed in Table 1; the methods are defined in the subsections that
that follow. follow.
+=============+=============================================+ +=============+=============================================+
| Parameter | Description | | Parameter | Description |
+=============+=============================================+ +=============+=============================================+
| ROUNDS | Number of rounds of communication during | | ROUNDS | Number of rounds of communication during |
| | the preparation phase (Section 4.3) | | | the preparation phase (Section 4.3) |
+-------------+---------------------------------------------+ +-------------+---------------------------------------------+
| SHARES | Number of input shares into which each | | SHARES | Number of input shares into which each |
| | measurement is sharded (Section 4.2) | | | measurement is sharded (Section 4.2) |
+-------------+---------------------------------------------+ +-------------+---------------------------------------------+
skipping to change at page 19, line 22 skipping to change at page 19, line 22
# Add the right operand to the left and return the result. # Add the right operand to the left and return the result.
def vec_add(left: Vec[Field], right: Vec[Field]): def vec_add(left: Vec[Field], right: Vec[Field]):
return list(map(lambda x: x[0] + x[1], zip(left, right))) return list(map(lambda x: x[0] + x[1], zip(left, right)))
Figure 8: Common functions for finite fields. Figure 8: Common functions for finite fields.
5.1.2. FFT-Friendly Fields 5.1.2. FFT-Friendly Fields
Some VDAFs require fields that are suitable for efficient computation Some VDAFs require fields that are suitable for efficient computation
of the discrete Fourier transform. (One example is prio3 (Section 6) of the discrete Fourier transform. (One example is Prio3 (Section 6)
when instantiated with the generic FLP of Section 6.3.3.) when instantiated with the generic FLP of Section 6.3.3.)
Specifically, a field is said to be "FFT-friendly" if, in addition to Specifically, a field is said to be "FFT-friendly" if, in addition to
satisfying the interface described in Section 5.1, it implements the satisfying the interface described in Section 5.1, it implements the
following method: following method:
* Field.gen() -> Field returns the generator of a large subgroup of * Field.gen() -> Field returns the generator of a large subgroup of
the multiplicative group. the multiplicative group.
FFT-friendly fields also define the following parameter: FFT-friendly fields also define the following parameter:
skipping to change at page 20, line 38 skipping to change at page 20, line 38
| GEN_ORDER | 2^66 | | GEN_ORDER | 2^66 |
+--------------+--------------------------------+ +--------------+--------------------------------+
Table 3: Field128, an FFT-friendly field. Table 3: Field128, an FFT-friendly field.
5.2. Pseudorandom Generators 5.2. Pseudorandom Generators
A pseudorandom generator (PRG) is used to expand a short, A pseudorandom generator (PRG) is used to expand a short,
(pseudo)random seed into a long string of pseudorandom bits. A PRG (pseudo)random seed into a long string of pseudorandom bits. A PRG
suitable for this document implements the interface specified in this suitable for this document implements the interface specified in this
section. Concrete constructions are described in Section 5.2.1. section. Concrete constructions are described in the subsections
that folllow.
PRGs are defined by a class Prg with the following associated PRGs are defined by a class Prg with the following associated
parameter: parameter:
* SEED_SIZE: Unsigned is the size (in bytes) of a seed. * SEED_SIZE: Unsigned is the size (in bytes) of a seed.
A concrete Prg implements the following class method: A concrete Prg implements the following class method:
* Prg(seed: Bytes, info: Bytes) constructs an instance of Prg from * Prg(seed: Bytes, info: Bytes) constructs an instance of Prg from
the given seed and info string. The seed MUST be of length the given seed and info string. The seed MUST be of length
skipping to change at page 21, line 39 skipping to change at page 21, line 39
vec = [] vec = []
while len(vec) < length: while len(vec) < length:
x = OS2IP(prg.next(Field.ENCODED_SIZE)) x = OS2IP(prg.next(Field.ENCODED_SIZE))
x &= m x &= m
if x < Field.MODULUS: if x < Field.MODULUS:
vec.append(Field(x)) vec.append(Field(x))
return vec return vec
Figure 9: Derived class methods for PRGs. Figure 9: Derived class methods for PRGs.
5.2.1. Constructions 5.2.1. PrgAes128
5.2.1.1. PrgAes128
OPEN ISSUE Phillipp points out that a fixed-key mode of AES may be OPEN ISSUE Phillipp points out that a fixed-key mode of AES may be
more performant (https://eprint.iacr.org/2019/074.pdf). See more performant (https://eprint.iacr.org/2019/074.pdf). See
https://github.com/cjpatton/vdaf/issues/32 for details. https://github.com/cjpatton/vdaf/issues/32 for details.
Our first construction, PrgAes128, converts a blockcipher, namely Our first construction, PrgAes128, converts a blockcipher, namely
AES-128, into a PRG. Seed expansion involves two steps. In the AES-128, into a PRG. Seed expansion involves two steps. In the
first step, CMAC [RFC4493] is applied to the seed and info string to first step, CMAC [RFC4493] is applied to the seed and info string to
get a fresh key. In the second step, the fresh key is used in CTR- get a fresh key. In the second step, the fresh key is used in CTR-
mode to produce a key stream for generating the output. A fixed mode to produce a key stream for generating the output. A fixed
skipping to change at page 22, line 23 skipping to change at page 22, line 23
self.key = AES128-CMAC(seed, info) self.key = AES128-CMAC(seed, info)
def next(self, length): def next(self, length):
self.length_consumed += length self.length_consumed += length
# CTR-mode encryption of the all-zero string of the desired # CTR-mode encryption of the all-zero string of the desired
# length and using a fixed, all-zero IV. # length and using a fixed, all-zero IV.
stream = AES128-CTR(key, zeros(16), zeros(self.length_consumed)) stream = AES128-CTR(key, zeros(16), zeros(self.length_consumed))
return stream[-length:] return stream[-length:]
Figure 10: Definition of PRG PrgBlockCipher(Aes128). Figure 10: Definition of PRG PrgAes128.
6. Prio3 6. Prio3
NOTE This construction has not undergone significant security NOTE This construction has not undergone significant security
analysis. analysis.
This section describes "Prio3", a VDAF for Prio [CGB17]. Prio is This section describes "Prio3", a VDAF for Prio [CGB17]. Prio is
suitable for a wide variety of aggregation functions, including (but suitable for a wide variety of aggregation functions, including (but
not limited to) sum, mean, standard deviation, estimation of not limited to) sum, mean, standard deviation, estimation of
quantiles (e.g., median), and linear regression. In fact, the scheme quantiles (e.g., median), and linear regression. In fact, the scheme
skipping to change at page 26, line 7 skipping to change at page 26, line 7
proof = Flp.prove(inp, prove_rand, joint_rand) proof = Flp.prove(inp, prove_rand, joint_rand)
# Verifier queries the input and proof. # Verifier queries the input and proof.
verifier = Flp.query(inp, proof, query_rand, joint_rand, num_shares) verifier = Flp.query(inp, proof, query_rand, joint_rand, num_shares)
# Verifier decides if the input is valid. # Verifier decides if the input is valid.
return Flp.decide(verifier) return Flp.decide(verifier)
Figure 11: Execution of an FLP. Figure 11: Execution of an FLP.
The proof system is constructed so that, if input is a valid input, The proof system is constructed so that, if input is a valid input,
then run_flp(Flp,. input) always returns True. On the other hand, if then run_flp(Flp, input) always returns True. On the other hand, if
input is invalid, then as long as joint_rand and query_rand are input is invalid, then as long as joint_rand and query_rand are
generated uniform randomly, the output is False with overwhelming generated uniform randomly, the output is False with overwhelming
probability. probability.
We remark that [BBCGGI19] defines a much larger class of fully linear We remark that [BBCGGI19] defines a much larger class of fully linear
proof systems than we consider here. In particular, what is called proof systems than we consider here. In particular, what is called
an "FLP" here is called a 1.5-round, public-coin, interactive oracle an "FLP" here is called a 1.5-round, public-coin, interactive oracle
proof system in their paper. proof system in their paper.
6.1.1. Encoding the Input 6.1.1. Encoding the Input
skipping to change at page 27, line 29 skipping to change at page 27, line 29
+-------------+-----------------------------------------------+ +-------------+-----------------------------------------------+
| Prep | Tuple[Vec[Flp.Field], Optional[Bytes], Bytes] | | Prep | Tuple[Vec[Flp.Field], Optional[Bytes], Bytes] |
+-------------+-----------------------------------------------+ +-------------+-----------------------------------------------+
| OutShare | Vec[Flp.Field] | | OutShare | Vec[Flp.Field] |
+-------------+-----------------------------------------------+ +-------------+-----------------------------------------------+
| AggShare | Vec[Flp.Field] | | AggShare | Vec[Flp.Field] |
+-------------+-----------------------------------------------+ +-------------+-----------------------------------------------+
| AggResult | Vec[Unsigned] | | AggResult | Vec[Unsigned] |
+-------------+-----------------------------------------------+ +-------------+-----------------------------------------------+
Table 5: Associated parameters for the prio3 VDAF. Table 5: Associated parameters for the Prio3 VDAF.
6.2.1. Setup 6.2.1. Setup
The setup algorithm generates a symmetric key shared by all of the The setup algorithm generates a symmetric key shared by all of the
Aggregators. The key is used to derive query randomness for the FLP Aggregators. The key is used to derive query randomness for the FLP
query-generation algorithm run by the Aggregators during preparation. query-generation algorithm run by the Aggregators during preparation.
An Aggregator's verification parameter also includes its "ID", a An Aggregator's verification parameter also includes its "ID", a
unique integer in [0, SHARES). unique integer in [0, SHARES).
def setup(Prio3): def setup(Prio3):
k_query_init = gen_rand(Prio3.Prg.SEED_SIZE) k_query_init = gen_rand(Prio3.Prg.SEED_SIZE)
verify_param = [(j, k_query_init) for j in range(Prio3.SHARES)] verify_param = [(j, k_query_init) for j in range(Prio3.SHARES)]
return (None, verify_param) return (None, verify_param)
Figure 12: The setup algorithm for prio3. Figure 12: The setup algorithm for Prio3.
6.2.2. Sharding 6.2.2. Sharding
Recall from Section 6.1 that the FLP syntax calls for "joint Recall from Section 6.1 that the FLP syntax calls for "joint
randomness" shared by the prover (i.e., the Client) and the verifier randomness" shared by the prover (i.e., the Client) and the verifier
(i.e., the Aggregators). VDAFs have no such notion. Instead, the (i.e., the Aggregators). VDAFs have no such notion. Instead, the
Client derives the joint randomness from its input in a way that Client derives the joint randomness from its input in a way that
allows the Aggregators to reconstruct it from their input shares. allows the Aggregators to reconstruct it from their input shares.
(This idea is based on the Fiat-Shamir heuristic and is described in (This idea is based on the Fiat-Shamir heuristic and is described in
Section 6.2.3 of [BBCGGI19].) Section 6.2.3 of [BBCGGI19].)
skipping to change at page 30, line 25 skipping to change at page 30, line 25
)) ))
for j in range(Prio3.SHARES-1): for j in range(Prio3.SHARES-1):
input_shares.append(Prio3.encode_helper_share( input_shares.append(Prio3.encode_helper_share(
k_helper_input_shares[j], k_helper_input_shares[j],
k_helper_proof_shares[j], k_helper_proof_shares[j],
k_helper_blinds[j], k_helper_blinds[j],
k_helper_hints[j], k_helper_hints[j],
)) ))
return input_shares return input_shares
Figure 13: Input-distribution algorithm for prio3. Figure 13: Input-distribution algorithm for Prio3.
6.2.3. Preparation 6.2.3. Preparation
This section describes the process of recovering output shares from This section describes the process of recovering output shares from
the input shares. The high-level idea is that each Aggregator first the input shares. The high-level idea is that each Aggregator first
queries its input and proof share locally, then exchanges its queries its input and proof share locally, then exchanges its
verifier share with the other Aggregators. The verifier shares are verifier share with the other Aggregators. The verifier shares are
then combined into the verifier message, which is used to decide then combined into the verifier message, which is used to decide
whether to accept. whether to accept.
skipping to change at page 32, line 35 skipping to change at page 32, line 35
verifier = vec_add(verifier, verifier_share) verifier = vec_add(verifier, verifier_share)
if Prio3.Flp.JOINT_RAND_LEN > 0: if Prio3.Flp.JOINT_RAND_LEN > 0:
k_joint_rand_check = xor(k_joint_rand_check, k_joint_rand_check = xor(k_joint_rand_check,
k_joint_rand_share) k_joint_rand_share)
return Prio3.encode_prepare_message(verifier, return Prio3.encode_prepare_message(verifier,
k_joint_rand_check) k_joint_rand_check)
Figure 14: Preparation state for prio3. Figure 14: Preparation state for Prio3.
6.2.4. Aggregation 6.2.4. Aggregation
Aggregating a set of output shares is simply a matter of adding up Aggregating a set of output shares is simply a matter of adding up
the vectors element-wise. the vectors element-wise.
def out_shares_to_agg_share(Prio3, _agg_param, out_shares): def out_shares_to_agg_share(Prio3, _agg_param, out_shares):
agg_share = Prio3.Flp.Field.zeros(Prio3.Flp.OUTPUT_LEN) agg_share = Prio3.Flp.Field.zeros(Prio3.Flp.OUTPUT_LEN)
for out_share in out_shares: for out_share in out_shares:
agg_share = vec_add(agg_share, out_share) agg_share = vec_add(agg_share, out_share)
return agg_share return agg_share
Figure 15: Aggregation algorithm for prio3. Figure 15: Aggregation algorithm for Prio3.
6.2.5. Unsharding 6.2.5. Unsharding
To unshard a set of aggregate shares, the Collector first adds up the To unshard a set of aggregate shares, the Collector first adds up the
vectors element-wise. It then converts each element of the vector vectors element-wise. It then converts each element of the vector
into an integer. into an integer.
def agg_shares_to_result(Prio3, _agg_param, agg_shares): def agg_shares_to_result(Prio3, _agg_param, agg_shares):
agg = Prio3.Flp.Field.zeros(Prio3.Flp.OUTPUT_LEN) agg = Prio3.Flp.Field.zeros(Prio3.Flp.OUTPUT_LEN)
for agg_share in agg_shares: for agg_share in agg_shares:
agg = vec_add(agg, agg_share) agg = vec_add(agg, agg_share)
return list(map(lambda x: x.as_unsigned(), agg)) return list(map(lambda x: x.as_unsigned(), agg))
Figure 16: Computation of the aggregate result for prio3. Figure 16: Computation of the aggregate result for Prio3.
6.2.6. Auxiliary Functions 6.2.6. Auxiliary Functions
def encode_leader_share(Prio3, def encode_leader_share(Prio3,
input_share, input_share,
proof_share, proof_share,
k_blind, k_blind,
k_hint): k_hint):
encoded = Bytes() encoded = Bytes()
encoded += Prio3.Flp.Field.encode_vec(input_share) encoded += Prio3.Flp.Field.encode_vec(input_share)
skipping to change at page 35, line 4 skipping to change at page 35, line 4
l = Prio3.Flp.Field.ENCODED_SIZE * Prio3.Flp.VERIFIER_LEN l = Prio3.Flp.Field.ENCODED_SIZE * Prio3.Flp.VERIFIER_LEN
encoded_verifier, encoded = encoded[:l], encoded[l:] encoded_verifier, encoded = encoded[:l], encoded[l:]
verifier = Prio3.Flp.Field.decode_vec(encoded_verifier) verifier = Prio3.Flp.Field.decode_vec(encoded_verifier)
k_joint_rand = None k_joint_rand = None
if Prio3.Flp.JOINT_RAND_LEN > 0: if Prio3.Flp.JOINT_RAND_LEN > 0:
l = Prio3.Prg.SEED_SIZE l = Prio3.Prg.SEED_SIZE
k_joint_rand, encoded = encoded[:l], encoded[l:] k_joint_rand, encoded = encoded[:l], encoded[l:]
if len(encoded) != 0: if len(encoded) != 0:
raise ERR_DECODE raise ERR_DECODE
return (verifier, k_joint_rand) return (verifier, k_joint_rand)
Figure 17: Helper functions required for prio3. Figure 17: Helper functions required for Prio3.
6.3. A General-Purpose FLP 6.3. A General-Purpose FLP
This section describes an FLP based on the construction from in This section describes an FLP based on the construction from in
[BBCGGI19], Section 4.2. We begin in Section 6.3.1 with an overview [BBCGGI19], Section 4.2. We begin in Section 6.3.1 with an overview
of their proof system and the extensions to their proof system made of their proof system and the extensions to their proof system made
here. The construction is specified in Section 6.3.3. here. The construction is specified in Section 6.3.3.
OPEN ISSUE We're not yet sure if specifying this general-purpose OPEN ISSUE We're not yet sure if specifying this general-purpose
FLP is desirable. It might be preferable to specify specialized FLP is desirable. It might be preferable to specify specialized
skipping to change at page 42, line 13 skipping to change at page 42, line 13
wire into the kth call to gadget G_i. wire into the kth call to gadget G_i.
4. Compute the "wire polynomials". That is, for every i in [H] and 4. Compute the "wire polynomials". That is, for every i in [H] and
j in [L_i], construct poly_wire_i[j-1], the jth wire polynomial j in [L_i], construct poly_wire_i[j-1], the jth wire polynomial
for the ith gadget, as follows: for the ith gadget, as follows:
* Let w = [seed_i[j-1], wire_i[j-1,0], ..., wire_i[j-1,M_i-1]]. * Let w = [seed_i[j-1], wire_i[j-1,0], ..., wire_i[j-1,M_i-1]].
* Let padded_w = w + Field.zeros(P_i - len(w)). * Let padded_w = w + Field.zeros(P_i - len(w)).
NOTE We pad w to the nearest power of 2 so that we can use FFT
for interpolating the wire polynomials. Perhaps there is some
clever math for picking wire_inp in a way that avoids having
to pad.
* Let poly_wire_i[j-1] be the lowest degree polynomial for which * Let poly_wire_i[j-1] be the lowest degree polynomial for which
poly_wire_i[j-1](alpha_i^k) == padded_w[k] for all k in [P_i]. poly_wire_i[j-1](alpha_i^k) == padded_w[k] for all k in [P_i].
5. Compute the "gadget polynomials". That is, for every i in [H]: 5. Compute the "gadget polynomials". That is, for every i in [H]:
* Let poly_gadget_i = G_i(poly_wire_i[0], ..., poly_wire_i[L_i- * Let poly_gadget_i = G_i(poly_wire_i[0], ..., poly_wire_i[L_i-
1]). That is, evaluate the circuit G_i on the wire 1]). That is, evaluate the circuit G_i on the wire
polynomials for the ith gadget. (Arithmetic is in the ring of polynomials for the ith gadget. (Arithmetic is in the ring of
polynomials over Field.) polynomials over Field.)
skipping to change at page 44, line 5 skipping to change at page 44, line 11
NOTE Reference implementations of each of these VDAFs can be found NOTE Reference implementations of each of these VDAFs can be found
in https://github.com/cjpatton/vdaf/blob/main/poc/vdaf_prio3.sage. in https://github.com/cjpatton/vdaf/blob/main/poc/vdaf_prio3.sage.
6.4.1. Prio3Aes128Count 6.4.1. Prio3Aes128Count
Our first instance of Prio3 is for a simple counter: Each measurement Our first instance of Prio3 is for a simple counter: Each measurement
is either one or zero and the aggregate result is the sum of the is either one or zero and the aggregate result is the sum of the
measurements. measurements.
This instance uses PrgAes128 (see Section 5.2.1) as its PRG. Its This instance uses PrgAes128 (Section 5.2.1) as its PRG. Its
validity circuit, denoted Count, uses Field64 (Table 2) as its finite validity circuit, denoted Count, uses Field64 (Table 2) as its finite
field. Its gadget, denoted Mul, is the degree-2, arity-2 gadget field. Its gadget, denoted Mul, is the degree-2, arity-2 gadget
defined as defined as
def Mul(x, y): def Mul(x, y):
return x * y return x * y
The validity circuit is defined as The validity circuit is defined as
def Count(inp: Vec[Field64]): def Count(inp: Vec[Field64]):
skipping to change at page 45, line 5 skipping to change at page 45, line 11
Table 8: Parameters of validity circuit Table 8: Parameters of validity circuit
Count. Count.
6.4.2. Prio3Aes128Sum 6.4.2. Prio3Aes128Sum
The next instance of Prio3 supports summing of integers in a pre- The next instance of Prio3 supports summing of integers in a pre-
determined range. Each measurement is an integer in range [0, determined range. Each measurement is an integer in range [0,
2^bits), where bits is an associated parameter. 2^bits), where bits is an associated parameter.
This instance of prio3 uses PrgAes128 (see Section 5.2.1) as its PRG. This instance of Prio3 uses PrgAes128 (Section 5.2.1) as its PRG.
Its validity circuit, denoted Sum, uses Field128 (Table 3) as its Its validity circuit, denoted Sum, uses Field128 (Table 3) as its
finite field. The measurement is encoded as a length-bits vector of finite field. The measurement is encoded as a length-bits vector of
field elements, where the lth element of the vector represents the field elements, where the lth element of the vector represents the
lth bit of the summand: lth bit of the summand:
def encode(Sum, measurement: Integer): def encode(Sum, measurement: Integer):
if 0 > measurement or measurement >= 2^Sum.INPUT_LEN: if 0 > measurement or measurement >= 2^Sum.INPUT_LEN:
raise ERR_INPUT raise ERR_INPUT
encoded = [] encoded = []
skipping to change at page 46, line 31 skipping to change at page 46, line 31
Table 9: Parameters of validity circuit Sum. Table 9: Parameters of validity circuit Sum.
6.4.3. Prio3Aes128Histogram 6.4.3. Prio3Aes128Histogram
This instance of Prio3 allows for estimating the distribution of the This instance of Prio3 allows for estimating the distribution of the
measurements by computing a simple histogram. Each measurement is an measurements by computing a simple histogram. Each measurement is an
arbitrary integer and the aggregate result counts the number of arbitrary integer and the aggregate result counts the number of
measurements that fall in a set of fixed buckets. measurements that fall in a set of fixed buckets.
This instance of prio3 uses PrgAes128 (see Section 5.2.1) as its PRG. This instance of Prio3 uses PrgAes128 (Section 5.2.1) as its PRG.
Its validity circuit, denoted Histogram, uses Field128 (Table 3) as Its validity circuit, denoted Histogram, uses Field128 (Table 3) as
its finite field. The measurement is encoded as a one-hot vector its finite field. The measurement is encoded as a one-hot vector
representing the bucket into which the measurement falls (let bucket representing the bucket into which the measurement falls (let bucket
denote a sequence of monotonically increasing integers): denote a sequence of monotonically increasing integers):
def encode(Histogram, measurement: Integer): def encode(Histogram, measurement: Integer):
boundaries = buckets + [Infinity] boundaries = buckets + [Infinity]
encoded = [Field128(0) for _ in range(len(boundaries))] encoded = [Field128(0) for _ in range(len(boundaries))]
for i in range(len(boundaries)): for i in range(len(boundaries)):
if measurement <= boundaries[i]: if measurement <= boundaries[i]:
skipping to change at page 49, line 23 skipping to change at page 49, line 23
Our VDAF composes an IDPF with the "secure sketching" protocol of Our VDAF composes an IDPF with the "secure sketching" protocol of
[BBCGGI21]. This protocol ensures that evaluating a set of input [BBCGGI21]. This protocol ensures that evaluating a set of input
shares on a unique set of candidate prefixes results in shares of a 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-hot" vector, i.e., a vector that is zero everywhere except for
one element, which is equal to one. one element, which is equal to one.
7.1. Incremental Distributed Point Functions (IDPFs) 7.1. Incremental Distributed Point Functions (IDPFs)
An IDPF is defined over a domain of size 2^BITS, where BITS is 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 constant defined by the IDPF. The Client specifies an index alpha
and values beta, one for each "level" 1 <= l <= BITS. The key and a pair of values beta, one for each "level" 1 <= l <= BITS. The
generation generates two IDPF keys, one for each Aggregator. When key generation generates two IDPF keys, one for each Aggregator.
evaluated at index 0 <= x < 2^l, each IDPF share returns an additive When evaluated at index 0 <= x < 2^l, each IDPF share returns an
share of beta[l] if x is the l-bit prefix of alpha and shares of zero additive share of beta[l] if x is the l-bit prefix of alpha and
otherwise. shares of zero otherwise.
CP What does it mean for x to be the l-bit prefix of alpha? We CP What does it mean for x to be the l-bit prefix of alpha? We
need to be a bit more precise here. need to be a bit more precise here.
CP Why isn't the domain size actually 2^(BITS+1), i.e., the number 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)? 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 Each beta[l] is a pair of elements of a finite field. Each level MAY
have different field parameters. Thus a concrete IDPF specifies have different field parameters. Thus a concrete IDPF specifies
associated types Field[1], Field[2], ..., and Field[BITS] defining, associated types Field[1], Field[2], ..., and Field[BITS] defining,
skipping to change at page 52, line 28 skipping to change at page 52, line 28
# Create secret shares of correlations to aid # Create secret shares of correlations to aid
# the Aggregators' computation. # the Aggregators' computation.
A = -2*a+k A = -2*a+k
B = a*a + b - a * k + c B = a*a + b - a * k + c
correlation_share = Field[l].rand_vec(5) correlation_share = Field[l].rand_vec(5)
correlation_shares_1.append(correlation_share) correlation_shares_1.append(correlation_share)
correlation_shares_0.append( correlation_shares_0.append(
[a, b, c, A, B] - correlation_share) [a, b, c, A, B] - correlation_share)
# Generate IDPF shares. # Generate IDPF shares.
(key_0, key_1) = idpf_gen(input, beta) (key_0, key_1) = idpf_gen(alpha, beta)
input_shares = [ input_shares = [
encode_input_share(key_0, correlation_shares_0), encode_input_share(key_0, correlation_shares_0),
encode_input_share(key_1, correlation_shares_1), encode_input_share(key_1, correlation_shares_1),
] ]
return input_shares return input_shares
Figure 20: The input-distribution algorithm for poplar1. Figure 20: The input-distribution algorithm for poplar1.
TODO It would be more efficient to represent the correlation TODO It would be more efficient to represent the shares of a, b,
shares using PRG seeds as suggested in [BBCGGI21]. and c using PRG seeds as suggested in [BBCGGI21].
7.2.2. Preparation 7.2.2. Preparation
The aggregation parameter encodes a sequence of candidate prefixes. The aggregation parameter encodes a sequence of candidate prefixes.
When an Aggregator receives an input share from the Client, it begins When an Aggregator receives an input share from the Client, it begins
by evaluating its IDPF share on each candidate prefix, recovering a by evaluating its IDPF share on each candidate prefix, recovering a
pair of vectors of field elements data_share and auth_share, The pair of vectors of field elements data_share and auth_share, The
Aggregators use auth_share and the correlation shares provided by the Aggregators use auth_share and the correlation shares provided by the
Client to verify that their data_share vectors are additive shares of Client to verify that their data_share vectors are additive shares of
a one-hot vector. a one-hot vector.
skipping to change at page 53, line 26 skipping to change at page 53, line 26
def next(self, inbound: Optional[Bytes]): def next(self, inbound: Optional[Bytes]):
l = self.l l = self.l
(a_share, b_share, c_share, (a_share, b_share, c_share,
A_share, B_share) = correlation_shares[l-1] A_share, B_share) = correlation_shares[l-1]
if self.step == "ready" and inbound == None: if self.step == "ready" and inbound == None:
# Evaluate IDPF on candidate prefixes. # Evaluate IDPF on candidate prefixes.
data_share, auth_share = [], [] data_share, auth_share = [], []
for x in self.candidate_prefixes: for x in self.candidate_prefixes:
value = kdpf_key.eval(l, x) value = self.idpf_key.eval(l, x)
data_share.append(value[0]) data_share.append(value[0])
auth_share.append(value[1]) auth_share.append(value[1])
# Prepare first sketch verification message. # Prepare first sketch verification message.
r = Prg.expand_into_vec(Field[l], self.k_verify_rand, len(data_share)) r = Prg.expand_into_vec(Field[l], self.k_verify_rand, len(data_share))
verifier_share_1 = [ verifier_share_1 = [
a_share + inner_product(data_share, r), a_share + inner_product(data_share, r),
b_share + inner_product(data_share, r * r), b_share + inner_product(data_share, r * r),
c_share + inner_product(auth_share, r), c_share + inner_product(auth_share, r),
] ]
skipping to change at page 58, line 29 skipping to change at page 58, line 29
<https://dl.acm.org/doi/10.1145/2660267.2660348>. <https://dl.acm.org/doi/10.1145/2660267.2660348>.
[GI14] Gilboa, N. and Y. Ishai, "Distributed Point Functions and [GI14] Gilboa, N. and Y. Ishai, "Distributed Point Functions and
Their Applications", EUROCRYPT 2014 , 2014, Their Applications", EUROCRYPT 2014 , 2014,
<https://link.springer.com/ <https://link.springer.com/
chapter/10.1007/978-3-642-55220-5_35>. chapter/10.1007/978-3-642-55220-5_35>.
[I-D.draft-gpew-priv-ppm] [I-D.draft-gpew-priv-ppm]
Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood, Geoghegan, T., Patton, C., Rescorla, E., and C. A. Wood,
"Privacy Preserving Measurement", Work in Progress, "Privacy Preserving Measurement", Work in Progress,
Internet-Draft, draft-gpew-priv-ppm-00, 25 October 2021, Internet-Draft, draft-gpew-priv-ppm-01, 7 March 2022,
<https://datatracker.ietf.org/doc/html/draft-gpew-priv- <https://datatracker.ietf.org/doc/html/draft-gpew-priv-
ppm-00>. ppm-01>.
[OriginTelemetry] [OriginTelemetry]
"Origin Telemetry", 2020, <https://firefox-source- "Origin Telemetry", 2020, <https://firefox-source-
docs.mozilla.org/toolkit/components/telemetry/collection/ docs.mozilla.org/toolkit/components/telemetry/collection/
origin.html>. origin.html>.
[Vad16] Vadhan, S., "The Complexity of Differential Privacy", [Vad16] Vadhan, S., "The Complexity of Differential Privacy",
2016, <https://link.springer.com/ 2016, <https://link.springer.com/
chapter/10.1007/978-3-319-57048-8_7>. chapter/10.1007/978-3-319-57048-8_7>.
Acknowledgments Acknowledgments
Thanks to Henry Corrigan-Gibbs, Armando Faz-Hernandez, Mariana Thanks to David Cook, Henry Corrigan-Gibbs, Armando Faz-Hernandez,
Raykova, and Christopher Wood for useful feedback on and Mariana Raykova, and Christopher Wood for useful feedback on and
contributions to the spec. contributions to the spec.
Test Vectors Test Vectors
Test vectors cover the generation input shares and the conversion of Test vectors cover the generation of input shares and the conversion
input shares into output shares. Vectors specify the public and of input shares into output shares. Vectors specify the public and
verification parameters, the measurement, the aggregation parameter, verification parameters, the measurement, the aggregation parameter,
the expected input shares, the prepare messages, and the expected the expected input shares, the prepare messages, and the expected
output shares. output shares.
Test vectors are encoded in JSON. Input shares and prepare messages Test vectors are encoded in JSON. Input shares and prepare messages
are represented as hexadecimal streams. To make the tests are represented as hexadecimal streams. To make the tests
deterministic, gen_rand() was replaced with a function that returns deterministic, gen_rand() was replaced with a function that returns
the requested number of 0x01 octets. the requested number of 0x01 octets.
Prio3Aes128Count Prio3Aes128Count
skipping to change at page 63, line 4 skipping to change at page 63, line 4
141498557790535505389178461361438099677, 141498557790535505389178461361438099677,
78413905472707322737069488700370687925, 78413905472707322737069488700370687925,
321206606564195806619711647355696054201 321206606564195806619711647355696054201
] ]
] ]
} }
] ]
} }
Authors' Addresses Authors' Addresses
Christopher Patton
Cloudflare, Inc.
Email: cpatton@cloudflare.com
Richard L. Barnes Richard L. Barnes
Cisco Cisco
Email: rlb@ipv.sx Email: rlb@ipv.sx
Christopher Patton
Cloudflare, Inc.
Email: chrispatton+ietf@gmail.com
Phillipp Schoppmann Phillipp Schoppmann
Google Google
Email: schoppmann@google.com Email: schoppmann@google.com
 End of changes. 34 change blocks. 
51 lines changed or deleted 55 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/