Closed cjpatton closed 2 years ago
As far as how big the primes ought to be, I think we ought to aim for a soundness error of around 1/2^64 for any VDAF. Higher security levels can be targeted as desired.
For prio3, we should have:
For poplar1 we might reuse these fields, or pick new ones if the fields we pick for prio3 aren't suitable. We will also need:
The document now specifies a 64-bit and a 128-bit field suitable for prio3.
At this point we have fairly clear criteria for choosing fields for Prio. Namely, the prime modulus
p
should be of the form2^k * q + 1
, wherek
is large enough to support proof sizes we're interested in. The fact that the multiplicative group has a subgroup of order2^k
is exploited for fast polynomial interpolation.k
should also be chosen to align with the word size of the machine, e.g.,32
or64
so that fast arithmetic can be generated for it (cc/ @armfazh).The requirements are different for Poplar, though any field we choose for Prio ought to be suitable for Poplar as well. The main difference I see is that we'll need a much larger field for the leaves of the IPDF tree than we need for the inner nodes. I wonder if the leaves could use
GF(2^255 - 19)
, since there are already fast, heavily vetted implementation of this field (namely for X25519 and ed25519)? @schoppmp do you have any other thoughts here?