psionic

With the power of ✨cryptography✨.

But for real, this is a technique very related to ElGamal encryption and Diffie-Hellman key exchange. It is based on cyclic groups, which are really interesting and totally out of scope for this explanation. Just know that you can sorta kinda treat the group elements like numbers, but only for multiplication. This means that we can multiply elements together (or multiply an element by itself, giving us a bit of exponentiation too).

We start out with a generator, which is a special kind of group element. Let's call it g. We then pick a secret, random number, which we will call x. Then, g^x is a random element in the group that only you know. We will be using it as an encryption key.

Now, you have some items in your private set. Let's hash each item into a string of 256 bytes, and then pretend that those bytes represent a number. That number, let's call it v, can be encrypted simply by computing g^xv.

Now, that we have encrypted all of the values, we can send them to your friend. Since they are also following this guide, they also have a secret number. Let's call it y. Now, they will encrypt the thing you sent with their secret number, giving us the value g^xyv for each item v.

Now, we also have to run the protocol in reverse, where they are the ones encrypting, and you encrypt their things with your secret. This means that at the end, you will both have your stuff that looks like g^xyv, and their stuff which looks like g^xyw. (Notice the w instead of your v.) Then we can clearly see that if v = w, the values are going to be the same, and then you both will know that v is present in both of your sets. Ta-da!

For the really nerdy: the cyclic group in question is secp256r1, so it would technically be more correct to use additive notation, but honestly—I prefer the multiplicative notation. Sue me.