How to learn enough crypto to understand this paper?
I'll give you an EL18 description of a basic private set intersection:
I have a database of image fingerprints which I want you to test your images against and tell me if there are matches. I can assume that you're going to faithfully run my protocol because I use DRM to control the software that runs on your computing device. The obvious way to accomplish the matching would be for me to just send you the database of fingerprints-- they are hashes after all and don't tell you anything about the images other than letting you match them-- and for you to tell me about the matches.
But I don't want to tell you the database or tell you when an image matches because if I do you'll realize that I'm targeting images connected with a particular ethnicity, which I intend to mass murder. So, instead I tell you I want to search for child porn and I get you to agree to the following protocol, and you're foolish enough let me keep the hashes secret for no obvious reason.
The first building block we need is an encryption scheme which is additively homomorphic, such as elgamal encryption. With this special encryption scheme the following properties hold: Enc(Data1, key) + Enc(Data2, key) = Enc(Data1+Data2,key) and x*Enc(Data1,key) = Enc(Data1*x,key). Or, in English, the sum of two ciphertexts gives you a ciphertext of the sum of the plaintexts, and a ciphertext multiplied by a value gives you a ciphertext for the plaintext multiplied by that value.
With that in hand we can build a private set intersection.
(1) I pick a private key, send you the public key, and I encrypt each of the hashes in my database. I send you the encryptions-- which, thanks to the encryption, teaches you nothing about the database except an upper bound on its size.
(2) For each database entry you take the hash of image you want to test, encrypt it with the same key and subtract it from the encrypted database entry. If they matched you have an encryption of zero (which you can't tell is zero, due to encryption), if they didn't match you have an encryption of some non-zero value-- the difference between the image hash and the database entry. You then pick a new random number and multiply the result with it. You now either have an encryption of a totally random number (if there was no match) or an encryption of zero (since random*0=0).
(3) You send that to me, I decrypt it... and if it decrypts to zero I add you to the list of people to be executed at some time in the future. If it doesn't decrypt to zero I learn absolutely nothing about your hash, other than it didn't match, because the result is literally a random number.
The Apple scheme makes a number of elaborations on this basic idea to improve efficiency (the database is a cuckoo hash table, so instead of sending you one encryption per database entry per image of mine I only need to send you a few encryption per image-- however much fanout the hash table has), to make it so that matches result in leaking a decryption key so they can decrypt the image, and additional complexity to make it so that the matching isn't fully triggered unless you have more than some threshold number of matching images and to partially obscure the exact number of sub-threshold matches.