Smooth Univariate Sum-Check

The following is taken from the Aurora paper [BSCRSVW18].

In the section that follows, let $F$ be an integral domain, in particular any field $F$ .

Vanishing Sum of Powers

Let $H \subseteq F$ be a multiplicative coset of a cyclic subgroup, $∣ H ∣ > 1$ and let $0 < i < ∣ H ∣$ , then: $0 = x \in H \sum x^{i}$

In other words: the combined sum of the (non-zero) $i$ -th powers of the elements of $H$ is zero.

Proof.

Pick $g \in H$ , such that $g^{i} \neq = 1$ , which exists since $i < ∣ H ∣$ and $H$ is a coset of a cyclic subgroup. Since $H$ is a coset we have $g \cdot H = H$ , so: $x \in H \sum (g \cdot x)^{i} = x \in H \sum x^{i}$ Rearranging: $0 = x \in H \sum (g \cdot x)^{i} - x \in H \sum x^{i} = x \in H \sum g^{i} x^{i} - x^{i} = x \in H \sum (g^{i} - 1) \cdot x^{i} = (g^{i} - 1) \cdot (x \in H \sum x^{i})$ Since $g^{i} \neq = 1$ , we have $(g^{i} - 1) \neq = 0$ , therefore $(\sum_{x \in H} x) = 0$ since $F$ is an integral domain.

Observe that the proof above only relies on the existence of $g \in H$ such that $g^{i} \neq = 1$ . We can generalize this proof to polynomials (not just monomials), by simply observing that all monomials $X^{i}$ indidually will sum to zero, except the constant term:

Vanishing Sum of Low-Degree Polynomials

Let $H \subseteq F$ be a multiplicative coset of the integral domain $F$ and let $f (X) \in F [X]$ be a polynomial of $de g f < ∣ H ∣$ . Then: $x \in H \sum f (x) = f (0) \cdot ∣ H ∣$

Proof.

Let $c_{0}, c_{1}, \dots, c_{d - 1}$ be the coefficients of $f (X)$ .

Then: $x \in H \sum f (x) = x \in H \sum c_{0} + c_{1} \cdot x + c_{2} \cdot x^{2} + \dots + c_{d - 1} \cdot x^{d - 1} = (x \in H \sum c_{0}) + (x \in H \sum c_{1} \cdot x) + (x \in H \sum c_{2} \cdot x^{2}) + \dots + (x \in H \sum c_{d - 1} \cdot x^{d - 1}) = c_{0} \cdot (x \in H \sum 1) + c_{1} \cdot (x \in H \sum x) + c_{2} \cdot (x \in H \sum x^{2}) + \dots + c_{d - 1} \cdot (x \in H \sum x^{d - 1}) = c_{0} \cdot (x \in H \sum 1) + c_{1} \cdot 0 + c_{2} \cdot 0 + \dots + c_{d - 1} \cdot 0 = c_{0} \cdot ∣ H ∣ = f (0) \cdot ∣ H ∣$

Interactive Reduction

The theorem above gives raise to a natural protocol for proving that a polynomial evaluates to zero over a multiplicative subgroup of $F$ . Suppose the prover has $g (X) \in F [X]$ of degree greater than $∣ H ∣$ and claims that $α = \sum_{x \in H} f (x)$ . The trick behind the reduction is to ask the prover to split $g (X)$ into provided $f (X)$ and $h (X)$ , with $de g f < ∣ H ∣ - 1$ such that: $g (X) = α /∣ H ∣ + X \cdot f (X) + Z_{H} (X) \cdot h (X)$ Where $Z_{H} (X)$ is the polynomial of degree $∣ H ∣ - 1$ that vanishes on $H$ . Observe that: $x \in H \sum g (x) = x \in H \sum α /∣ H ∣ + x \cdot f (X) + Z_{H} (x) \cdot h (x) = (x \in H \sum α /∣ H ∣ + x \cdot f (x)) + (x \in H \sum Z_{H} (x) \cdot h (x)) = (x \in H \sum α /∣ H ∣ + x \cdot f (x)) + (x \in H \sum 0 \cdot h (x)) = x \in H \sum α /∣ H ∣ + x \cdot f (x)$ Because, by definition, $Z_{H} (x) = 0$ for all $x \in H$ . Now, observe that $α + X \cdot f (x)$ is a polynomial of degree $< ∣ H ∣$ and hence, by the previous theorem: $x \in H \sum α /∣ H ∣ + x \cdot f (x) = ∣ H ∣ \cdot (α /∣ H ∣) = α$ So we simply "put" the sum divided by the cardinality of $H$ "into" the constant term of $f (X)$ . The verifier checks that the polynomial is decomposed correctly by quering all the polynomials involved at a random point $c \in F$ , i.e check: $g (c) = α /∣ H ∣ + c \cdot g (c) + Z_{H} (c) \cdot h (c)$

Interactive Reduction

Input.

$R_{S u m} : = {(x = (α, H), w = g (X)) ∣ α = x \in H \sum g (X)}$

Output.

$R_{E v a l} : = {(x = (c), w = (g (X), f (X), h (X))) ∣ g (c) = α /∣ H ∣ + c \cdot g (c) + Z_{H} (c) \cdot h (c)}$

Protocol

Prover computes $f (X)$ , $h (X)$ st. $de g f < ∣ H ∣ - 1$ $g (X) = α /∣ H ∣ + X \cdot f (X) + Z_{H} (X) \cdot h (X)$
Verifier samples $c \in F$ and checks: $g (c) = α /∣ H ∣ + c \cdot g (c) + Z_{H} (c) \cdot h (c)$

Keyboard shortcuts

Smooth Univariate Sum-Check

Interactive Reduction