Private Set Intersection Based on Lightweight Oblivious Key-Value Storage Structure

Abstract

At this stage, the application of Private Set Intersection (PSI) protocols is essential for smart homes. Oblivious Key-Value Stores (OKVS) can be used to design efficient PSI protocols. Constructing OKVS with a cuckoo hashing graph is a common approach. It increases the number of hash functions while reducing the possibility of collisions into rings. However, the existing OKVS construction scheme requires a high time overhead, and such an OKVS applied to PSI protocols would also have a high communication overhead. In this paper, we propose a method called 3-Hash Garbled Cuckoo Graph (3H-GCG) for constructing cuckoo hash graphs. Specifically, this method handles hash collisions between different keys more efficiently than existing methods, and it can also be used to construct an OKVS structure with less storage space. Based on the 3H-GCG, we design a PSI protocol using the Vector Oblivious Linear Evaluation (VOLE) and OKVS paradigm, which achieves semi-honest security and malicious security. Extensive experiments demonstrate the effectiveness of our method. When the set size is 218–220, our PSI protocol is less computationally intensive than other existing protocols. The experiments also show an increase in the ratio of raw to constructed data of about 7.5%. With the semi-honest security setting, our protocol achieves the fastest runtime with the set size of 218. With malicious security settings, our protocol has about 10% improvement in communication compared with other existing protocols.

Keywords

• private set intersection
• oblivious key-value stores
• cuckoo hashing graph