I am reading the Pinocchio paper. The paper says, in paragraph "polynomial asymptotics" of section 4.2.1, a worker, in order to include $h(s)$ into the proof, has to interpolate $p(x)$, and then divide it with $t(x)$ to get $h(x)$, then calculate $h(s)$.

As a worker, I would calculate $p(s)$, then $t(s)$, and let $h(s)=p(s)*(t(s))^{-1}$. Suppose this $h(s)$ is good, this approach is much less complicated, compared to the approach described in the paper, which dictates at least $O(n (log(n))^2)$ complexity.

I am wondering why this simpler approach to get $h(s)$ for the worker does not work. Any help is appreciated.


The worker does not know $s, t(s), v_k(s), w_k(s), y_k(s)$, the workers knows only the content of the public evaluation key and the public verification key. That's to say, the worker knows only $g^s, g^{t(s)}, g^{v_k(s)}$ etc.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.