Module prio::vdaf::prio3

Implementation of the Prio3 VDAF [draft-irtf-cfrg-vdaf-08].

WARNING: This code has not undergone significant security analysis. Use at your own risk.

Prio3 is based on the Prio system desigend by Dan Boneh and Henry Corrigan-Gibbs and presented at NSDI 2017 [CGB17]. However, it incorporates a few techniques from Boneh et al., CRYPTO 2019 [BBCG+19], that lead to substantial improvements in terms of run time and communication cost. The security of the construction was analyzed in [DPRS23].

Prio3 is a transformation of a Fully Linear Proof (FLP) system [draft-irtf-cfrg-vdaf-08] into a VDAF. The base type, Prio3, supports a wide variety of aggregation functions, some of which are instantiated here:

• Prio3Count for aggregating a counter (*)
• Prio3Sum for copmputing the sum of integers (*)
• Prio3SumVec for aggregating a vector of integers
• Prio3Histogram for estimating a distribution via a histogram (*)

Additional types can be constructed from Prio3 as needed.

(*) denotes that the type is specified in [draft-irtf-cfrg-vdaf-08].

Structs

• Prio3
  The base type for Prio3.
• Prio3InputShare
  Message sent by the Client to each Aggregator during the Sharding phase.
• Prio3PrepareMessage
  Result of combining a round of Prio3PrepareShare messages.
• Prio3PrepareShare
  Message broadcast by each Aggregator in each round of the Preparation phase.
• Prio3PrepareState
  State of each Aggregator during the Preparation phase.
• Prio3PublicShare
  Message broadcast by the Client to every Aggregator during the Sharding phase.

Functions

• optimal_chunk_length
  Finds the optimal choice of chunk length for Prio3Histogram or Prio3SumVec, given its encoded measurement length. For Prio3Histogram, the measurement length is equal to the length parameter. For Prio3SumVec, the measurement length is equal to the product of the length and bits parameters.

Type Aliases

• Prio3Average
  The average type. Each measurement is an integer in [0,2^bits) for some 0 < bits < 64 and the aggregate is the arithmetic average.
• Prio3Count
  The count type. Each measurement is an integer in [0,2) and the aggregate result is the sum.
• Prio3FixedPointBoundedL2VecSumexperimental
  The fixed point vector sum type. Each measurement is a vector of fixed point numbers and the aggregate is the sum represented as 64-bit floats. The preparation phase ensures the L2 norm of the input vector is < 1.
• Prio3FixedPointBoundedL2VecSumMultithreadedexperimental and multithreaded
  The fixed point vector sum type. Each measurement is a vector of fixed point numbers and the aggregate is the sum represented as 64-bit floats. The verification function ensures the L2 norm of the input vector is < 1.
• Prio3Histogram
  The histogram type. Each measurement is an integer in [0, length) and the result is a histogram counting the number of occurrences of each measurement.
• Prio3HistogramMultithreadedmultithreaded
  Like Prio3Histogram except this type uses multithreading to improve sharding and preparation time. Note that this improvement is only noticeable for very large input lengths.
• Prio3Sum
  The sum type. Each measurement is an integer in [0,2^bits) for some 0 < bits < 64 and the aggregate is the sum.
• Prio3SumVec
  The count-vector type. Each measurement is a vector of integers in [0,2^bits) and the aggregate is the element-wise sum.
• Prio3SumVecMultithreadedmultithreaded
  Like Prio3SumVec except this type uses multithreading to improve sharding and preparation time. Note that the improvement is only noticeable for very large input lengths.