Given the popular Private Set Intersection (PSI) protocol first described in [1]:
- Alice choose a random $a$, and sends $\{H(x_i)^{a}\bmod p\}| (i=1,...m)$ to Bob.
- Bob choose a random $b$, and sends $\{H(y_i)^{b}\bmod p\}| (i=1,...n)$ to Alice.
- Alice computes and sends $\{H(y_i)^{ba}\bmod p\}| (i=1,...n)$ to Bob.
- Bob computes and sends $\{H(x_i)^{ab}\bmod p\}| (i=1,...m)$ to Alice.
- Each party locally compute the intersections.
Question 1: If (with a very small chance) there exist $x_1$ and $x_2$ that $H(x_1)=H(x_2)^2\bmod p$, then Bob could discover it because $H(x_1)^a=(H(x_2)^a)^2\bmod p$. Surely Bob could not simulate this information. Does it mean that this protocol violate semihonest security?
I discussed this with friends, some said this does not violate semihonest security, because the chance of $H(x_1)=H(x_2)^2\bmod p$ is negligable. But I think it does, because in Definition 4.1. of the simulation proof tutorial [2], the simulation should always succeed, and should not depend on the input $\{x,y\}$.
Question 2: In the PSI protocol (Fig.3) of [3], they use $H(H(x_i)+H(x_i)^{a})$ instead of $H(x_i)^{a}$ (notice that the protocol is still correct if they use $H(x_i)^{a}$), this seems to strengthen my point (naive DH-PSI protocol is not provable), because $H(H(x_i)+H(x_i)^{a})$ is easier to simulate than $H(x_i)^{a}$ . Is my understanding correct?
Thanks.
- Huberman B A, Franklin M, Hogg T. Enhancing privacy and trust in electronic communities[C]// ACM Conference on Electronic Commerce. ACM, 1999:78-86
- Lindell Y, How to simulate it, https://eprint.iacr.org/2016/046.pdf
- Heinrich A, Hollick M, Schneider T, et al. PrivateDrop: Practical Privacy-Preserving Authentication for Apple AirDrop, USENIX'SEC 21