Assuming an algorithm $A$ known to both Alice and Bob.

Alice runs the algorithm and gets a result $R$. How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random value (without having Bob run the algorithm himself)?

Please note that Alice does not have to prove correctness of $R$, just that she ran $A$ to obtain $R$.

The algorithm and its inputs can be modified to build the proof if necessary

New contributor
BGR is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • The answer might depend on the program $P$. – Yuval Filmus 2 hours ago
  • Are you familiar with interactive proofs? – Yuval Filmus 2 hours ago
  • @YuvalFilmus Hello. Are you referring to Sigma protocols used in zero knowledge proofs for instance? – BGR 2 hours ago
  • I have never heard of Sigma protocols. Zero-knowledge proofs are just one type of interactive proofs. – Yuval Filmus 2 hours ago
  • Either program $P$ or algorithm $A$ is an unnecessary variable. It is cleaner to just say "there is an algorithm $A$ that is known to both Alice and Bob". It looks like we should prefer an algorithm since it is more well defined than a program. Could you remove program P from the question? – Apass.Jack 1 hour ago

Your Answer

BGR is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.