Research On Private Set Intersection Protocol Based On Garbled Bloom Filter

Private set intersection(PSI)is an important part of information security,and has a wide range of applications such as measuring advertising conversion rates,fingerprint matching,botnet detection,human genome testing,and proximity testing.Private set intersection allows multiple parties to jointly compute and obtain the intersection of their own sets without revealing any information.However,the existing private set intersection protocols have low efficiency and are not suitable for portable devices with weak computing power.In addition,in the multi-party private set intersection protocols,the collusion between corrupted parties results in the failure of the protocol.Aiming at the above problems,we propose two secure and efficient private set intersection protocols based on the garbled Bloom filter.(1)Aiming at the problem that the existing threshold private set intersection protocols have low efficiency,we proposed an efficient threshold private set intersection protocol based on the garbled Bloom filter,which achieves computational security in semi-honest model.To improve the efficiency of the threshold private set intersection protocol,we design a new threshold private set intersection protocol based on garbled Bloom filter and threshold secret sharing,which uses a small amount of public-key operations.Moreover,our protocol combines with the Reed-Solomon decoding algorithm to reconstruct the secret which is a feasible method to avoid calculating all possible combinations among the shares.The performance analysis shows that our protocol is more efficient than the previous threshold private set intersection protocols.(2)Aiming at the problems caused by the collusion between participants in the existing multi-party private set intersection protocols,we proposed a three-party private set intersection protocol based on garbled Bloom filter.First of all,we improve the secret sharing algorithm and avoids the information leakage of the participants in the interaction process.Then,the protocol uses lightweight cryptographic primitives,such as hash functions,oblivious transfer extension,etc.,avoiding a large number of expensive public key operations.The performance analysis shows that the computational complexity of the protocol is O(m)and the communication complexity of the protocol is O(m?).Finally,we give the proofs of the above two private set intersection protocols.At the same time,the performance and efficiency of the two protocols is compared with the existing private set intersection protocols.The proof of security and performance analysis show that the two protocols are secure and effective.