Does there exist a cryptographic algorithm for comparing 2 encrypted strings
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.