8
$\begingroup$

I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this problem belongs to exactly.

In a nutshell: person A has a list of data, another person (B) has an algorithm that gives each item on this list a score and then sums all these scores to provide an overall score for the whole list. How can we run the algorithm on the data list so that the data is kept extremely secure (preferably never leaving person A) but so that person B can be certain the algorithm ran properly and was not tampered with.

Here is an example: Anna and Bob live in a large village. Anna has a list on her computer of all the things she has done in the village, both good and bad. Bob has made a very simple scoring algorithm for such lists, which runs on each item on the list and gives it a score and then adds all these numbers up to give Anna a final score. This score lets Bob know how beneficial Anna is to the village community and is specific to Bobs opinion. (This is more than an example as this is actually the system I want to make)

However Anna does not want to give Bob her list, as then he has access to potentially embarrasing info in there (everyone has skeletons in thier closet). Bob however does not trust Anna to run his algorithms herself, as she may just lie and tell Bob the score was very high so that Bob is more likely to help her.

There are a few solutions I have already thought of, but all have problems:

A. Find a random person to take the data and run the algorithm and send the score back, but it may be difficult to ensure that this random person do not know Anna and try to help her or make a copy of the data and later try to trace it back and blackmail Anna.

B. Let Anna run the algorithm but somehow encode a check code into the scores, for example, instead of rating an event as 1 rate it as 1.0000000000797, in such a way that Bob can later use this as a checkcode to see if the given score is correct. However this check could also be misused by Bob to indicate what specific things Anna has done. Also I can imagine such a system would be trivial to reverse engineer so that Anna can give a false score with a correct checkcode, considering that Anna must have full access to Bob´s algorithm to run it.

C. The village creates a secure server to take such data and algorithms and run them together. However Anna and Bob both don´t really trust anyone enough to do this and not make a copy of the data or modify the scores, unless there is some fundamentally secure architecture for doing so. Also I would prefer this to be a P2P system.

$\endgroup$
  • $\begingroup$ What if Bob's scoring algorithm is, for instance, the binary representation of if Anna has done or hasn't done each of the things on the list? (So 1*<did Anna do thing 1> + 2*<did Anna do thing 2> + 4*<did Anna do thing 3>...) Then Bob will have access to Anna's data just based on the output of the scoring algorithm. $\endgroup$ – TLW Oct 15 '15 at 23:43
  • 1
    $\begingroup$ I wonder if homomorphic encryption has any play here? It solves the reverse problem kind of though - it lets some other system do computation on data without learning the values that it's working with. $\endgroup$ – Alan Wolfe Oct 16 '15 at 14:37
  • $\begingroup$ @TLW I am not fully sure if I understand what you are saying... who is running the algorithm in this situation and still how can we be sure the final value is not intercepted and tampered with? $\endgroup$ – Robin A Oct 19 '15 at 21:38
9
$\begingroup$

In the crypto community, this task is known as delegated computation, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you some proof that it actually performed the computation (and didn't just output a random output, and ran away with your money).

A pointer, off the top of my head, is "Delegating computation: interactive proofs for muggles" (Goldwasser, Kalai, and Rothblum, J. ACM (62), 2015). Other solutions probably exist, look inside.

$\endgroup$
1
$\begingroup$

There is a new field of homomorphic encryption that generally fits your requirements:

Homomorphic encryption is a form of encryption that allows computations to be carried out on ciphertext, thus generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext.

The processing entity cannot know "anything" about the cyphertext, it only appears as random data, it can only corrupt the computation, and the client needs some way to detect/ defend against corrupted data/ calculations. this can be done with message digests and fault tolerant computing.

Homomorphic encryption was only demonstrated as theoretically possible somewhat recently hence is more in conceptual stages and does not appear to be implemented much in practice so far, but eventually the idea is that it might show up as a capability (eg similar to other standard services like virtualization) on large standardized compute clusters eg Amazon ECC or google compute engine.

$\endgroup$
  • $\begingroup$ This doesn't answer the question that was asked. Homomorphic encryption does not (by itself) allow B to verify that the algorithm ran properly and the data was not tampered with. Homomorphic encryption ensures only confidentiality, not integrity, but the question is about integrity. $\endgroup$ – D.W. Oct 18 '15 at 0:18
  • $\begingroup$ the question is about "running an algorithm on data remotely" which is the raison d'etre of homomorphic encryption, and the answer addresses that directly along with the extra concerns of tampering which message digests & fault tolerant computing techniques address. $\endgroup$ – vzn Oct 18 '15 at 0:27

Your Answer

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.

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