Efficient Multi-subset Fine-grained Authorization PSI over Outsourced Encrypted Datasets

Private set intersection (PSI) is an important cryptographic primitive with many real-world applications. Delegating PSI computation to the cloud can effectively reduce management and computational costs of data owners, and therefore has received widespread attention from researchers. However, in the existing delegated PSI schemes, it is hard for the data owner to authorize only a part of its outsourced data, and for users to flexibly select a part of the outsourced encrypted data of the data owner for intersection computation. In this paper, we propose the multi-subset fine-grained authorization PSI (MA-PSI) over outsourced encrypted datasets. Specially, our protocol is designed for the multi-subset case where each subset is associated with one single tag for data classification. Through tag classification and encryption technology, the data owner can perform fine-grained authorization on its subsets. By querying tags, the user can flexibly select any subset of the data owner for intersection computation. The security definition of the MA-PSI protocol is given, and its security is proved in the semi-honest model. Experimental results show that our protocol is very efficient and the computational cost is linear with the size of the subset. Specifically, the intersection algorithm SetI in our MA-PSI is about 80× (the subset size is 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">15</sup>) - 2500× (the subset size is 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">10</sup>) faster than APSI (Wang et al., IEEE TIFS 2021).