0
$\begingroup$

Context

Suppose Alice asks Bob to write a (python) code/function named get_sqrt(input) that computes and returns the square root of an input number named input. Next, Alice provides three random numbers as input to Bob. Bob produces the three output numbers using Bob's function get_sqrt(input) and returns to Alice:

  • Three output numbers that are the square roots of the three input numbers.
  • The python code get_sqrt(input).
  • Some kind of signature/hash code. This signature/hash code can consist of any combination of information derived from the input, output and python code get_sqrt(input).

Assumptions

  1. Alice only has access to Alice's world until Alice has verified the solution of Bob. Afterwards Alice gets access to both Alice's and Bob's world.
  2. Bob has access to both Bob's world and Alice's world (low- and high costs per operations).
  3. Bob can do computations cheaply in Bob's world, but Bob is not trusted in Bob's world.
  4. Re-doing the computation is too expensive in the world of Alice (for both Bob and Alice), because in the world of Alice, the costs per computation are too high.
  5. The solutions created by the function get_sqrt(input) are reversible or easily(polynomially) verifiable. (For example, the output of Bob's function get_sqrt(input) can be verified by Alice by checking whether the square of each output equals its accompanying input.)

Challenge

However, just that the answers provided by Bob are correct, does not mean that the get_sqrt(input) function that Bob sent to Alice actually generated those answers/isn't gibberish. Therefore, I was wondering if there is some property that can be computed by Bob (and/or Alice), based on the input, output, and (python) code get_sqrt(input) that makes it possible for Alice to verify that Bob's function indeed generates those output numbers based on the given input numbers (without re-doing the computations).

Question

Is there a way with which Alice can verify that the output numbers are generated by the get_sqrt(input) function based on the set of input numbers, without re-doing the computation?

$\endgroup$
4
  • 1
    $\begingroup$ Is it sufficient for you to validate that Bob is able to perform such computations or do you need to validate that a specific piece of code was executed? $\endgroup$ – SEJPM Feb 4 at 14:51
  • $\begingroup$ There is no need to validate that a specific piece of code was executed. It is not sufficient to validate that Bob is able to perform such computations. It is sufficient to validate that Alice is able to reproduce the computations (later-on (in a different environment where the costs per operation are lower). $\endgroup$ – a.t. Feb 4 at 14:58
  • 1
    $\begingroup$ Do you trust Bob, it seems no. Then why doesn't Alice verifies in the first place? I think this is not your actual question. $\endgroup$ – kelalaka Feb 4 at 20:12
  • $\begingroup$ Bob is not trusted, but able to do all computations in a cheap environment. Alice can't verify the code by re-computing it because the cost per operation are too high in the world of Alice. Bob has access to both the cheap- and expensive cost per operation worlds. But the costs per operations of verifying in Alice's world (by means of re-computation) are also too high for Bob. $\endgroup$ – a.t. Feb 4 at 20:20

Your Answer

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

Browse other questions tagged or ask your own question.