0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What exactly does A know? The input? The output? Some commitment to N? $\endgroup$
    – Maeher
    Dec 18, 2018 at 12:58
  • $\begingroup$ 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. $\endgroup$
    – zcaudate
    Dec 18, 2018 at 13:07
  • $\begingroup$ I can pretty sure B can save states and send back to A. $\endgroup$
    – kelalaka
    Dec 18, 2018 at 13:53
  • $\begingroup$ 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) $\endgroup$
    – Cort Ammon
    Dec 18, 2018 at 19:42
  • $\begingroup$ 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. $\endgroup$
    – zcaudate
    Dec 18, 2018 at 22:25

1 Answer 1

Reset to default
0
$\begingroup$

The answers to these questions depend heavily on the threat model. Starting from the most pathological, and working our way back:

  • 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think the last case might be the best solution. Thanks for breaking down all the possible availabilities. $\endgroup$
    – zcaudate
    Dec 18, 2018 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.