# How to prove that work is done without actually knowing the payload

Is there a way for an algorithm to run securely on one end, whilst the other end is able to be notified and also verify that it has run and done the work without knowing what the actual payload is?

For example, $$A$$ provides an algorithm that adds $$1$$ to any number.

$$B$$ takes this algorithm and performs it $$N$$ number of times. $$A$$ can then verify that $$B$$ has performed it $$N$$-times without knowing what $$N$$ is.

• What exactly does A know? The input? The output? Some commitment to N? – Maeher Dec 18 '18 at 12:58
• I'm looking to understand if it's possible to record the usages of a proprietary algorithm supplied by A on a remote system B that A has no control over. B wants to use A's algorithm without passing A it's data. A wants to monitor just B's usage of the algorithm so that A can charge B for it. – zcaudate Dec 18 '18 at 13:07
• I can pretty sure B can save states and send back to A. – kelalaka Dec 18 '18 at 13:53
• Are you just looking to charge a reasonably-honest B for use of A? Or are you targeting the ultra-malicious B that will reverse engineer A while it is running on his system? And are we to assume B wishes to maximize the uses of the algorithm (i.e. we don' thave to worry about B convincing A that the algorithm was run 5 times when, in reality, it only ran twice) – Cort Ammon Dec 18 '18 at 19:42
• I’m trying to work out what is the most reasonable way of delivering a charge on usage model for sensitive data. I’m weighing some trade offs. – zcaudate Dec 18 '18 at 22:25

• If the software has to be run on the remote machine, and $$A$$ cannot know anything about the data, and $$B$$ is willing to take full advantage of physical access to the remote machine, there's really nothing you can do. Physical access is really hard to beat.
• If $$A$$ can know a little of what $$B$$ needs, $$A$$ might be able to provide the algorithm encrypted in pieces, such that $$B$$ only gets enough of the algorithm to solve that one problem, but has to go back to $$A$$ to solve the next. However, this requires knowing a little about $$B$$'s data and is very algorithm specific.
• If the algorithm doesn't have to be run remotely, there's the relatively new field of homomorphic encryption. This would let $$A$$ run the algorithm locally on an encrypted copy of $$B$$'s data without konwing anything about it. However, this field is in its infancy, and practical examples are hard to find.
• If we can reasonably trust $$B$$ to not reverse engineer the code, new options form. At some point this trust becomes a legal question, which can get complicated.
In the last case, there is actually a solvable answer. $$B$$ runs the program, which takes the inputs and outputs an encrypted form of the outputs (typically with asymmetric encryption). This key is derived from the hash of all of the inputs. This hash is then provided to $$A$$, who looks at that hash, and provides the correct decryption key.
It can also be done in the reverse order: $$B$$ hashes the inputs, $$A$$ looks at the hash, and signs them. $$B$$ takes that signature and the inputs, and passes it into the algorithm, which confirms that the inputs are signed.