Does there exist a cryptographic algorithm for comparing 2 encrypted strings

Question

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.

Thanks

Answer 1

The simplest solution appears to be to:

• eliminate the requirement to use two different keys
  • it will probably be impossible otherwise
• use a randomized homomorphic encryption algorithm that can compute XOR
  • XOR computes differences, while you technically want equality; You could invert the output with a NOT gate to obtain the result of CMP (comparison), or you could simply check for a null string which would indicate equality.

With this solution, Alice would encrypt both messages under one key using a randomized homomorphic encryption algorithm.

Bob would compute XOR on the two ciphertexts and return the result to Alice.

Alice would then decrypt the ciphertext to obtain the result of the XOR of the two plaintexts, which indicates whether or not the two were different. This can be changed to indicate whether the two plaintexts were equivalent by inverting the result with a NOT gate, or simply checking for a null string.

• If XOR was computed on the ciphertexts and $s_1$ and $s_2$ are equivalent, then the output will be a null string of 0s.

I mention CMP because it technically computes what you want (equality), while XOR computes the inverse of what you want (difference). They are effectively both the same, and you will likely want to find a cipher that offers XOR as one that offers CMP will probably not be directly available.

Ciphers for computing XOR

You could use the Paillier cryptosystem; It technically computes the addition of ciphertexts, but the least significant bit of addition happens to be equivalent to XOR. You would need to encode your message one-bit per ciphertext, which would probably take up a decent amount of space.

There is also the cipher from Fully Homomorphic Encryption Over The Integers; It also stores 1 bit per plaintext, but it relies on the hardness of the AGCD problem, which may not be as secure as we would like.