AES ECB deterministic encryption to perform Private set intersection

Question

There are two parties, and each has a list of plain-texts. My end goal is to assign indices to unique plain-texts across both parties. My present approach is the following.

1. Both parties perform a Diffie-Hellman key exchange to generate a secret key (which is the same for both workers).

2. Then they encrypt the plain-texts using AES in ECB mode using the secret key.

3. The set of encrypted plain-texts is brought to my local machine. (Note that I bring a set, thus each encrypted text returned by a given party is unique.)

4. I compare them and assign unique indices to each of them.

The deterministic property of ECB mode, plays an important role here, as it helps to compare similar plain-texts encrypted with the same key.

But I understand (after reading multiple answers about it) that ECB mode has many weaknesses. For example, two plain-texts longer than 16 characters, having the same characters after the 16th character will have the same ending block in the encrypted text. The same logic applies to the first 16 characters as well.

I want to know, if there are other ways in which I can extract information about the plain-texts of both parties, by analyzing the encrypted texts returned by them to me.

And is there any other more secure way to achieve my end goal?

Answer 1

Yes, there is a more secure way to achieve your goal. For uniqueness you can use SIV mode with a static nonce. SIV mode first calculates a MAC over the plaintext and then uses that as IV to the mode of operation. This means that identical plaintext will result in identical ciphertext, but that plaintext that only differ by a single bit will result unrelated ciphertext. That way the leakage when identical blocks are used in the plaintext is avoided. SIV has the advantage that integrity / authenticity of the message is protected as well.

SIV has the disadvantage that it requires an authentication tag to be included, to achieve the aforementioned integrity / authenticity. This authentication tag then doubles as IV vector for the internal cipher (hence the name: synthetic IV). If you for some reason does not have the space to store the authentication tag then you may need to look at Form Preserving Encryption of FPE.

Answer 2

There is no need to decrypt here, so an encryption scheme is not the right fit. The parties simply need to compute a deterministic function whose outputs are random to your central machine --- i.e., a pseudorandom function. You should use a PRF like HMAC or GMAC etc.

If you use a PRF, then what you have is essentially what is described in the following work (Sec 3.1):

Scaling Private Set Intersection to Billion-Element Sets

Seny Kamara, Payman Mohassel, Mariana Raykova, Saeed Sadeghian

Financial Crypto 2014

Note that it's also enough for one party to choose the key unilaterally and send it to the other party. They don't need to use Diffie-Hellman.