2024-06-28

Polynomial Modulo Soundness

We want to proof a polynomial modular multiplication (PMM)

$A_i(X) ⋅ B_i(X) = R_i(X) \mod P(X)$

Where $A,B,R$ are low degree.

We can do this using an auxiliary low-degree polynomial $Q_i(X)$ and evaluating the following in a random point $z$

$A_i(z) \cdot B_i(z) = Q_i(z) \cdot P(z) + R_i(z)$

To verify many such PMMs we can take a linear combination in a random $α$

$\sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ \sum_i α^i ⋅ Q_i(z) + \sum_i α^i ⋅ R_i(z)$

Question Can the prover pre-sum the quotients? I.e. have an auxiliary low-degree polynomial $Q(X)$ and check:

$\sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ Q(z) + \sum_i α^i ⋅ R_i(z)$

Given $A_i, B_i, R_i, Q$ and $P$ low-degree polynomials that satisfy the above equation. We want to show the only solution is

$Q(X) = \sum_i α^i ⋅ Q_i(X)$

where

$Q_i(X) = \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)}$

We know that

$Q(X) = \frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)}$

So this amounts to proving

$\frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)} = \sum_i α^i ⋅ \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)}$

Let's assume that between $A_i(X) \cdot B_i(X) - R_i(X)$ there are enough degrees of freedom that these can be arbitrary polynomials $D_i(X)$ of degree $2\cdotd$ :

$\frac{\sum_i α^i ⋅ D_i(X)}{P(X)} = \sum_i α^i ⋅ \frac{D_i(X)}{P(X)}$