prio: Mantain polynomial always in the Lagrange basis.

[armfazh]

It has been observed in the rhizomes paper, Prio executes faster if the polynomials are kept in the Lagrange basis. For example, the FLP Prover sending the gadget polynomial to the verifier in such a representation.

The changes needed are minor:

• In the spec: indicate that all polynomial operations must be performed in Lagrange basis.
• In the code: implement Lagrange polynomial arithmetic and recalculate test vectors.

A verbose example of the changes needed in librpio-rs is here: armfazh/rhizomes#2

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

[tgeoghegan]

In the spec: indicate that all polynomial operations must be performed in Lagrange basis.

Does the spec actually have to say this as a must? If an implementation doesn't perform operations in the Lagrange basis, it'll be slower, but it'll still interoperate successfully with an implementation that does use the Lagrange basis, right?

[armfazh]

Regarding interoperability, the spec currently enforces that messages be encoded in the monomial basis. This is an implicit restriction on message encoding that ultimately gets reflected in unnecesary conversions.

A possible change is to let implementations to encode polynomials in any compatible basis.
However, how this can be managed with test vectors?

[tgeoghegan]

I understand now how this is a breaking change. Thanks.

[cjpatton]

@armfazh are there any new security considerations we need to be aware of if we took this change?

[armfazh]

are there any new security considerations we need to be aware of if we took this change?

I think the previous considerations still apply, but not new ones.
Most of the changes are about the way polynomial arithmetic is computed. Nothing changed in the design of the protocol, just the representation of polynomials.
In fact, the protocol constructs the polynomials in the values (Lagrange) representation, and the spirit of the proposal is to stick to such a representation while improving performance.

[cjpatton]

Let's prepare to discuss this change at IETF 124. Since the paper is so new and we're so close to done, we might decide that we don't want to block RGLC on this. Still, the potential performance benefits are too enticing to ignore.

@armfazh would you mind preparing a PR for this, just to give us a sense of how complex this change will be? No need to propagate it through the draft in the initial PR. My suggestion would be to just update the PoC.

Alternatively, @divergentdave if you wanted to take a crack at this, in order to learn how the new math works, I say go for it.

[armfazh]

The PR for libprio-rs (armfazh/rhizomes#2) is meant to give ideas about the changes needed.

It would be useful if someone (other than me) replicated the results in the Python implementation. Please comment if you prefer I work on the changes for the Python code. I'm ok with either option.

[cjpatton]

I would say if anyone is enthusiastic about seeing this through, then go ahead and write a PR.

[armfazh]

Happy to work on this, assign the issue to me.

[cjpatton]

Done, but let's wait for @divergentdave to finish reading the paper. We're still trying to decide if we think it's worth blocking RGLC on this.

[divergentdave]

I was initially worried about whether this would impact the zero knowledge security of the FLP, since the random wire seed values blind various values later in the protocol, and the Lagrange-to-monomial conversion mixes the wire seed into all polynomial coordinates, but I've read through the paper and reviewed BBCGGI '19, and I'm satisfied this wouldn't affect the security analysis. The prover's message is $\pi=(w, f_1(\omega_0), ..., f_L(\omega_0), c_p)$ and this would change the coordinates of the proof polynomial or gadget polynomial, $c_p$, from one basis to another. The HVZK simulator only needs to simulate the verifier's randomness and the response to the verifier's linear query, which evaluates $f'_i(r)$, $p'(r)$, and $p'(\omega_{M-1})$. The linear query that the verifier makes would naturally change due to the change in polynomial basis, but the values produced by the query would be the same. Since the polynomial coordinates $c_p$ are not in the verifier's view at all, the joint distributions are unchanged. Since we exclude cases where r is a root of unity, $f'_i(r)$ will still be uniformly distributed due to the influence of $f_i(0)$, chosen by the honest prover.

I think this change is worth considering, the speedups look promising.