Proofs

The $\mathsf{\text{proof}}$ generating function receives two parameters, the vector $S_1$ and a polynomial $Q_c$. Similar as before, this will compute a point on the curve which is equal to:

$$\pi =b_0\cdot P+b_1\cdot \tau \cdot P+b_2\cdot {\tau }^2\cdot P+\cdots +b_l\cdot {\tau }^l\cdot P=Q_c(\tau )\cdot P$$

where $b_i$ are the coefficients of the polynomial $Q_c$. Now, the way this polynomial is constructed is essential for the proof:

$$Q_c(x)=\frac{f(x)-f(\gamma )}{x-\gamma }$$

Again here we are exploiting the fact that $\gamma$ is a root of $f(x)-f(\gamma )$ therefore this polynomial must be divisible by $x-\gamma$.

Exercise 9

Implement the $\mathtt{\text{proof}}$ function and test it on the $Q_c$ polynomial for the challenge $\gamma =151515$ and the polynomial $a(x)$.

def proof(S1,Qc):
    #Solve here!
    return c

#Given a challenge γ
γ = 151515
#Solve here!
b = a(γ)
Qc= (a - b)//(x-γ)
π = proof(S1,Qc)

If computed correctly, the proof obtained from $\mathtt{\text{proof}}$ when called on $Q_c$ should be:

$$\begin{array}{rl}\pi =(& 18427764633036746853571353448280965399000717707037995558464363091930831203059:\\ & 15823869948268955546174436172082876809321127559750802916163692992123652869945:\\ & 1)\end{array}$$

The value of the polynomial on the challenge point is:

$$a(\gamma )=1739069066686765$$