Consider the following setting.

Alice receives a chunk of data from Victor, together with a cryptographic certificate of authenticity of some sort (eg hash signed with Victor’s private key).

Bob now wants to know the result of some computer program applied to the data. Alice is not willing to disclose the raw data to Bob, but is happy to perform the computation herself and send him the result. The program was not known at the time Victor certified the data.

Is there a scheme that will allow Bob to verify that the computation was in fact performed as agreed, on the data certified by Victor?

  • 1
    $\begingroup$ I am not sure exactly what would be the best solution for this case. But a lot of work has been done on Verifiable Computation, so there is probably some appropriate scheme. Maybe check out the videos here to learn more on the subject cyber.biu.ac.il/event/the-6th-biu-winter-school $\endgroup$ – Guut Boy Nov 13 '17 at 8:59

One of the many verifiable computation schemes would be the way to go.

Something like zkSNARKs would allow a prover, Alice in this case, to prove that she performed a computation correctly without revealing the inputs to her function. These schemes require Alice to initially send a commitment of her input to the verifier. In your setup, the chunk of data Victor signs may be a commitment to the original data he sent.

To learn more about zkSNARKs, I recommend the already linked Winter School, as well as the following primer provided by Zcash: https://z.cash/blog/snark-explain.html.

Edit Just encountered this work that is relevant: ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (https://eprint.iacr.org/2014/617)


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.