# 1 the problem

Let's invite our old friends, Alice and Bob. Suppose that they hold a set of elements respectively, and they would like to determine the intersection while keeping the other elements in private from each other. This is the so-called private set intersection(PSI) problem.

# 2 blind signature-based PSI scheme

A lot of protocols have been proposed to solve the PSI problem, hash-based, GC-based, polynomial interpolation-based, etc. This post explains the solution[1] based on blind signature discussed in a previous post.

Firstly, Bob generates his RSA key pair $$PK=\{e,n\}, SK=\{d,n\}$$ and distributes $$PK$$ to Alice. The protocol is depicted in the following figure.

$$c_i(1\leq i\leq \upsilon)$$ are elements hold by client, $$s_j(1\leq j\leq \omega)$$are the server's, $$H, H'$$ are cryptographic hash functions. In step 2, client blinds her input getting $$y_i$$ which will then be signed by server in step 4, and in step 6, client unblinds the signature. Easy to find that, $$t_i'=H'(D(H(c_i))), t_j=H'(D(H(s_j)))$$, and $$c_i=s_j$$ if $$t_i'=t_j$$ given that $$H,H'$$ are collision-resistent and $$D$$ is PRP.

# References

[1] E. De Cristofaro, G. Tsudik, Practical private set intersection protocols with linear complexity, in: International Conference on Financial Cryptography and Data Security, Springer, 2010: pp. 143–159.

Tags: cryptography.