Search for a String in a list of Encrypted Values

Imagine a scenario where one party wants to check whether a name they have exists in a list of names kept by the another party. But I do not want the other party to know what name I am searching. This problem may seem unrealistic but imagine a data breach where tons of personal information is leaked. You want to check whether you were impacted in the breach but do not trust the party hosting the personal information to keep your query safe. This is possible with the help of homomorphic encryption, specifically Paillier encrytption.

Python provides library that will allow you to use the Paillier system, an additive homomorphic cryptosystem, to perform arithmetic on encrypted integers. It is called phe. So if we want to search a list of names to see whether it includes “nathan” we need to convert our python strings to binary. Once those values are converted to binary, we need to encrypt the values using a public or private key. For the purposes of this example, let’s assume I am reaching out to a service that has encrypted information and I want to check my value against their encrypted values. Once our value is encrypted with the service’s public key, we can check whether the difference between our encrypted value and the values provided by the service is equal to zero. If it is, we got a hit!

Start a python console which has access to the standard library and phe. pip install phe should work if you have not installed the library already. Follow along in your console session.

Generate the public/private keypair

Create binary versions of our strings and put them in a list. For more information on working with ascii to binary see the documentation for binascii.

Encrypt the values:

Now we can perform operations on encrypted values. Notice how with our list, values 0 and 1 are equal but 1 and 2 are not.

The next thing to demonstrate is search the encrypted values for a hidden value. This would likely not be decrypted client side, instead, the encrypted values would be sent back to the service and decrypted. The service would receive a bunch of encrypted numbers that did not mean anything to them. They would decrypt and return the results which could be decoded. In this example we subtract our search value from the encrypted one for simplicity’s sake. We are looking for 0 which indicates a hit.

This exercise is pretty straight forward, a toy example. The real world uses for this are still developing and research around homomorphic encryption is actively growing. Please let me know if you have any other examples of asymmetric cryptosystems in the real world, I would love to hear about them!