Towards Secure Bilateral Friend Query with Conjunctive Policy Matching in Social Networks

Bilateral friend queries have attracted increasing interest in social networks, as each user has a common requirement to specify a policy for the other. However, existing bilateral friend query schemes either only cannot support conjunctive policy matching, where the match is successful if the policy is a subset of attributes, or compromise user privacy, which reduces users' enthusiasm for friend query services. In this paper, we propose a secure bilateral friend query with conjunctive policy matching named BFQ. Specifically, the matchmaking encryption technique is utilized to achieve bilateral policy specification, where both sender and requester can specify policies for the other. Then, based on the Newton interpolation theorem, we design a novel conjunctive policy matching algorithm, where the match succeeds if and only if user authenticity holds and the policies of both parties are the subset of attributes. Otherwise, nothing is revealed except whether the match occurs or not. Security analysis proves that user authenticity and privacy, i.e., attribute privacy, policy privacy, and match privacy, are well guaranteed under the chosen-plaintext attack. We then implement a real prototype application and demonstrate that BFQ has practical efficiency through theoretical and experimental evaluation.