Blind Evaluation of Polynomials

We denote by F p the field of size p ; that is, the elements of F p are { 0 , … , p − 1 } and addition and multiplication are done mod p as explained before.

Polynomials and linear combinations

Recall that a polynomial P of degree d over F p is an expression of the form P(X)=a0+a1⋅X+a2⋅X2+…+ad⋅Xd , for some a 0 , … , ad ∈ Fp .

We can evaluate P at a point s ∈ F p by substituting s for X , and computing the resultant sum P(s)=a0+a1⋅s+a2⋅s2+…+ad⋅sd

For someone that knows P , the value P ( s ) is a linear combination of the values 1 , s , … , s d – where linear combination just means “weighted sum”, in the case of P ( s ) the “weights” are a 0 , … , a d .

Given a , b , E ( x ) , E ( y ) , we can compute E ( a x + b y ) . This is simply because E(ax+by)=gax+by=gax⋅gby=(gx)a⋅(gy)b=E(x)a⋅E(y)b.