I would like to know if there exists algorithms A and B such that the following is possible.
Say Alice has 2 binary strings S1 and S2 both of length n and 2 keys k1 and k2. She encrypts each string with the corresponding key resulting in S1' and S2' respectively and gives these to Bob. Via algorithm A on S1' and S2' Bob produces R which he returns to Alice. Alice then uses algorithm B to determine x, which is 0 if S1≠S2 and 1 if S1=S2.
Additionally, algorithm B must have constant time complexity with respect to n (the lengths of S1 and S2). Also, at no point should Bob be able to determine the values of S1, S2 or x.
If no such algorithm exists or no such algorithm is known to exist, I would be happy to weaken the time complexity condition so that algorithm B need only be sub linear in terms of n.
Note that I have no particular encryption algorithm in mind, the process of encrypting S1 and S2 can be anything so long as Bob is unable to decrypt S1' and S2' in addition to not being able to determine x.
Just as with most encryption schemes by "unable to decrypt" I mean "unable to decrypt consistently in a reasonable amount of time".
This is a special case of the more general problem of having another individual do computations on some data without ever seeing the data or the resulting output. This is a problem I have been interested in for some time. If you know of any resources on this topic I would be interested to know about them.