| < 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 | |||
| 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 | |||
| 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/ | ||||