protocol:
Optimization in special case:
linear time, linear space prover:
Analysis:
To what I can think of:
\(d\cdot (d-1) \cdot 2^{l-1}\) small multiplication come from that \(s_1(u)\) is a \(d\) degree polynomial, that means prover needs to send \(d\) points to the verifier(shouldn’t be d+1?), for each points, there will be \(d – 1\) multiplication to compute this product:
But isn’t the following part also need multiplication?
