30 January 2024 in IEEE Transactions on Cloud Computing
Private set intersection cardinality (PSI-CA) allows two parties to learn the size of the intersection between two private sets without revealing other additional information, which is a promising technique to solve privacy concerns in contact tracing. Efficient PSI protocols typically use oblivious transfer, involving multiple rounds of interaction and leading to heavy local computation overheads and protocol delays, especially when interacting with many receivers. Cloud-assisted PSI-CA is a better solution as it relieves participants' burdens of computation and communication. However, cloud servers may return incorrect or incomplete results for some reason, leading to an incorrectness issue. At present, to our knowledge, existing cloud-assisted PSI-CA protocols cannot address such a concern. To address this, we propose two specific verifiable cloud-assisted PSI-CA protocols: one based on a two-server protocol and the other on a single-server protocol. Further, we employ Cuckoo hashing to optimize these two protocols, enabling the receiver's computational costs independent of the size of the sender's set. We also prove the security of the protocols and implement them. Finally, we analyze and discuss their performance demonstrating that the single-server verifiable PSI-CA protocol does not introduce significant computation or communication costs while adding functionalities.
5 February 2024 in IEEE Transactions on Cloud Computing
Laconic Private Set Intersection (LPSI) is a type of PSI protocols characterized by the requirement of only two-round interactions and by having a reused message in the first round that is independent of the set size. Recently, Aranha et al. (CCS'2022) proposed a LPSI protocol that utilizes the pairing-based accumulator. However, this protocol heavily relies on time-consuming bilinear pairing operations, which can potentially cause a bottleneck. Furthermore, in certain scenarios like contact tracing, it is sufficient to only reveal the intersection cardinality. To tackle this problem and expand on its functionalities, we introduce a cloud-assisted two-party LPSI cardinality (TLPSI-CA) that inherits the properties of LPSI. Interestingly, the cloud-assisted TLPSI-CA eliminates the direct interaction between the sender and receiver, enabling the sender's message to be reused across any number of protocol executions. Besides, we further extend it to the multi-party scenario, which also possesses laconic properties. Then, we prove the two protocols' security in achieving the defined ideal functionalities. Finally, we evaluate the performance of both protocols and find that TLPSI-CA successfully reduces the local computation costs for participants. Additionally, the multi-party protocol performs similarly to TLPSI-CA, with the exception of the higher communication costs incurred by the receiver.
11 January 2024 in Peer-to-Peer Networking and Applications