Using faster polynomial evaluation from rhizomes paper (ia.cr/2025/1727)

[armfazh]

Use of faster polynomial evaluation in the Lagrange basis from the rhizomes paper.

• It is applied to FLP.Query algorithm to evaluate several polynomials at a random value.
• In the paper, Algorithm 6 evaluates a single polynomial, while Alg. 7 is its batched version that is implemented.

A verbose example of the changes needed for libprio-rs is here: armfazh/rhizomes#1
The actual PR is here: divviup/libprio-rs#1340

Reference:
LINK Rhizomes and the Roots of Efficiency, Latincrypt 2025.

No breaking changes

[cjpatton]

Thanks @armfazh, this is awesome :)

I think we could resolve this one by adding an implementation note to Section 7.3, as well as an informative reference to your paper.

My vote would be to take this change in the next draft, regardless of what we do with #574. What do you think, @divergentdave?

[cjpatton]

Speaking of: when you benchmarked this, did you notice whether there was an improvement across the board, for all Prio3 variants? Or does it only make a difference for larger circuits?

[armfazh]

Speaking of: when you benchmarked this, did you notice whether there was an improvement across the board, for all Prio3 variants? Or does it only make a difference for larger circuits?

In the benchmark plot, there are improvements even for variants where N is as small as 10.

This also applies even for the Count VDAF that uses small degree polynomials.

[cjpatton]

@armfazh please send a PR when convenient!