search

osu-crypto / libPSI

A repository for private set intersection.
Other
168 stars 47 forks source link

Some questions about PSI protocol #34

Closed HaoXuan40404 closed 2 years ago

HaoXuan40404 commented 2 years ago

I'm testing some PSI protocols like kkrt, and trying to make both participants get the interaction set result, then I got some questions about this protocol.

In KKRT, the receiver has ri, and the sender has seed ki. After both parties run OPRF, the receiver receives F(ki, ri). If the receiver sends F(ki, ri) to the sender, whether the sender has a certain probability can be reversed. Receiver's private data ri?

If A and B, C perform KKRT PSI, we want A to finally obtain the intersection of A and B and the intersection of A and C, and do not want A to know which intersection comes from B and which comes from C. Is it possible to add a coordinator? A、B run OPRF and send the PRF of both parties to the coordinator; A、C run OPRF and send the PRFs of both parties to the coordinator; the coordinator compares the PRFs, and finally returns the intersection result to A. If the coordinator and B collide, can the coordinator deduce the set elements of A?

ladnir commented 2 years ago

Do not send F(ki,ri) to the sender. They can brute force ri. If you want both parties to learn the intersection, the receiver can simply send the intersection at the end.

For multi-party, i think its non-trivial if you want a dishonest majority (collusion). Ni has some good protocols for computing A intersect B intersect C. But it sounds like you want to compute

(A intersect B) union (A intersect C)

You might be able to come up with some way to do this but I think it's somewhat non-trivial. You could use this paper https://eprint.iacr.org/2019/518.pdf . It can do the desired computation but is in the honest majority three-party setting.

HaoXuan40404 commented 2 years ago

Does the probability of brute force cracking depend on the length of ri，and what length of ri can make the probability negligible?

ladnir commented 2 years ago

None. It's the same as simply sending H(ri) and skipping the psi.

HaoXuan40404 commented 2 years ago

H here is the PRF in KKRT, not the hash, is there still this conclusion?

ladnir commented 2 years ago

Not sure what you mean.

If you send F(ki, ri) then this is equivalent to sending H(ri) where H is some public hahs function. Kkrt completely pointless if you do this. You might as well do niave hashing.

This does not solve your three party thing.