As intuition for why the VC scheme is sound, note that it seems hard for an adversary who does not know α to construct any pair of group elements h,hα except in the obvious way: by taking pairs (g1,g α 1 ),(g2,g α 2 ),... that he is given, and applying the same linear combination (in the exponent) to the left and right elements of the pairs.

     This hardness is formalized in the d-PKE assumption, a sort of “knowledge-of-exponent” assumption that says that the adversary must “know” such a linear combination, in the sense that this linear combination can be extracted from him.      Roughly, this means that, in the security proof, we can extract polynomials Vmid(x), W(x), Y(x) such that Vmid (from the proof) equalsVmid(s), W =W(s) and Y =Y(s), and that moreover these polynomials are in the linear spans of the vk(x)’s, wk(x)’s, and yk(x)’s respectively.

     If the adversary manages to provide a proof of a false statement that verifies, then these polynomials must not actually correspond to a QAP solution. So, either p(x) is not actually divisible by t(x) (in this case we break 2q-SDH) or V(x) = vio(x)+Vmid(x), W(x) and Y(x) do not use the same linear combination (in this case we break q-PDH because in the proof we choose β in a clever way).

     We can apply GGPR’s rerandomization technique [30] (§2.3) to provide zero-knowledge for our new verifiable computation construction.

     The worker chooses δv,δw,δy R ← F and in his proof, instead of the polynomials vmid(x), v(x), w(x) and y(x), he uses the following randomized versions vmid(x) + δvt(x), v(x) + δvt(x), w(x) + δwt(x) and y(x) +δyt(x).

     In order to facilitate the randomization of the proof we add the following terms to the evaluation key: g αvt(s) v , g αwt(s) w , g αyt(s) y , g βt(s) v , g βt(s) w , g βt(s) y .

     Our main improvement is that our VC scheme only requires a regular QAP, rather than a strong QAP, which improves performance by more than a factor of 3.

     Moreover, the scheme itself is simpler, leading to fewer group elements in the keys and proof, fewer bilinear maps for Verify, etc.

     The scheme above assumes a symmetric bilinear map. In practice, for performance reasons, we use an asymmetric bilinear map e : G1 × G2 → GT where G1 is an elliptic curve group called the “base” curve, and G2 is the “twist” curve.

     Operations over the base curve are about 3 times faster than over the twist curve (§5.1). Due to our optimizations, while the worker must compute the g w(s) w term over the twist curve, all of the other proof terms can be over the base curve.

     As intuition for why the VC scheme is sound, note that it seems hard for an adversary who does not know α to construct any pair of group elements h,hα except in the obvious way: by taking pairs (g1,g α 1 ),(g2,g α 2 ),... that he is given, and applying the same linear combination (in the exponent) to the left and right elements of the pairs.

     This hardness is formalized in the d-PKE assumption, a sort of “knowledge-of-exponent” assumption that says that the adversary must “know” such a linear combination, in the sense that this linear combination can be extracted from him.      Roughly, this means that, in the security proof, we can extract polynomials Vmid(x), W(x), Y(x) such that Vmid (from the proof) equalsVmid(s), W =W(s) and Y =Y(s), and that moreover these polynomials are in the linear spans of the vk(x)’s, wk(x)’s, and yk(x)’s respectively.

     If the adversary manages to provide a proof of a false statement that verifies, then these polynomials must not actually correspond to a QAP solution. So, either p(x) is not actually divisible by t(x) (in this case we break 2q-SDH) or V(x) = vio(x)+Vmid(x), W(x) and Y(x) do not use the same linear combination (in this case we break q-PDH because in the proof we choose β in a clever way).

     We can apply GGPR’s rerandomization technique [30] (§2.3) to provide zero-knowledge for our new verifiable computation construction.

     The worker chooses δv,δw,δy R ← F and in his proof, instead of the polynomials vmid(x), v(x), w(x) and y(x), he uses the following randomized versions vmid(x) + δvt(x), v(x) + δvt(x), w(x) + δwt(x) and y(x) +δyt(x).

     In order to facilitate the randomization of the proof we add the following terms to the evaluation key: g αvt(s) v , g αwt(s) w , g αyt(s) y , g βt(s) v , g βt(s) w , g βt(s) y .

     Our main improvement is that our VC scheme only requires a regular QAP, rather than a strong QAP, which improves performance by more than a factor of 3.

     Moreover, the scheme itself is simpler, leading to fewer group elements in the keys and proof, fewer bilinear maps for Verify, etc.

     The scheme above assumes a symmetric bilinear map. In practice, for performance reasons, we use an asymmetric bilinear map e : G1 × G2 → GT where G1 is an elliptic curve group called the “base” curve, and G2 is the “twist” curve.

     Operations over the base curve are about 3 times faster than over the twist curve (§5.1). Due to our optimizations, while the worker must compute the g w(s) w term over the twist curve, all of the other proof terms can be over the base curve.