# Anticollusion Attack Strategy Combining Trust Metrics and Secret Sharing for Friendships Protection

Authors: Junfeng Tian; Yue Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Online social networks provide users with services such as online interaction, instant messaging, and information sharing. The friend search engine, a new type of social application, provides users with the service for querying the list of other individuals’ friends. Currently, the existing research focuses on independent attacks for friend search engines while ignoring the more complicated collusion attacks, which can expose more friendships that users are not willing to share. Compared with independent attackers, collusion attackers share query results by cooperating with each other. In this article, we propose a resistance strategy against collusion attacks to protect the friendship privacy. The proposed trust metric is based on users’ behaviors and is combined with Shamir’s secret sharing system, which can transform friendships into secrets. Through secret distribution and reconfiguration, only the participants who meet the query requirements can successfully reconstruct the secret, while the participants who do not meet the query conditions cannot successfully obtain the secret fragments even if they obtain the secret fragments. Experiments are conducted to verify the effectiveness of the proposed strategy and proved that this strategy can greatly limit the number of malicious attackers, greatly reduce the probability of successful collusion attacks, and reduce the number of victims.


---

## Body

## 1. Introduction

Friendship, as the beginning of social networks, is one of the most important factors in the development of online social networks (OSNs). Friendship is also the basis of social relationships. The friend search engine was born with the development of social networks. It provides a service for users in social networks to browse other users’ friends list. According to “findermind,” the top 25 friend search engines help users find anyone for free and with high quality [1]. The powerful function of searching friends with friend search engines provides great convenience for users to search for familiar or interested friends and potentially attracts more people to join social networks.


### 1.1. Problem Identification

Friend search engines may reveal more friendships than users are willing to share, which is considered a privacy violation. Without a proper protection strategy to address such privacy leakage, friendships that users do not want to display are always revealed, which will lead to users no longer using OSNs. Currently, available protection schemes [2] have been shown to resist malicious queries of friendships by independent attackers. The social network can record the query history of each individual requester, and when a query is made to the same user, the attacker always obtains the same friends list as a result of the query. With a defence strategy, an independent attacker cannot query for friendships outside the user’s privacy settings.A complicity attack by multiple queries has emerged [3]. It is accomplished by multiple malicious attackers who share query results by coordinating the query targets and sequences to make users reveal their friendships outside the privacy settings. Collusion attackers can gain access to the users’ friendships that cannot be queried by independent attackers. Since existing defence strategies can only protect friendship privacy from independent attacks, they cannot effectively resist conspiracy attacks. However, the FriendGuard supports only two kinds of friend searches, including unweighted and popularity-based friend search [4]. The methods and characteristics of the conspiracy attacks need to be analyzed, and the query strategy needs to be studied and improved in order to protect the friendship privacy. The data sharing framework can resolve potential data leakage [5]. We focus on the design of an anticollusion attack strategy that is aimed at the privacy of users’ friendships in OSNs.


### 1.2. Methods and Contributions

Friendships serve as the basis for interaction between users in social networks and as an extension of interpersonal relationships in the real world. Collusion attacks on friendships can lead to the leakage of interpersonal relationships outside the user’s settings, which will cause a more serious impact on the stability of OSNs. To address such complicity attacks in social networks, we design a privacy protection strategy for friendships that can resist complicity attacks by combining the trust metric [6] with a t,n threshold function [7], drawing on the idea of secret sharing. The main contributions can be divided into the following three aspects:A method to measure trust based on users’ interaction behaviors is proposed. Combining the important features of users’ interactions, the attributes that affect the trust metric are identified. Direct trust, recommendation trust, and comprehensive trust are calculated, and the friend queriers are classified according to the trust metric to control them when they query friendships.A privacy-preserving strategy for friendships that can resist conspiracy attacks is proposed. The trust metric is combined with the Shamir Secret Sharing (SSS) system to transform friendships into secrets. Thet,n threshold function is specially applied so that after sharing the secret, only a subset of the target user’s friendships can be successfully queried by satisfying a specific condition, thus protecting the privacy of friendships.The experimental design and implementation are described. First, the rationality of the trust metric is verified by a probabilistic random function. Then, the security is verified by experimenting against the collusion attack scheme. The feasibility and security are illustrated in terms of the limit rate, the number of victims, the number of attackers, and the probability of successful attacks.


## 1.1. Problem Identification

Friend search engines may reveal more friendships than users are willing to share, which is considered a privacy violation. Without a proper protection strategy to address such privacy leakage, friendships that users do not want to display are always revealed, which will lead to users no longer using OSNs. Currently, available protection schemes [2] have been shown to resist malicious queries of friendships by independent attackers. The social network can record the query history of each individual requester, and when a query is made to the same user, the attacker always obtains the same friends list as a result of the query. With a defence strategy, an independent attacker cannot query for friendships outside the user’s privacy settings.A complicity attack by multiple queries has emerged [3]. It is accomplished by multiple malicious attackers who share query results by coordinating the query targets and sequences to make users reveal their friendships outside the privacy settings. Collusion attackers can gain access to the users’ friendships that cannot be queried by independent attackers. Since existing defence strategies can only protect friendship privacy from independent attacks, they cannot effectively resist conspiracy attacks. However, the FriendGuard supports only two kinds of friend searches, including unweighted and popularity-based friend search [4]. The methods and characteristics of the conspiracy attacks need to be analyzed, and the query strategy needs to be studied and improved in order to protect the friendship privacy. The data sharing framework can resolve potential data leakage [5]. We focus on the design of an anticollusion attack strategy that is aimed at the privacy of users’ friendships in OSNs.


## 1.2. Methods and Contributions

Friendships serve as the basis for interaction between users in social networks and as an extension of interpersonal relationships in the real world. Collusion attacks on friendships can lead to the leakage of interpersonal relationships outside the user’s settings, which will cause a more serious impact on the stability of OSNs. To address such complicity attacks in social networks, we design a privacy protection strategy for friendships that can resist complicity attacks by combining the trust metric [6] with a t,n threshold function [7], drawing on the idea of secret sharing. The main contributions can be divided into the following three aspects:A method to measure trust based on users’ interaction behaviors is proposed. Combining the important features of users’ interactions, the attributes that affect the trust metric are identified. Direct trust, recommendation trust, and comprehensive trust are calculated, and the friend queriers are classified according to the trust metric to control them when they query friendships.A privacy-preserving strategy for friendships that can resist conspiracy attacks is proposed. The trust metric is combined with the Shamir Secret Sharing (SSS) system to transform friendships into secrets. Thet,n threshold function is specially applied so that after sharing the secret, only a subset of the target user’s friendships can be successfully queried by satisfying a specific condition, thus protecting the privacy of friendships.The experimental design and implementation are described. First, the rationality of the trust metric is verified by a probabilistic random function. Then, the security is verified by experimenting against the collusion attack scheme. The feasibility and security are illustrated in terms of the limit rate, the number of victims, the number of attackers, and the probability of successful attacks.


## 2. Related Works

### 2.1. Attacks on the Privacy of Friendships

The number of users in OSNs continues to grow. Tens of thousands of users search for new friends and establish new contacts every day. Therefore, the privacy problem in friend search engines has attracted the attention of many researchers. Attacks against the privacy of friendships in OSNs can be divided into two categories: attacks initiated by independent attackers and by colluding attackers.Regarding independent attacks, research on modeling malicious attacks in OSNs showed that malicious individuals use the actual trust relationship between users and their family and friends to spread malware via OSNs [8]. By changing the display of malicious posts and personal information and hiding him/herself to avoid detection, an attacker in a chameleon attack, which is a new type of deception based on OSNs, is able to destroy users’ privacy [9]. Studies have also shown that when the topology of OSNs does not contain cycles, malicious entities will violate users’ privacy via active attacks if the network structure is not carefully designed [10]. Due to the rapid development of convolutional neural networks in recent years, applying them to social networks can result in very effective reasoning attacks and make high-precision predictions about private data [11]. In the heuristic attack model based on the Dopv attack [12], the attacker obtains the number of friends of the victim from two published social network graphs by spoofing the trust or browsing the homepage. The tag symmetry attack identifies a pair of friends by marking two fixed-point tags that connect the same edge [13]. An attacker can also identify the friendships of a pair of users by the number of their mutual friends [14]. Although OSN can hide the identity of the user by removing the user’s identifier, an attacker can use other contextual information about the OSN to infer the identity of the target user [15].Collusion attacks involve multiple malicious entities with the aim of launching a malicious attack through the coordination of multiple malicious entities to obtain more private information than is obtained in independent attacks. Multiple malicious entities can be fake accounts that are created by a single attacker or different real attackers [16, 17].The router and users can maliciously collude to perform a collusion name guessing attack to compromise people’s privacy [18]. Compared with independent attacks, collusion attacks are more complex and often exploit system vulnerabilities that independent attacks cannot detect. There is a complex collusion attack strategy in which multiple malicious users coordinate their queries, share the query results, and dynamically adjust their query based on the system’s feedback to other malicious requestors [3].


### 2.2. Protection on the Privacy of Friendships

The actual parameter settings of social network providers have an impact on the display of users’ personal information [19]. The personalized privacy measurement algorithm can calculate the user’s privacy level, thereby protecting privacy data [20]. Moreover, the classification-anonymity model effectively guarantees the privacy of sensitive data [21]. Users’ privacy is secured by encrypting data, and only authorized parties who have obtained the key can decrypt the encrypted content [22]. The blockchain-based secure key management scheme can improve trustworthiness more effectively and efficiently [23].The additive secret sharing technique can encrypt raw data into two ciphertexts and construct two classes of secure functions, which can be used to implement a privacy-preserving convolutional neural network [24]. Trust and identity are fundamental issues in social and online environments, and trust management can help users build trust and establish relationships with other users [25]. Existing relationships of users in social networks can be described as one-hop trust relationships, and further multihop trust relationships are built during the recommendation process [26]. When a user involves data items from multiple users, the trust value among users can be used to weigh the weight of user opinions to determine whether the data items are released or not, thus enabling collaborative privacy management [27]. In addition, a series of studies have proposed an unsupervised trust inference algorithm that is based on collaborative filtering in weighted social networks and a fast and robust trust inference algorithm [28, 29] to strengthen the security of social networks via trust inference and to satisfy the goal of differential privacy, a privacy and availability data clustering (PADC) scheme based on k -means algorithm and differential privacy is proposed, which can enhance the selection of the initial center points and the distance calculation method from other points to the center point [30].However, researchers rarely consider privacy leakage problems caused by the friend search service provided by OSNs. Research on these problems can address the privacy needs of users’ friends while ensuring the sociality of OSNs. The solution adopted by most OSNs is to allow each individual user to choose to completely display or completely hide their entire friend list. Moreover, OSNs often default their users to expose the entire friend list, of which most users are unaware [31]. It is conceivable that this setting aims to increase the sociality of the OSN. If users set their friend list to be completely hidden to protect the privacy of their friendships, this setting will substantially affect the sociality of OSNs. There are also some OSNs that set the users’ friend list display to “show only a fixed number.” For example, on Facebook, the number of friends displayed is set to 8, which limits the flexibility of users in changing their personal settings. However, some researchers have discovered that randomly displaying eight friends is sufficient for third parties to obtain data to estimate friend lists [32]. Moreover, regarding the different privacy settings of users, consider the following example: if A and B are friends, even if user A hides his or her friend list and the requestor cannot query the friend list of A, if user B is set to display his or her friend list, when the requestor queries the friend list of B, the friendships of B and A will be displayed and destroy A’s privacy. This problem is referred to as the “mutual effect” [2].To better protect the privacy of users’ friendships in OSNs, a privacy protection strategy in the friend search engine [2] was shown to successfully resist attacks initiated by independent attackers. However, the strategy was unable to defend against collusion attacks initiated by multiple malicious attackers. Subsequently, an advanced collusion attack strategy coordinated by multiple malicious requestors [3] showed that multiple malicious requestors with limited knowledge of OSNs can successfully destroy users’ privacy settings in the friend search engine. Another study [33] implemented web applications to detect malicious behavior such as collusion attacks in the friend search engine. However, few researchers have investigated how to resist collusion attacks initiated by malicious attackers in friend search engines.In this article, we propose an anticollusion attack strategy to fill these research gaps. This strategy distinguishes trusted users from untrusted users based on the credibility among users in OSNs and uses thet,n threshold function to limit the querying of requestors in the friend search engine to resist malicious attacks initiated by colluding attackers in OSNs.


## 2.1. Attacks on the Privacy of Friendships

The number of users in OSNs continues to grow. Tens of thousands of users search for new friends and establish new contacts every day. Therefore, the privacy problem in friend search engines has attracted the attention of many researchers. Attacks against the privacy of friendships in OSNs can be divided into two categories: attacks initiated by independent attackers and by colluding attackers.Regarding independent attacks, research on modeling malicious attacks in OSNs showed that malicious individuals use the actual trust relationship between users and their family and friends to spread malware via OSNs [8]. By changing the display of malicious posts and personal information and hiding him/herself to avoid detection, an attacker in a chameleon attack, which is a new type of deception based on OSNs, is able to destroy users’ privacy [9]. Studies have also shown that when the topology of OSNs does not contain cycles, malicious entities will violate users’ privacy via active attacks if the network structure is not carefully designed [10]. Due to the rapid development of convolutional neural networks in recent years, applying them to social networks can result in very effective reasoning attacks and make high-precision predictions about private data [11]. In the heuristic attack model based on the Dopv attack [12], the attacker obtains the number of friends of the victim from two published social network graphs by spoofing the trust or browsing the homepage. The tag symmetry attack identifies a pair of friends by marking two fixed-point tags that connect the same edge [13]. An attacker can also identify the friendships of a pair of users by the number of their mutual friends [14]. Although OSN can hide the identity of the user by removing the user’s identifier, an attacker can use other contextual information about the OSN to infer the identity of the target user [15].Collusion attacks involve multiple malicious entities with the aim of launching a malicious attack through the coordination of multiple malicious entities to obtain more private information than is obtained in independent attacks. Multiple malicious entities can be fake accounts that are created by a single attacker or different real attackers [16, 17].The router and users can maliciously collude to perform a collusion name guessing attack to compromise people’s privacy [18]. Compared with independent attacks, collusion attacks are more complex and often exploit system vulnerabilities that independent attacks cannot detect. There is a complex collusion attack strategy in which multiple malicious users coordinate their queries, share the query results, and dynamically adjust their query based on the system’s feedback to other malicious requestors [3].


## 2.2. Protection on the Privacy of Friendships

The actual parameter settings of social network providers have an impact on the display of users’ personal information [19]. The personalized privacy measurement algorithm can calculate the user’s privacy level, thereby protecting privacy data [20]. Moreover, the classification-anonymity model effectively guarantees the privacy of sensitive data [21]. Users’ privacy is secured by encrypting data, and only authorized parties who have obtained the key can decrypt the encrypted content [22]. The blockchain-based secure key management scheme can improve trustworthiness more effectively and efficiently [23].The additive secret sharing technique can encrypt raw data into two ciphertexts and construct two classes of secure functions, which can be used to implement a privacy-preserving convolutional neural network [24]. Trust and identity are fundamental issues in social and online environments, and trust management can help users build trust and establish relationships with other users [25]. Existing relationships of users in social networks can be described as one-hop trust relationships, and further multihop trust relationships are built during the recommendation process [26]. When a user involves data items from multiple users, the trust value among users can be used to weigh the weight of user opinions to determine whether the data items are released or not, thus enabling collaborative privacy management [27]. In addition, a series of studies have proposed an unsupervised trust inference algorithm that is based on collaborative filtering in weighted social networks and a fast and robust trust inference algorithm [28, 29] to strengthen the security of social networks via trust inference and to satisfy the goal of differential privacy, a privacy and availability data clustering (PADC) scheme based on k -means algorithm and differential privacy is proposed, which can enhance the selection of the initial center points and the distance calculation method from other points to the center point [30].However, researchers rarely consider privacy leakage problems caused by the friend search service provided by OSNs. Research on these problems can address the privacy needs of users’ friends while ensuring the sociality of OSNs. The solution adopted by most OSNs is to allow each individual user to choose to completely display or completely hide their entire friend list. Moreover, OSNs often default their users to expose the entire friend list, of which most users are unaware [31]. It is conceivable that this setting aims to increase the sociality of the OSN. If users set their friend list to be completely hidden to protect the privacy of their friendships, this setting will substantially affect the sociality of OSNs. There are also some OSNs that set the users’ friend list display to “show only a fixed number.” For example, on Facebook, the number of friends displayed is set to 8, which limits the flexibility of users in changing their personal settings. However, some researchers have discovered that randomly displaying eight friends is sufficient for third parties to obtain data to estimate friend lists [32]. Moreover, regarding the different privacy settings of users, consider the following example: if A and B are friends, even if user A hides his or her friend list and the requestor cannot query the friend list of A, if user B is set to display his or her friend list, when the requestor queries the friend list of B, the friendships of B and A will be displayed and destroy A’s privacy. This problem is referred to as the “mutual effect” [2].To better protect the privacy of users’ friendships in OSNs, a privacy protection strategy in the friend search engine [2] was shown to successfully resist attacks initiated by independent attackers. However, the strategy was unable to defend against collusion attacks initiated by multiple malicious attackers. Subsequently, an advanced collusion attack strategy coordinated by multiple malicious requestors [3] showed that multiple malicious requestors with limited knowledge of OSNs can successfully destroy users’ privacy settings in the friend search engine. Another study [33] implemented web applications to detect malicious behavior such as collusion attacks in the friend search engine. However, few researchers have investigated how to resist collusion attacks initiated by malicious attackers in friend search engines.In this article, we propose an anticollusion attack strategy to fill these research gaps. This strategy distinguishes trusted users from untrusted users based on the credibility among users in OSNs and uses thet,n threshold function to limit the querying of requestors in the friend search engine to resist malicious attacks initiated by colluding attackers in OSNs.


## 3. Collusion Attack Strategy

### 3.1. Related Definitions

In friend search engines, to strengthen the protection of the user’s friendships, a certain number of friendships, such ask, will be displayed when responding to a query request. These k friends are defined as the most influential friends of the users in the OSN. Assume that node Na exists in the OSN with direct friends Na.i and that set is Faki<k. Requestor Q1 wants to query Na’s friendships; two nodes, N1 and N2, exist, and k=1. N1 and N2 are each user’s most important friends.


#### 3.1.1. Unpopular Node

Na is an unpopular node if nodes Na.i∈Fak and Na∉Fka.i. As Figure 1 shows, N0 is an unpopular node.Figure 1
Unpopular node.


#### 3.1.2. Popular Node

Na is a popular node if Na∈Fa.ik and Na.i∈Fak. As Figure 2 shows, N0 is a popular node.Figure 2
Popular node.


#### 3.1.3. Occupation

If requestorQ1 queries node N1, based on the friend search engine display strategy, the query result is EN1,N2. At this time, N1 has shown his or her most important friend N2, and N1 is occupied.


#### 3.1.4. Passive Display

RequestorQ1 queries the important friend list of N1. Based on the friend search engine strategy, the query result is EN1,N2. The most important friend who exposes N2 is N1, and N2 is referred to as a passive display.


### 3.2. Attack Model

#### 3.2.1. Maximum Number of Friends Displayed

Due to the different personal preferences of users in OSNs, their privacy settings will also be different. The maximum number of friends displayed,k, may also be different. This strategy assumes that all nodes have the same k value.


#### 3.2.2. Attackers’ Prior Knowledge

Typically, the success of a malicious requestor’s attack is closely related to his or her knowledge of OSNs. The attack success rate of malicious requestors who know more about OSNs is expected to be higher. This article assumes that malicious requestors have limited knowledge of OSNs and are limited only to target nodes.


#### 3.2.3. Attack Target

The goal of the malicious query is to violate the privacy of the target user in the OSN (i.e., to query thek + 1th friend of the target node). When the privacy of the target user is set to show a number of friends less than k, the privacy of the target user cannot be violated. Each malicious requestor’s attack target is unique, and each collusion attack has only one victim node. Although malicious requestors may infringe the privacy of other users during the query process, only when the privacy of the target node is destroyed is the collusion attack considered successful.


#### 3.2.4. Attack Strategy

Collusion attackers in OSNs can query users’ friendships via the friend search engine and query the relationship between users and friends by coordinating the query sequence and query targets.(1) Attacks on Unpopular Nodes. When the target user is an unpopular node, since there exists at least one node Na.i∈Fak， and Na∉Fa.ik. Therefore, the first malicious attacker obtains the set of its friends Fak by querying Na’s friends and shares the query result with the new attacker. The new malicious attacker can query Na’s friends Na.i separately by the query result shared by the first malicious attacker and always find the node in Fa.ik where Na does not exist. Suppose the node is Na.x, and a query on Na.x can show its kfriends so that it is occupied. At this point, if a query is performed again on the target node Na, Na will display its k+1th friend Na.k+1 since Na.x is already occupied.Suppose there exists a malicious attackerMRii=1,2,…, k=1. Taking the unpopular node in Figure 1 as an example to illustrate the attack process on the nonpopular node. The results are shown in Table 1.Table 1
Attack process on unpopular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.12MR2N0.1EN0.1,N0.1.1N0EN0,N0.2(2) Attacks on Popular Nodes. Analogous to the attack on unpopular nodes, the basic idea of the attack on popular nodes is also to expose the k+1th friend of the target node by occupying one of its top k friends. However, since both popular nodes and their friends are each other’s first k friends, directly querying the friends of the target popular node cannot destroy its friendship privacy by appropriation. Therefore, Na.i is occupied k times by passively displaying Na.i. However, when the target node and its friend Na.1 are each other’s first important friend, they cannot be passively displayed.TakingN0 as the target node in Figure 3 as an example, suppose there exist malicious attackers MRii=1,2,… with k=3, The attack process of an attack on popular node N0 is shown in Table 2.Figure 3
Friendship of popular nodeN0.Table 2
Attack process on popular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.1,EN0,N0.2,EN0,N0.32MR2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N03MR3N0.2.1EN0.2.1,N0.2.1.1,EN0.2.1,N0.2,EN0.2.1,N0.2.1.2N0.2.2EN0.2.2,N0.2.2.1,EN0.2.2,N0.2.2.2,EN0.2.2,N0.2.2.3N0.2EN0.2,N0.2.1,EN0.2,N0,EN0.2,N0.2.34MR4N0.2.3EN0.2.3,N0.2.3.1,EN0.2.3,N0.2,EN0.2.3,N0.2.3.2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N0.2.3N0EN0,N0.1,EN0,N0.3,EN0,N0.4


## 3.1. Related Definitions

In friend search engines, to strengthen the protection of the user’s friendships, a certain number of friendships, such ask, will be displayed when responding to a query request. These k friends are defined as the most influential friends of the users in the OSN. Assume that node Na exists in the OSN with direct friends Na.i and that set is Faki<k. Requestor Q1 wants to query Na’s friendships; two nodes, N1 and N2, exist, and k=1. N1 and N2 are each user’s most important friends.


### 3.1.1. Unpopular Node

Na is an unpopular node if nodes Na.i∈Fak and Na∉Fka.i. As Figure 1 shows, N0 is an unpopular node.Figure 1
Unpopular node.


### 3.1.2. Popular Node

Na is a popular node if Na∈Fa.ik and Na.i∈Fak. As Figure 2 shows, N0 is a popular node.Figure 2
Popular node.


### 3.1.3. Occupation

If requestorQ1 queries node N1, based on the friend search engine display strategy, the query result is EN1,N2. At this time, N1 has shown his or her most important friend N2, and N1 is occupied.


### 3.1.4. Passive Display

RequestorQ1 queries the important friend list of N1. Based on the friend search engine strategy, the query result is EN1,N2. The most important friend who exposes N2 is N1, and N2 is referred to as a passive display.


## 3.1.1. Unpopular Node

Na is an unpopular node if nodes Na.i∈Fak and Na∉Fka.i. As Figure 1 shows, N0 is an unpopular node.Figure 1
Unpopular node.


## 3.1.2. Popular Node

Na is a popular node if Na∈Fa.ik and Na.i∈Fak. As Figure 2 shows, N0 is a popular node.Figure 2
Popular node.


## 3.1.3. Occupation

If requestorQ1 queries node N1, based on the friend search engine display strategy, the query result is EN1,N2. At this time, N1 has shown his or her most important friend N2, and N1 is occupied.


## 3.1.4. Passive Display

RequestorQ1 queries the important friend list of N1. Based on the friend search engine strategy, the query result is EN1,N2. The most important friend who exposes N2 is N1, and N2 is referred to as a passive display.


## 3.2. Attack Model

### 3.2.1. Maximum Number of Friends Displayed

Due to the different personal preferences of users in OSNs, their privacy settings will also be different. The maximum number of friends displayed,k, may also be different. This strategy assumes that all nodes have the same k value.


### 3.2.2. Attackers’ Prior Knowledge

Typically, the success of a malicious requestor’s attack is closely related to his or her knowledge of OSNs. The attack success rate of malicious requestors who know more about OSNs is expected to be higher. This article assumes that malicious requestors have limited knowledge of OSNs and are limited only to target nodes.


### 3.2.3. Attack Target

The goal of the malicious query is to violate the privacy of the target user in the OSN (i.e., to query thek + 1th friend of the target node). When the privacy of the target user is set to show a number of friends less than k, the privacy of the target user cannot be violated. Each malicious requestor’s attack target is unique, and each collusion attack has only one victim node. Although malicious requestors may infringe the privacy of other users during the query process, only when the privacy of the target node is destroyed is the collusion attack considered successful.


### 3.2.4. Attack Strategy

Collusion attackers in OSNs can query users’ friendships via the friend search engine and query the relationship between users and friends by coordinating the query sequence and query targets.(1) Attacks on Unpopular Nodes. When the target user is an unpopular node, since there exists at least one node Na.i∈Fak， and Na∉Fa.ik. Therefore, the first malicious attacker obtains the set of its friends Fak by querying Na’s friends and shares the query result with the new attacker. The new malicious attacker can query Na’s friends Na.i separately by the query result shared by the first malicious attacker and always find the node in Fa.ik where Na does not exist. Suppose the node is Na.x, and a query on Na.x can show its kfriends so that it is occupied. At this point, if a query is performed again on the target node Na, Na will display its k+1th friend Na.k+1 since Na.x is already occupied.Suppose there exists a malicious attackerMRii=1,2,…, k=1. Taking the unpopular node in Figure 1 as an example to illustrate the attack process on the nonpopular node. The results are shown in Table 1.Table 1
Attack process on unpopular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.12MR2N0.1EN0.1,N0.1.1N0EN0,N0.2(2) Attacks on Popular Nodes. Analogous to the attack on unpopular nodes, the basic idea of the attack on popular nodes is also to expose the k+1th friend of the target node by occupying one of its top k friends. However, since both popular nodes and their friends are each other’s first k friends, directly querying the friends of the target popular node cannot destroy its friendship privacy by appropriation. Therefore, Na.i is occupied k times by passively displaying Na.i. However, when the target node and its friend Na.1 are each other’s first important friend, they cannot be passively displayed.TakingN0 as the target node in Figure 3 as an example, suppose there exist malicious attackers MRii=1,2,… with k=3, The attack process of an attack on popular node N0 is shown in Table 2.Figure 3
Friendship of popular nodeN0.Table 2
Attack process on popular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.1,EN0,N0.2,EN0,N0.32MR2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N03MR3N0.2.1EN0.2.1,N0.2.1.1,EN0.2.1,N0.2,EN0.2.1,N0.2.1.2N0.2.2EN0.2.2,N0.2.2.1,EN0.2.2,N0.2.2.2,EN0.2.2,N0.2.2.3N0.2EN0.2,N0.2.1,EN0.2,N0,EN0.2,N0.2.34MR4N0.2.3EN0.2.3,N0.2.3.1,EN0.2.3,N0.2,EN0.2.3,N0.2.3.2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N0.2.3N0EN0,N0.1,EN0,N0.3,EN0,N0.4


## 3.2.1. Maximum Number of Friends Displayed

Due to the different personal preferences of users in OSNs, their privacy settings will also be different. The maximum number of friends displayed,k, may also be different. This strategy assumes that all nodes have the same k value.


## 3.2.2. Attackers’ Prior Knowledge

Typically, the success of a malicious requestor’s attack is closely related to his or her knowledge of OSNs. The attack success rate of malicious requestors who know more about OSNs is expected to be higher. This article assumes that malicious requestors have limited knowledge of OSNs and are limited only to target nodes.


## 3.2.3. Attack Target

The goal of the malicious query is to violate the privacy of the target user in the OSN (i.e., to query thek + 1th friend of the target node). When the privacy of the target user is set to show a number of friends less than k, the privacy of the target user cannot be violated. Each malicious requestor’s attack target is unique, and each collusion attack has only one victim node. Although malicious requestors may infringe the privacy of other users during the query process, only when the privacy of the target node is destroyed is the collusion attack considered successful.


## 3.2.4. Attack Strategy

Collusion attackers in OSNs can query users’ friendships via the friend search engine and query the relationship between users and friends by coordinating the query sequence and query targets.(1) Attacks on Unpopular Nodes. When the target user is an unpopular node, since there exists at least one node Na.i∈Fak， and Na∉Fa.ik. Therefore, the first malicious attacker obtains the set of its friends Fak by querying Na’s friends and shares the query result with the new attacker. The new malicious attacker can query Na’s friends Na.i separately by the query result shared by the first malicious attacker and always find the node in Fa.ik where Na does not exist. Suppose the node is Na.x, and a query on Na.x can show its kfriends so that it is occupied. At this point, if a query is performed again on the target node Na, Na will display its k+1th friend Na.k+1 since Na.x is already occupied.Suppose there exists a malicious attackerMRii=1,2,…, k=1. Taking the unpopular node in Figure 1 as an example to illustrate the attack process on the nonpopular node. The results are shown in Table 1.Table 1
Attack process on unpopular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.12MR2N0.1EN0.1,N0.1.1N0EN0,N0.2(2) Attacks on Popular Nodes. Analogous to the attack on unpopular nodes, the basic idea of the attack on popular nodes is also to expose the k+1th friend of the target node by occupying one of its top k friends. However, since both popular nodes and their friends are each other’s first k friends, directly querying the friends of the target popular node cannot destroy its friendship privacy by appropriation. Therefore, Na.i is occupied k times by passively displaying Na.i. However, when the target node and its friend Na.1 are each other’s first important friend, they cannot be passively displayed.TakingN0 as the target node in Figure 3 as an example, suppose there exist malicious attackers MRii=1,2,… with k=3, The attack process of an attack on popular node N0 is shown in Table 2.Figure 3
Friendship of popular nodeN0.Table 2
Attack process on popular nodeN0.
StepRequestorTargetResult1MR1N0EN0,N0.1,EN0,N0.2,EN0,N0.32MR2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N03MR3N0.2.1EN0.2.1,N0.2.1.1,EN0.2.1,N0.2,EN0.2.1,N0.2.1.2N0.2.2EN0.2.2,N0.2.2.1,EN0.2.2,N0.2.2.2,EN0.2.2,N0.2.2.3N0.2EN0.2,N0.2.1,EN0.2,N0,EN0.2,N0.2.34MR4N0.2.3EN0.2.3,N0.2.3.1,EN0.2.3,N0.2,EN0.2.3,N0.2.3.2N0.2EN0.2,N0.2.1,EN0.2,N0.2.2,EN0.2,N0.2.3N0EN0,N0.1,EN0,N0.3,EN0,N0.4


## 4. Anticollusion Attack Strategy of Friendships Protection

The collusion attack compromises users’ friendship privacy by coordinating the query order through multiple malicious requesters and dynamically adjusting the query target through the query results of others. To solve the problem, we investigate the strategy to resist collusion attacks. In this work, the access control of requestors in the friend search engine is considered, credibility is employed as the restriction condition for requestor queries, and the Shamir Secret Sharing (SSS) system is utilized to control queries.


### 4.1. Credibility Calculations

In OSNs, the interaction behaviors between users are an important factor that affects the trust metric between users. According to the relationship between users, the trust relationship between two users, i.e., the trust subject and the trust object, can be divided into three types, that are direct trust, recommendation trust, and comprehensive trust. There are four main attributes that are important for credibility calculations.


#### 4.1.1. Number of Interactions

The greater the number of interactions between two users is, the higher the trust between the users is.


#### 4.1.2. Interaction Evaluation

After each interaction, the user gives a corresponding evaluation based on the process, the results, and the importance of the interaction event. The evaluation value of thelth interaction is recorded as Cl∈0,1.


#### 4.1.3. Interaction Time

Interaction evaluations that are similar to the current time better reflect the user’s recent behavior. The closer the evaluation is to the current time, the greater the impact is on direct credibility.


#### 4.1.4. Interaction Events

The weight of the event of thelth interaction between two users is denoted as Wl.


#### 4.1.5. Direct Trust (DTij)

For two user nodes that have historical interactions in the OSN, the credibility of one user to another is referred to as direct trust. A user obtains the credibility evaluation of another based on the historical performance of the user who has interacted with him or her.If nodei and node j have interacted n times in the OSN, after the lth interaction is completed, node i evaluates node j to obtain evaluation value Cl and interaction event weight Wl. Subsequently, the lth interaction time tl, importance of the lth interaction event Wl, evaluation value Cl of the interaction event of node i with node j, and the influence of the number n of interactions between node i and node j on the evaluation value are considered. The calculation formula of direct trust is expressed as follows:(1)DTij=α⋅∑l=1nΦtl⋅Cl⋅Wn,where α = n/n+1 is a function of the number of interactions used to adjust the influence of the number of interactions on credibility. The user obtains a high degree of trust only when he or she obtains multiple satisfactory evaluation values. φ (tl) = exp (⌈tn−tl/T⌉) is the time decay coefficient, where tn is the nth interaction time (i.e., current interaction time), tl is the lth interaction time, and T is the time period. The evaluation of an interaction event that is more similar to the current interaction time has a greater impact on credibility. Wl and Cl are the weight of the interaction event between node i and node j and the evaluation value of node i for the event, respectively. This approach can prevent malicious requestors from interacting with the target user by using events with a low weight to gain the trust of the target user while deceiving the user during interaction events with high weights.


#### 4.1.6. Recommended Trust (RTij)

If nodei wants to gain a comprehensive understanding of nodej, node i needs to obtain the recommended trust for node j via intermediate node c, where node c=c1,c2,c3,…,cn. The calculation of recommended trust is expressed as follows:(2)RTij=∑c=1nDTic⋅DTcj,where DTic is the direct trust of user i in user c, DTcj is the direct trust of user c in user j, and the direct trust of user i in user c can be regarded as a recommendation for calculating the recommended trust weights.


#### 4.1.7. Comprehensive Trust (OTij)

The credibility of a user in the OSN must be integrated with his or her direct trust and the recommended trust of other users, which is referred to as comprehensive trust. The weights of direct trust and recommended trust are determined by experimental calculations. In real life, people are generally more inclined to believe their judgments, and the recommendations of others serve only as a reference. Thus, the calculation of comprehensive trust is expressed as follows:(3)OTij=u⋅DTij+v⋅RTiju+v=1,u>v,where OTij is the direct trust of node i in node j, RTij is the recommended trust of node i in node j, and u and v are the weight coefficients of direct trust and recommended trust, respectively.


### 4.2. Shamir Secret Sharing System

TheSSS system is a specific secret sharing scheme designed by Shamir based on language interpolation polynomial theory [34, 35]. This scheme clearly illustrates how to divide data D into n segments so that D can be easily reconstructed from t segments and so that even if all t−1 segments are mastered, D cannot be reconstructed.In response to collusion attacks in OSNs, this article uses theSSSt,n threshold function to control the querying of users’ friendships. The t,n threshold SSS consists of the following three stages.


#### 4.2.1. System Parameter Setting

n is the number of all participants, t is the threshold, p is a large prime number, and s∈Zp is the secret to be shared.


#### 4.2.2. Secret Distribution

The secret distributorD chooses a random t degree polynomial.(4)ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp.The conditiona0=s is satisfied. D sends si=ai to participants Pi,i=1,2,…,n.


#### 4.2.3. Secret Reconstruction

Any number of participants can reconstruct the secret using their secret fragments. Lett participants who want to reconstruct the secret be Pi,i=1,2,…,t, and let A=1,2,…,t.λi is calculated based on the following formula:(5)λi=∏j∈A/ijj−i.The original secret is restored based on the following formula:(6)s=∑i∈Asiλ.The security of theSSS depends on the assumption that the parties honestly perform the operations predetermined by the agreement. We consider reliable secret distributors and believe that the administrators of OSNs are honest in the strategy.


### 4.3. Friend Search Engine with the SSS System

#### 4.3.1. Friendships Transform

When a querier queries the friends of a target user, the friend search engine will return the relationship of edges between nodes among users according to the display strategy. However, according to the SSS system and the requirement of thet,n threshold function, the shared secret is s∈Zp with p being a large prime number. The secret s to be shared in this strategy is the friendship of the target. Therefore, it is necessary to process the representation of an important user’s friendship and transform it to the range of Zp and then share it by the threshold function.In order to transform the friendships into shareable secrets, we propose a friendship transform algorithm to convert the friendships to satisfy the secret sharing condition. According to the query goal of the querier, theIDs of the first k friends of the target node are first obtained. The friendships transform algorithm is shown as Algorithm 1.Algorithm 1: Friendships_transform.
Input:IDx: ID of the target userOutput:s: the secret to share(1)
Get theIDs of the top k friends of the target node: ID1, ID2, ID3, …, IDk;(2)
SUMID=∑i=1kIDi;(3)
ifSUMID is prime then(4)
s=SUMID(5)
else(6)
s=find_next_primeSUMID;(7)
end if


#### 4.3.2. Friendships Protection

In OSNs, users can access the friendships of other users by friend search engines. Multiple malicious requestors can share their query results with each other by coordinating the query target and query sequence, which causes the target user to expose more friends than the user is willing to display. A friend search engine that has introduced the trust metric andSSS can control the queries of users. This control can guarantee that only users whose comprehensive trust reaches the trust threshold can successfully query the friendships of the target user.Assume that secret distributorD is honest and that each anonymous requestor Pi,i=1,2,…,n can obtain a correct secret fragment from D. The number of requestors is higher than the trust threshold for querying the friendships of the target user each time nA≥2. The access control process of this solution is described as follows.Obtain Comprehensive Trust. Requestors Pi,i=1,2,…,n request querying the friendships of target user na, obtaining comprehensive trust Tai of Pi, and sorting the results in descending order by value based on the interaction between target user na and requestor Pi in the OSN.Classify the Query. Based on trust threshold TR, the requestors are divided into categories A and B. Category A: Tai∈TR,1 and category B: Tai∈0,TR. The number of requestors in the two categories is denoted as nA and nB.Confirm Thresholdt. According to the definition of the t,n threshold function and the requirements of access control security, requestors who have not reached the system trust threshold cannot successfully query the target user’s friendships. Since Tai<TR, it is necessary to ensure that requestors in category B cannot successfully query the friendships of the target user. Thus, in each query process, t=nB+1.Secret Distribution. The secret distributor D chooses a random t degree polynomial ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp, a0=s. D sends si=ai to participants Pi,i=1,2,…,n.Secret Reconstruction. nB requestors in category B, who are arranged in descending order of comprehensive trust, submit the secret fragments si obtained in reverse order, and nA requestors and nB requestors are divided into nA groups for secret reconstruction.Assume that requestorPii=1,2,…,n, who queries the friendships of the target user, is arranged in descending order based on the comprehensive trust of the target user na. Category A is P1, P2, P3, …, Pm, and category B is Pm+1, Pm+2, …, Pn. Threshold t=nB+1. As shown in Table 3, category A can be divided into m groups to reconstruct secret s.Table 3
Groups to reconstruct secrets.
Group numberGroup member1P1,Pn,Pn−1,…,Pm+12P2,Pn,Pn−1,…,Pm+13P3,Pn,Pn−1,…,Pm+1……mPm,Pn,Pn−1,…,Pm+1The comprehensive trust of the first requestor among them groups of requestors who participate in the secret reconstruction is greater than the trust threshold set by the target user (i.e., only users trusted by the target user can successfully query the target’s friendships). During each secret reconstruction process, the users Pm+1, Pm+2, …, Pn who have not reached the comprehensive trust level threshold must submit their secret fragments sm+1, sm+2, …, sn obtained from D. Users P1, P2, P3, …, Pm will submit sm+1, sm+2, …, sn. The secret fragment sii∈1,m is secretly reconstructed. The threshold t=nB+1 can ensure that even if Pm+1, Pm+2, …, Pn constitute the group of submitted secret fragments, the secret cannot be successfully reconstructed.


#### 4.3.3. Punishment Mechanism

Multiple malicious requestors query the friendships of users by coordinating their query order and query target via the friend search engine. The proposed mechanism further protects the privacy of the target users’ friendships by setting the punishment mechanism. When the user who has inquired about the friendships of the target user causes the privacy leak, the comprehensive trust of the inquirers will be reduced, which will make the next query impossible. Assume that before querying the friendships of the target user, the malicious requestorsMR1 and MR2 are disguised as trusted nodes. If malicious requestors MR1 and MR2 have comprehensive trust Tai, Tai>Tt, during the first query, the malicious requestor MR1 can successfully reconstruct target node na’s friendships by secret fragments submitted by category B users and the secret fragments obtained from D. After the malicious requestor MR1 obtains the query result and shares it with MR2, malicious requestor MR2 can require the other nodes based on the query result of MR1. If the final query result causes the target node to expose the k+1th friend, then the system punishes all nodes that are secretly reconstructed, which reduces the trust value of the user nodes for the reconstructed secret to 1/2 of the original value. The trust decay function is expressed as follows:(7)Ti′=Ti2.Taking the attack in Section3.2.3 as an example, assume that the trust threshold is 0.5 and the comprehensive trust of MR1 and MR2 is the maximum value of 1. According to the collusion attack strategy, N3’s privacy will be violated.When the friend search engine detects that the privacy of userN3 is breached, it will reduce the trust of all users who have queried at this time to punish them. The trust value of MR2 was originally 1. After the punishment, its comprehensive trust is reduced according to the trust decay function, and the comprehensive trust of malicious requestors MR1 and MR2 is reduced from 1 to 0.5. The comprehensive trust obtained from the target user is now lower than the trust threshold, and the next query cannot be performed.


## 4.1. Credibility Calculations

In OSNs, the interaction behaviors between users are an important factor that affects the trust metric between users. According to the relationship between users, the trust relationship between two users, i.e., the trust subject and the trust object, can be divided into three types, that are direct trust, recommendation trust, and comprehensive trust. There are four main attributes that are important for credibility calculations.


### 4.1.1. Number of Interactions

The greater the number of interactions between two users is, the higher the trust between the users is.


### 4.1.2. Interaction Evaluation

After each interaction, the user gives a corresponding evaluation based on the process, the results, and the importance of the interaction event. The evaluation value of thelth interaction is recorded as Cl∈0,1.


### 4.1.3. Interaction Time

Interaction evaluations that are similar to the current time better reflect the user’s recent behavior. The closer the evaluation is to the current time, the greater the impact is on direct credibility.


### 4.1.4. Interaction Events

The weight of the event of thelth interaction between two users is denoted as Wl.


### 4.1.5. Direct Trust (DTij)

For two user nodes that have historical interactions in the OSN, the credibility of one user to another is referred to as direct trust. A user obtains the credibility evaluation of another based on the historical performance of the user who has interacted with him or her.If nodei and node j have interacted n times in the OSN, after the lth interaction is completed, node i evaluates node j to obtain evaluation value Cl and interaction event weight Wl. Subsequently, the lth interaction time tl, importance of the lth interaction event Wl, evaluation value Cl of the interaction event of node i with node j, and the influence of the number n of interactions between node i and node j on the evaluation value are considered. The calculation formula of direct trust is expressed as follows:(1)DTij=α⋅∑l=1nΦtl⋅Cl⋅Wn,where α = n/n+1 is a function of the number of interactions used to adjust the influence of the number of interactions on credibility. The user obtains a high degree of trust only when he or she obtains multiple satisfactory evaluation values. φ (tl) = exp (⌈tn−tl/T⌉) is the time decay coefficient, where tn is the nth interaction time (i.e., current interaction time), tl is the lth interaction time, and T is the time period. The evaluation of an interaction event that is more similar to the current interaction time has a greater impact on credibility. Wl and Cl are the weight of the interaction event between node i and node j and the evaluation value of node i for the event, respectively. This approach can prevent malicious requestors from interacting with the target user by using events with a low weight to gain the trust of the target user while deceiving the user during interaction events with high weights.


### 4.1.6. Recommended Trust (RTij)

If nodei wants to gain a comprehensive understanding of nodej, node i needs to obtain the recommended trust for node j via intermediate node c, where node c=c1,c2,c3,…,cn. The calculation of recommended trust is expressed as follows:(2)RTij=∑c=1nDTic⋅DTcj,where DTic is the direct trust of user i in user c, DTcj is the direct trust of user c in user j, and the direct trust of user i in user c can be regarded as a recommendation for calculating the recommended trust weights.


### 4.1.7. Comprehensive Trust (OTij)

The credibility of a user in the OSN must be integrated with his or her direct trust and the recommended trust of other users, which is referred to as comprehensive trust. The weights of direct trust and recommended trust are determined by experimental calculations. In real life, people are generally more inclined to believe their judgments, and the recommendations of others serve only as a reference. Thus, the calculation of comprehensive trust is expressed as follows:(3)OTij=u⋅DTij+v⋅RTiju+v=1,u>v,where OTij is the direct trust of node i in node j, RTij is the recommended trust of node i in node j, and u and v are the weight coefficients of direct trust and recommended trust, respectively.


## 4.1.1. Number of Interactions

The greater the number of interactions between two users is, the higher the trust between the users is.


## 4.1.2. Interaction Evaluation

After each interaction, the user gives a corresponding evaluation based on the process, the results, and the importance of the interaction event. The evaluation value of thelth interaction is recorded as Cl∈0,1.


## 4.1.3. Interaction Time

Interaction evaluations that are similar to the current time better reflect the user’s recent behavior. The closer the evaluation is to the current time, the greater the impact is on direct credibility.


## 4.1.4. Interaction Events

The weight of the event of thelth interaction between two users is denoted as Wl.


## 4.1.5. Direct Trust (DTij)

For two user nodes that have historical interactions in the OSN, the credibility of one user to another is referred to as direct trust. A user obtains the credibility evaluation of another based on the historical performance of the user who has interacted with him or her.If nodei and node j have interacted n times in the OSN, after the lth interaction is completed, node i evaluates node j to obtain evaluation value Cl and interaction event weight Wl. Subsequently, the lth interaction time tl, importance of the lth interaction event Wl, evaluation value Cl of the interaction event of node i with node j, and the influence of the number n of interactions between node i and node j on the evaluation value are considered. The calculation formula of direct trust is expressed as follows:(1)DTij=α⋅∑l=1nΦtl⋅Cl⋅Wn,where α = n/n+1 is a function of the number of interactions used to adjust the influence of the number of interactions on credibility. The user obtains a high degree of trust only when he or she obtains multiple satisfactory evaluation values. φ (tl) = exp (⌈tn−tl/T⌉) is the time decay coefficient, where tn is the nth interaction time (i.e., current interaction time), tl is the lth interaction time, and T is the time period. The evaluation of an interaction event that is more similar to the current interaction time has a greater impact on credibility. Wl and Cl are the weight of the interaction event between node i and node j and the evaluation value of node i for the event, respectively. This approach can prevent malicious requestors from interacting with the target user by using events with a low weight to gain the trust of the target user while deceiving the user during interaction events with high weights.


## 4.1.6. Recommended Trust (RTij)

If nodei wants to gain a comprehensive understanding of nodej, node i needs to obtain the recommended trust for node j via intermediate node c, where node c=c1,c2,c3,…,cn. The calculation of recommended trust is expressed as follows:(2)RTij=∑c=1nDTic⋅DTcj,where DTic is the direct trust of user i in user c, DTcj is the direct trust of user c in user j, and the direct trust of user i in user c can be regarded as a recommendation for calculating the recommended trust weights.


## 4.1.7. Comprehensive Trust (OTij)

The credibility of a user in the OSN must be integrated with his or her direct trust and the recommended trust of other users, which is referred to as comprehensive trust. The weights of direct trust and recommended trust are determined by experimental calculations. In real life, people are generally more inclined to believe their judgments, and the recommendations of others serve only as a reference. Thus, the calculation of comprehensive trust is expressed as follows:(3)OTij=u⋅DTij+v⋅RTiju+v=1,u>v,where OTij is the direct trust of node i in node j, RTij is the recommended trust of node i in node j, and u and v are the weight coefficients of direct trust and recommended trust, respectively.


## 4.2. Shamir Secret Sharing System

TheSSS system is a specific secret sharing scheme designed by Shamir based on language interpolation polynomial theory [34, 35]. This scheme clearly illustrates how to divide data D into n segments so that D can be easily reconstructed from t segments and so that even if all t−1 segments are mastered, D cannot be reconstructed.In response to collusion attacks in OSNs, this article uses theSSSt,n threshold function to control the querying of users’ friendships. The t,n threshold SSS consists of the following three stages.


### 4.2.1. System Parameter Setting

n is the number of all participants, t is the threshold, p is a large prime number, and s∈Zp is the secret to be shared.


### 4.2.2. Secret Distribution

The secret distributorD chooses a random t degree polynomial.(4)ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp.The conditiona0=s is satisfied. D sends si=ai to participants Pi,i=1,2,…,n.


### 4.2.3. Secret Reconstruction

Any number of participants can reconstruct the secret using their secret fragments. Lett participants who want to reconstruct the secret be Pi,i=1,2,…,t, and let A=1,2,…,t.λi is calculated based on the following formula:(5)λi=∏j∈A/ijj−i.The original secret is restored based on the following formula:(6)s=∑i∈Asiλ.The security of theSSS depends on the assumption that the parties honestly perform the operations predetermined by the agreement. We consider reliable secret distributors and believe that the administrators of OSNs are honest in the strategy.


## 4.2.1. System Parameter Setting

n is the number of all participants, t is the threshold, p is a large prime number, and s∈Zp is the secret to be shared.


## 4.2.2. Secret Distribution

The secret distributorD chooses a random t degree polynomial.(4)ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp.The conditiona0=s is satisfied. D sends si=ai to participants Pi,i=1,2,…,n.


## 4.2.3. Secret Reconstruction

Any number of participants can reconstruct the secret using their secret fragments. Lett participants who want to reconstruct the secret be Pi,i=1,2,…,t, and let A=1,2,…,t.λi is calculated based on the following formula:(5)λi=∏j∈A/ijj−i.The original secret is restored based on the following formula:(6)s=∑i∈Asiλ.The security of theSSS depends on the assumption that the parties honestly perform the operations predetermined by the agreement. We consider reliable secret distributors and believe that the administrators of OSNs are honest in the strategy.


## 4.3. Friend Search Engine with the SSS System

### 4.3.1. Friendships Transform

When a querier queries the friends of a target user, the friend search engine will return the relationship of edges between nodes among users according to the display strategy. However, according to the SSS system and the requirement of thet,n threshold function, the shared secret is s∈Zp with p being a large prime number. The secret s to be shared in this strategy is the friendship of the target. Therefore, it is necessary to process the representation of an important user’s friendship and transform it to the range of Zp and then share it by the threshold function.In order to transform the friendships into shareable secrets, we propose a friendship transform algorithm to convert the friendships to satisfy the secret sharing condition. According to the query goal of the querier, theIDs of the first k friends of the target node are first obtained. The friendships transform algorithm is shown as Algorithm 1.Algorithm 1: Friendships_transform.
Input:IDx: ID of the target userOutput:s: the secret to share(1)
Get theIDs of the top k friends of the target node: ID1, ID2, ID3, …, IDk;(2)
SUMID=∑i=1kIDi;(3)
ifSUMID is prime then(4)
s=SUMID(5)
else(6)
s=find_next_primeSUMID;(7)
end if


### 4.3.2. Friendships Protection

In OSNs, users can access the friendships of other users by friend search engines. Multiple malicious requestors can share their query results with each other by coordinating the query target and query sequence, which causes the target user to expose more friends than the user is willing to display. A friend search engine that has introduced the trust metric andSSS can control the queries of users. This control can guarantee that only users whose comprehensive trust reaches the trust threshold can successfully query the friendships of the target user.Assume that secret distributorD is honest and that each anonymous requestor Pi,i=1,2,…,n can obtain a correct secret fragment from D. The number of requestors is higher than the trust threshold for querying the friendships of the target user each time nA≥2. The access control process of this solution is described as follows.Obtain Comprehensive Trust. Requestors Pi,i=1,2,…,n request querying the friendships of target user na, obtaining comprehensive trust Tai of Pi, and sorting the results in descending order by value based on the interaction between target user na and requestor Pi in the OSN.Classify the Query. Based on trust threshold TR, the requestors are divided into categories A and B. Category A: Tai∈TR,1 and category B: Tai∈0,TR. The number of requestors in the two categories is denoted as nA and nB.Confirm Thresholdt. According to the definition of the t,n threshold function and the requirements of access control security, requestors who have not reached the system trust threshold cannot successfully query the target user’s friendships. Since Tai<TR, it is necessary to ensure that requestors in category B cannot successfully query the friendships of the target user. Thus, in each query process, t=nB+1.Secret Distribution. The secret distributor D chooses a random t degree polynomial ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp, a0=s. D sends si=ai to participants Pi,i=1,2,…,n.Secret Reconstruction. nB requestors in category B, who are arranged in descending order of comprehensive trust, submit the secret fragments si obtained in reverse order, and nA requestors and nB requestors are divided into nA groups for secret reconstruction.Assume that requestorPii=1,2,…,n, who queries the friendships of the target user, is arranged in descending order based on the comprehensive trust of the target user na. Category A is P1, P2, P3, …, Pm, and category B is Pm+1, Pm+2, …, Pn. Threshold t=nB+1. As shown in Table 3, category A can be divided into m groups to reconstruct secret s.Table 3
Groups to reconstruct secrets.
Group numberGroup member1P1,Pn,Pn−1,…,Pm+12P2,Pn,Pn−1,…,Pm+13P3,Pn,Pn−1,…,Pm+1……mPm,Pn,Pn−1,…,Pm+1The comprehensive trust of the first requestor among them groups of requestors who participate in the secret reconstruction is greater than the trust threshold set by the target user (i.e., only users trusted by the target user can successfully query the target’s friendships). During each secret reconstruction process, the users Pm+1, Pm+2, …, Pn who have not reached the comprehensive trust level threshold must submit their secret fragments sm+1, sm+2, …, sn obtained from D. Users P1, P2, P3, …, Pm will submit sm+1, sm+2, …, sn. The secret fragment sii∈1,m is secretly reconstructed. The threshold t=nB+1 can ensure that even if Pm+1, Pm+2, …, Pn constitute the group of submitted secret fragments, the secret cannot be successfully reconstructed.


### 4.3.3. Punishment Mechanism

Multiple malicious requestors query the friendships of users by coordinating their query order and query target via the friend search engine. The proposed mechanism further protects the privacy of the target users’ friendships by setting the punishment mechanism. When the user who has inquired about the friendships of the target user causes the privacy leak, the comprehensive trust of the inquirers will be reduced, which will make the next query impossible. Assume that before querying the friendships of the target user, the malicious requestorsMR1 and MR2 are disguised as trusted nodes. If malicious requestors MR1 and MR2 have comprehensive trust Tai, Tai>Tt, during the first query, the malicious requestor MR1 can successfully reconstruct target node na’s friendships by secret fragments submitted by category B users and the secret fragments obtained from D. After the malicious requestor MR1 obtains the query result and shares it with MR2, malicious requestor MR2 can require the other nodes based on the query result of MR1. If the final query result causes the target node to expose the k+1th friend, then the system punishes all nodes that are secretly reconstructed, which reduces the trust value of the user nodes for the reconstructed secret to 1/2 of the original value. The trust decay function is expressed as follows:(7)Ti′=Ti2.Taking the attack in Section3.2.3 as an example, assume that the trust threshold is 0.5 and the comprehensive trust of MR1 and MR2 is the maximum value of 1. According to the collusion attack strategy, N3’s privacy will be violated.When the friend search engine detects that the privacy of userN3 is breached, it will reduce the trust of all users who have queried at this time to punish them. The trust value of MR2 was originally 1. After the punishment, its comprehensive trust is reduced according to the trust decay function, and the comprehensive trust of malicious requestors MR1 and MR2 is reduced from 1 to 0.5. The comprehensive trust obtained from the target user is now lower than the trust threshold, and the next query cannot be performed.


## 4.3.1. Friendships Transform

When a querier queries the friends of a target user, the friend search engine will return the relationship of edges between nodes among users according to the display strategy. However, according to the SSS system and the requirement of thet,n threshold function, the shared secret is s∈Zp with p being a large prime number. The secret s to be shared in this strategy is the friendship of the target. Therefore, it is necessary to process the representation of an important user’s friendship and transform it to the range of Zp and then share it by the threshold function.In order to transform the friendships into shareable secrets, we propose a friendship transform algorithm to convert the friendships to satisfy the secret sharing condition. According to the query goal of the querier, theIDs of the first k friends of the target node are first obtained. The friendships transform algorithm is shown as Algorithm 1.Algorithm 1: Friendships_transform.
Input:IDx: ID of the target userOutput:s: the secret to share(1)
Get theIDs of the top k friends of the target node: ID1, ID2, ID3, …, IDk;(2)
SUMID=∑i=1kIDi;(3)
ifSUMID is prime then(4)
s=SUMID(5)
else(6)
s=find_next_primeSUMID;(7)
end if


## 4.3.2. Friendships Protection

In OSNs, users can access the friendships of other users by friend search engines. Multiple malicious requestors can share their query results with each other by coordinating the query target and query sequence, which causes the target user to expose more friends than the user is willing to display. A friend search engine that has introduced the trust metric andSSS can control the queries of users. This control can guarantee that only users whose comprehensive trust reaches the trust threshold can successfully query the friendships of the target user.Assume that secret distributorD is honest and that each anonymous requestor Pi,i=1,2,…,n can obtain a correct secret fragment from D. The number of requestors is higher than the trust threshold for querying the friendships of the target user each time nA≥2. The access control process of this solution is described as follows.Obtain Comprehensive Trust. Requestors Pi,i=1,2,…,n request querying the friendships of target user na, obtaining comprehensive trust Tai of Pi, and sorting the results in descending order by value based on the interaction between target user na and requestor Pi in the OSN.Classify the Query. Based on trust threshold TR, the requestors are divided into categories A and B. Category A: Tai∈TR,1 and category B: Tai∈0,TR. The number of requestors in the two categories is denoted as nA and nB.Confirm Thresholdt. According to the definition of the t,n threshold function and the requirements of access control security, requestors who have not reached the system trust threshold cannot successfully query the target user’s friendships. Since Tai<TR, it is necessary to ensure that requestors in category B cannot successfully query the friendships of the target user. Thus, in each query process, t=nB+1.Secret Distribution. The secret distributor D chooses a random t degree polynomial ax=s+a1x1+a2x2+a3x3+⋯+at−1xt−1modp,αj∈RZp, a0=s. D sends si=ai to participants Pi,i=1,2,…,n.Secret Reconstruction. nB requestors in category B, who are arranged in descending order of comprehensive trust, submit the secret fragments si obtained in reverse order, and nA requestors and nB requestors are divided into nA groups for secret reconstruction.Assume that requestorPii=1,2,…,n, who queries the friendships of the target user, is arranged in descending order based on the comprehensive trust of the target user na. Category A is P1, P2, P3, …, Pm, and category B is Pm+1, Pm+2, …, Pn. Threshold t=nB+1. As shown in Table 3, category A can be divided into m groups to reconstruct secret s.Table 3
Groups to reconstruct secrets.
Group numberGroup member1P1,Pn,Pn−1,…,Pm+12P2,Pn,Pn−1,…,Pm+13P3,Pn,Pn−1,…,Pm+1……mPm,Pn,Pn−1,…,Pm+1The comprehensive trust of the first requestor among them groups of requestors who participate in the secret reconstruction is greater than the trust threshold set by the target user (i.e., only users trusted by the target user can successfully query the target’s friendships). During each secret reconstruction process, the users Pm+1, Pm+2, …, Pn who have not reached the comprehensive trust level threshold must submit their secret fragments sm+1, sm+2, …, sn obtained from D. Users P1, P2, P3, …, Pm will submit sm+1, sm+2, …, sn. The secret fragment sii∈1,m is secretly reconstructed. The threshold t=nB+1 can ensure that even if Pm+1, Pm+2, …, Pn constitute the group of submitted secret fragments, the secret cannot be successfully reconstructed.


## 4.3.3. Punishment Mechanism

Multiple malicious requestors query the friendships of users by coordinating their query order and query target via the friend search engine. The proposed mechanism further protects the privacy of the target users’ friendships by setting the punishment mechanism. When the user who has inquired about the friendships of the target user causes the privacy leak, the comprehensive trust of the inquirers will be reduced, which will make the next query impossible. Assume that before querying the friendships of the target user, the malicious requestorsMR1 and MR2 are disguised as trusted nodes. If malicious requestors MR1 and MR2 have comprehensive trust Tai, Tai>Tt, during the first query, the malicious requestor MR1 can successfully reconstruct target node na’s friendships by secret fragments submitted by category B users and the secret fragments obtained from D. After the malicious requestor MR1 obtains the query result and shares it with MR2, malicious requestor MR2 can require the other nodes based on the query result of MR1. If the final query result causes the target node to expose the k+1th friend, then the system punishes all nodes that are secretly reconstructed, which reduces the trust value of the user nodes for the reconstructed secret to 1/2 of the original value. The trust decay function is expressed as follows:(7)Ti′=Ti2.Taking the attack in Section3.2.3 as an example, assume that the trust threshold is 0.5 and the comprehensive trust of MR1 and MR2 is the maximum value of 1. According to the collusion attack strategy, N3’s privacy will be violated.When the friend search engine detects that the privacy of userN3 is breached, it will reduce the trust of all users who have queried at this time to punish them. The trust value of MR2 was originally 1. After the punishment, its comprehensive trust is reduced according to the trust decay function, and the comprehensive trust of malicious requestors MR1 and MR2 is reduced from 1 to 0.5. The comprehensive trust obtained from the target user is now lower than the trust threshold, and the next query cannot be performed.


## 5. Experiment

In this section, we experimentally verify the effectiveness of the proposed anticollusion attack strategy. Our experimental research includes synthetic datasets to verify the validity of the credibility calculations and three large-scale real-world datasets to verify the security of the anticollusion attack strategy.


### 5.1. Datasets

We generate random numbers that satisfy the previously described conditions of the credibility calculation method, including data on 1000 groups of user interactions, and verify the correctness of the trust calculations. In addition, we use three real-world social network datasets to verify the security of the anticollusion attack strategy.


#### 5.1.1. Synthetic Dataset

A random probability function is used to fit users’ interactions in OSNs. The setting standards for the time interval of interactions between users and the weights of the interaction events are different for each OSN. We select the interaction data within the time interval (Φtl=0.367879) among users in the synthetic dataset. The number of interactions is set to 50; the weights of the interaction events take values in the range 1,20; and the interaction evaluation takes values in the range 0,1 as an example to verify the rationality of the trust calculations, that is, Wl∈1,20, Cl∈0,1, and n∈1,50. The trust between two users may exceed 1 and should be normalized.


#### 5.1.2. Facebook Dataset

In [36], the data from https://Facebook.com capture the friendships among users, which can be modeled as undirected graphs.


#### 5.1.3. Slashdot Dataset

In [37], Slashdot is a technology-related news website and a specific user community, where users can submit and edit news about the current main technology. In 2002, Slashdot launched the Slashdot Zoo function, which enables users to mark each other as friends or enemies. The network establishes links between two friends or enemies among Slashdot users. Therefore, the data in this dataset are directional. This article uses 2009 Slashdot data, and the Slashdot dataset is converted to an undirected graph to reflect users’ friendships. Regardless of the direction of the connection between two nodes in the network, an edge is created in the undirected graph for these two nodes.


#### 5.1.4. Gowalla Dataset

In [38], Gowalla is a location-based social networking site in which users share their location by signing in. The friendships collected from Gowalla are undirected. The complete dataset consists of 19, 591 nodes and 950, 327 edges. Due to data size limitations, this program selects only a portion of the data for testing.We list the main attributes of each dataset in Table4. The synthetic dataset is used to verify the rationality of the credibility calculations, and the remaining three datasets are used to verify the security of the proposed anticollusion attack strategy.Table 4
Social network dataset property.
DatasetSynthetic datasetFacebookSlashdotGowallaVertices10006373182168196591Edges8997817090948464582533Average degree—25.77312.2739.668


### 5.2. Strategy Analysis

#### 5.2.1. Collusion Attack Strategy Analysis

According to the collusion attack model in [3], the collusion attack model has different probabilities of success for collusion attacks on popular and unpopular nodes. The probability of a successful conspiracy attack is mainly related to four factors, such as the degree d of the query node, the number of friends k allowed to be displayed, the layer of the friend relationship tree, and the rank r of the query user among the friends in that layer.Given a user node of degreed, assume that the probability that one of his friends is ranked among the top k is k/d. Randomly choose the victim node N0 and one of his top k friends N0.i with degree d0.i; then, the probability that N0 is among the top k friends of N0.i is(8)kd0.i,d0.i>k,1,d0.i≤k.Simplify it asmink/d0.i,1.Assuming that the probability ofN0 becoming one of the top k friends of any of its friends is independent, the probability of N0 becoming a popular node is p. Then, p is denoted by(9)pN0=∏i=1kminkd0.i,1.IfN0 is an unpopular node, the probability of easily destroying the privacy of the target user’s friendships by direct query at the first level is(10)pAttackatlayer1=1−∏i=1kminkd0.i,1.The number of collusion attackers required is(11)NumAttackersforunpop=1+k.IfN0 is a popular node, according to the attack flow of compromising the privacy of popular nodes, a malicious attacker cannot directly make N0 reveal the k+1th friend by querying its first layer friends. Therefore, the collusion attackers make the target user N0’s first friend N0.1 occupied and thus compromise the target user’s friendship privacy by passively displaying it with probability:(12)pAttackthroughN0.1=1−∏i=1r0.1minkd0.1.i,1,where r0.1 is the ranking of N0 among the friends of N0.1.


#### 5.2.2. Anticollusion Attack Strategy Analysis

According to the analysis of the attack success probability of the collusion attack and the total number of malicious attackers required, the probability of successful attack is equation (10), and the number of collusion attackers required is k+1. The attack on popular nodes is more complicated. Generally, this attack cannot destroy the privacy of the target user’s friendships by querying the first friend only, and the probability of destroying the target user’s privacy by occupying the first friend N0.1 of the target user is equation (12), where the number of conspiracy attackers required is at least k+2.In the friendship protection strategy against collusion attacks, the querier first needs to obtain a high level of trust through long-term interaction with the target user, and second, the querier needs to query the friends through thet,n threshold function. On the one hand, the anticollusion attack strategy sets a fully trusted querier to help with the query when there are fewer than n queriers. On the other hand, it avoids the situation where all of the malicious queriers have a high trust value.In the worst case, the number of collusion attackers needed for unpopular nodes is only 2, which requires at least two queries, while the number of collusion attackers needed for popular nodes is 3, which requires at least three queries. When querying by thet,n threshold function, the worst case of the class A has nA−1 malicious attackers among the queriers. The subsequent security analysis will verify and analyze the security of the friendships privacy protection strategy with the worst-case number of malicious attackers against the collusion attack.


### 5.3. Performance Analysis

In this section, we analyze the rationality of the trust calculations and the security of the anticollusion attack strategy usingt,n threshold function access control.


#### 5.3.1. Credibility Calculation Rationality

In this article, we propose a trust measure based on the interaction behaviors between users. Considering the number of interactions between two users in a period of time, interaction evaluation, interaction event weight, and other factors, the direct trust degree is calculated by regulating the function. Based on the direct trust degree, the calculation methods of the recommended trust degree and comprehensive trust degree are derived. In this section, the rationality of the trust calculation method is verified by relevant experiments.As Figure4 shows, when the time period spanned by user interactions is 2, the time decay coefficient is approximately 0.135; while when the time period spanned by user interactions is 3, the time decay coefficient has dropped to less than 0.1. When the number of user interactions was 9, the ratio of the interaction number conditioning function (INCN) to the number of interactions (IN) was 0.105, while when the number of interactions was 10, the ratio of the interaction number conditioning function to the number of interactions was 0.095. The number of time decays and the ratio of the interaction number conditioning function to the number of interactions were too low to show the more obvious experimental data results. Therefore, the number of interactions between users selected for the experiment ranged from 1 to 9, and the time period spanned by user interactions was selected as 1 or 2.Figure 4
Schematic diagram of data selection.Based on random numbers, the values of direct trust and recommended trust are calculated by equations (1) and (2), respectively, and the value of the user’s comprehensive trust is calculated by equation (3). We selected 1000 sets of data to prove the correctness of the trust calculations. The results are shown in Figure 5.Figure 5
Trust values. (a) Direct trust. (b) Recommend trust. (c) Comprehensive trust.
(a)(b)(c)Figures5(a)–5(c) show that the results of the direct trust, recommend trust, and comprehensive trust calculations, respectively, are normally distributed. In addition, they are in line with realistic expectations.


#### 5.3.2. Security Analysis

To improve the security and usability of the friend search engine, we assume that OSN administrators can be fully trusted in regard to the friend search engine. When the number of requestors is less than the number of query requests, the administrators can help the requestors complete the query.In this work, we compare the proposed anticollusion strategy with the original collusion attack. The security of the proposed strategy is verified and analyzed in four aspects, such as limit rate, the number of victims, the number of collusion attackers, and the success rate of the collusion attack. It is assumed that the original conspiracy attacker uses a minimum number of malicious attackers and can compromise the privacy of the target user with a minimum number of queries, and the probability of success of its attack is1; i.e., the conspiracy attacker can successfully compromise the privacy of the target’s friendships in each query.Limit Rate (LR). The LR of the system is defined as the ratio of the number of users in category B to the number of all users, that is, the proportion of users who cannot successfully query in the friend search engine among all requestors. Based on equation (3) OTij=u⋅DTij+v⋅RTiju+v=1,u>v, where DTij, RTij∈0,1. The direct trust weight coefficient u is set to 0.6, and the trust threshold is set to 0.5, 0.6, 0.7, 0.8, and 0.9. A total of 1000 experiments are conducted to verify the LR of the proposed strategy.Figure6 shows the LR and trust threshold results of the strategy. The value of the direct trust weight coefficient u is 0.6. When the trust threshold is 0.5, the LR of the strategy is approximately 40%. When the trust threshold is 0.6, the LR increases to 80%. At 0.7, the LR increases to almost 100%. Therefore, when the trust threshold is 0.7, almost no user reaches the trust threshold, and the friend search engine will not allow any querying. When the trust threshold is 0.6, 80% of users in the OSN cannot reach the threshold. Thus, the number of requestors in the friend search engine is limited, and the safety of the friend search engine is increased.Number of Victims. Consider the trust threshold of 0.5 as an example. Sixty percent of users can make normal queries. In the worst case of the friend search engine query, the number of malicious requestors is not limited, and malicious requestors can destroy the privacy of the target user via a one-time collusion attack at the first layer. The probability of successfully destroying the user’s privacy is equation (10). The attack can destroy the privacy of 80% of the nodes in OSNs [3].Figure 6
Limit rate under the trust threshold withu = 0.6.In a one-time collusion attack, the maximum number of malicious requestors isnA−1, and the collusion attack performs at least two queries. Thus, the probability of one collusion attack that destroys the target user’s privacy at the first layer is(13)nA−1nA2⋅pAttackatlayer1.When the trust threshold is set to 0.5 (lowest threshold), 40% of users’ queries will be restricted. In this case, the anticollusion attack strategy can reduce the number of users whose privacy is breached by at least 47.9%. Accordingly, the number of users whose privacy is violated decreases. By comparing the Facebook, Gowalla, and Slashdot datasets, we obtain the results shown in Figure7.Figure 7
Comparison of the number of victims with a compromised strategy.Due to the limitation of the trust threshold, the number of users whose privacy is breached is significantly reduced. The number of users whose privacy is breached in the Facebook and Slashdot datasets is reduced by approximately 20, 000, while the number of users whose privacy is breached in the Gowalla dataset is reduced by approximately 60, 000. In the three datasets, the number of users whose privacy has been violated will be reduced by at least 40%. The proposed strategy greatly reduces the number of users whose privacy is violated, which improves the privacy security of users in OSNs.Number of Collusion Attackers. Based on the t,n threshold function, in the query process of the friend search engine, n inquirers are required to participate in the query, and at least t requestors are required to perform secret reconstruction. Therefore, in a single query process, to ensure that malicious requestors can successfully query, it is necessary to ensure that t requestors are malicious requestors and that the comprehensive trust is higher than the trust threshold. In the best situation, two malicious requestors can destroy the privacy of the target user by making two queries. The total number of attackers required is 2n, while in the comparison strategy, the number of inquirers required is only 2. Therefore, when the value of n set by the system is larger, more malicious attackers will be needed.Figure8 shows that the number of colluding attackers varies with the number of queries n. The number of attackers in the proposed strategy is twice that of the comparison strategy. Under the same conditions, the colluding attackers will need more entities or accounts to make queries with the proposed strategy.Probability of a Successful Collusion Attack. Assume that malicious requestors who have not interacted with the target user in the OSN want to query the target’s friendships. First, excellent long-term interactions with the target are needed to obtain the trust of the target. A successful collusion attack requires multiple malicious requestors to cooperate to coordinate their query order and target, and each malicious requestor can successfully query the friend list of the query target. Therefore, multiple malicious requestors need to maintain excellent interactions with users in the OSN, which will require colluding malicious requestors to spend a substantial amount of time disguising their intentions to obtain the trust of the target user.Figure 8
Number of collusion attackers.Consider the successful collusion attack process in Table2 as an example. The collusion attack was coordinated by four malicious requestors. MR1 makes the first requests, and MR2 determines the target to be queried based on the query results of MR1. MR3 queries based on the query result of MR2 Thus, user N0.2.2 will be “occupied,” and the new friend N0.2.3 of user N0.2 can be queried. MR4 makes a query based on the query result of MR3 and obtains the k+1th friend of N0, i.e., fourth friend N0.4. The privacy of the friendships of user N0 is destroyed.Undert,n threshold function access control, four malicious requestors, i.e., MR1, MR2, MR3, and MR4, want to complete this query. First, they need to obtain the high trust of the target nodes, i.e., N0, N0.2, N0.2.1, N0.2.2, and N0.2.3, and all four malicious requestors must have excellent long-term interactions with the target. If a malicious requestor cannot obtain the trust of the target, then Tij<Tt, and the previously described attack cannot be successfully carried out. Therefore, a successful malicious attack by colluding attackers requires that all malicious requestors reach the trust threshold.If malicious requestors already exist in the OSN and have interacted with the target user, this strategy restricts requestors whose trust level is below the trust threshold. A requestor cannot query the target user’s friend list undert,n threshold function access control. Therefore, when the trust threshold is 0.5, 40% of users who do not reach the trust threshold will not be able to query. As described in the second part of this section, for the collusion attack strategy in [3], if t,n threshold function access control is not adopted, the probability that colluding attackers will successfully destroy a user’s privacy is 1 for each query. In the t,n threshold secret sharing anticollusion attack strategy combined with trust, the comprehensive trust of the requestors who can successfully query the friendships of the target user must be higher than the trust threshold; that is, malicious requestors need to be in category A. Next, we take the trust threshold of 0.5 as an example to discuss the probability that colluding attackers will successfully destroy the privacy of a user’s friendships under t,n threshold function access control.If there is a collusion attack, the worst case is that there are enough colluding attackers, and the privacy of the target user is destroyed by just two queries. During a single query, the maximum number of malicious requestors isnA−1.For unpopular nodes, the maximum probability of malicious requestors who make two requests is(14)0.6nA−1·nA−1nA2.For popular nodes, the maximum probability of malicious requestors who make three requests is(15)0.6nA−1·nA−1nA3.In Facebook, Gowalla, and Slashdot, we observe that regardless of whether a popular node or an unpopular node is considered, the number of malicious requestors required to conduct a successful collusion attack can reach 10,000, which is the best case of a successful collusion attack in the three datasets. Therefore, as Figures9(a) and 9(b) show, in the case of nA≥2, when there are at most nA−1 malicious requestors, the probabilities of successful collusion attacks for unpopular nodes and popular nodes are p≤0.09 and p≤0.027, respectively.Figure 9
Comparison of the probabilities of a successful collusion attack based on the number of collusion attackers. (a) Unpopular nodes. (b) Popular nodes.
(a)(b)Figure9 shows that when the number of malicious requestors is 2, the anticollusion attack strategy based on t,n threshold secret sharing can reduce the probability of a successful collusion attack from 1 to 0.09 and the probability of a successful conspiracy attack on popular nodes from 1 to 0.027. When the number of malicious requestors increases to 18, the anticollusion attack strategy reduces the probability of a successful collusion attack to 0. When the system trust threshold is higher, it is more difficult for malicious requestors to conduct collusion attacks.Therefore, the trust-based SSS anticollusion attack strategy proposed in this work can substantially reduce the number of users whose privacy is compromised by means of credibility calculations, the trust threshold and thet,n threshold function. This strategy restricts user queries based on trust and uses the t,n threshold function of the SSS for access control. This strategy can also reduce the probability of successful collusion attacks, which has a significant effect on resisting collusion attacks and can protect the friendship privacy of users in OSNs.


## 5.1. Datasets

We generate random numbers that satisfy the previously described conditions of the credibility calculation method, including data on 1000 groups of user interactions, and verify the correctness of the trust calculations. In addition, we use three real-world social network datasets to verify the security of the anticollusion attack strategy.


### 5.1.1. Synthetic Dataset

A random probability function is used to fit users’ interactions in OSNs. The setting standards for the time interval of interactions between users and the weights of the interaction events are different for each OSN. We select the interaction data within the time interval (Φtl=0.367879) among users in the synthetic dataset. The number of interactions is set to 50; the weights of the interaction events take values in the range 1,20; and the interaction evaluation takes values in the range 0,1 as an example to verify the rationality of the trust calculations, that is, Wl∈1,20, Cl∈0,1, and n∈1,50. The trust between two users may exceed 1 and should be normalized.


### 5.1.2. Facebook Dataset

In [36], the data from https://Facebook.com capture the friendships among users, which can be modeled as undirected graphs.


### 5.1.3. Slashdot Dataset

In [37], Slashdot is a technology-related news website and a specific user community, where users can submit and edit news about the current main technology. In 2002, Slashdot launched the Slashdot Zoo function, which enables users to mark each other as friends or enemies. The network establishes links between two friends or enemies among Slashdot users. Therefore, the data in this dataset are directional. This article uses 2009 Slashdot data, and the Slashdot dataset is converted to an undirected graph to reflect users’ friendships. Regardless of the direction of the connection between two nodes in the network, an edge is created in the undirected graph for these two nodes.


### 5.1.4. Gowalla Dataset

In [38], Gowalla is a location-based social networking site in which users share their location by signing in. The friendships collected from Gowalla are undirected. The complete dataset consists of 19, 591 nodes and 950, 327 edges. Due to data size limitations, this program selects only a portion of the data for testing.We list the main attributes of each dataset in Table4. The synthetic dataset is used to verify the rationality of the credibility calculations, and the remaining three datasets are used to verify the security of the proposed anticollusion attack strategy.Table 4
Social network dataset property.
DatasetSynthetic datasetFacebookSlashdotGowallaVertices10006373182168196591Edges8997817090948464582533Average degree—25.77312.2739.668


## 5.1.1. Synthetic Dataset

A random probability function is used to fit users’ interactions in OSNs. The setting standards for the time interval of interactions between users and the weights of the interaction events are different for each OSN. We select the interaction data within the time interval (Φtl=0.367879) among users in the synthetic dataset. The number of interactions is set to 50; the weights of the interaction events take values in the range 1,20; and the interaction evaluation takes values in the range 0,1 as an example to verify the rationality of the trust calculations, that is, Wl∈1,20, Cl∈0,1, and n∈1,50. The trust between two users may exceed 1 and should be normalized.


## 5.1.2. Facebook Dataset

In [36], the data from https://Facebook.com capture the friendships among users, which can be modeled as undirected graphs.


## 5.1.3. Slashdot Dataset

In [37], Slashdot is a technology-related news website and a specific user community, where users can submit and edit news about the current main technology. In 2002, Slashdot launched the Slashdot Zoo function, which enables users to mark each other as friends or enemies. The network establishes links between two friends or enemies among Slashdot users. Therefore, the data in this dataset are directional. This article uses 2009 Slashdot data, and the Slashdot dataset is converted to an undirected graph to reflect users’ friendships. Regardless of the direction of the connection between two nodes in the network, an edge is created in the undirected graph for these two nodes.


## 5.1.4. Gowalla Dataset

In [38], Gowalla is a location-based social networking site in which users share their location by signing in. The friendships collected from Gowalla are undirected. The complete dataset consists of 19, 591 nodes and 950, 327 edges. Due to data size limitations, this program selects only a portion of the data for testing.We list the main attributes of each dataset in Table4. The synthetic dataset is used to verify the rationality of the credibility calculations, and the remaining three datasets are used to verify the security of the proposed anticollusion attack strategy.Table 4
Social network dataset property.
DatasetSynthetic datasetFacebookSlashdotGowallaVertices10006373182168196591Edges8997817090948464582533Average degree—25.77312.2739.668


## 5.2. Strategy Analysis

### 5.2.1. Collusion Attack Strategy Analysis

According to the collusion attack model in [3], the collusion attack model has different probabilities of success for collusion attacks on popular and unpopular nodes. The probability of a successful conspiracy attack is mainly related to four factors, such as the degree d of the query node, the number of friends k allowed to be displayed, the layer of the friend relationship tree, and the rank r of the query user among the friends in that layer.Given a user node of degreed, assume that the probability that one of his friends is ranked among the top k is k/d. Randomly choose the victim node N0 and one of his top k friends N0.i with degree d0.i; then, the probability that N0 is among the top k friends of N0.i is(8)kd0.i,d0.i>k,1,d0.i≤k.Simplify it asmink/d0.i,1.Assuming that the probability ofN0 becoming one of the top k friends of any of its friends is independent, the probability of N0 becoming a popular node is p. Then, p is denoted by(9)pN0=∏i=1kminkd0.i,1.IfN0 is an unpopular node, the probability of easily destroying the privacy of the target user’s friendships by direct query at the first level is(10)pAttackatlayer1=1−∏i=1kminkd0.i,1.The number of collusion attackers required is(11)NumAttackersforunpop=1+k.IfN0 is a popular node, according to the attack flow of compromising the privacy of popular nodes, a malicious attacker cannot directly make N0 reveal the k+1th friend by querying its first layer friends. Therefore, the collusion attackers make the target user N0’s first friend N0.1 occupied and thus compromise the target user’s friendship privacy by passively displaying it with probability:(12)pAttackthroughN0.1=1−∏i=1r0.1minkd0.1.i,1,where r0.1 is the ranking of N0 among the friends of N0.1.


### 5.2.2. Anticollusion Attack Strategy Analysis

According to the analysis of the attack success probability of the collusion attack and the total number of malicious attackers required, the probability of successful attack is equation (10), and the number of collusion attackers required is k+1. The attack on popular nodes is more complicated. Generally, this attack cannot destroy the privacy of the target user’s friendships by querying the first friend only, and the probability of destroying the target user’s privacy by occupying the first friend N0.1 of the target user is equation (12), where the number of conspiracy attackers required is at least k+2.In the friendship protection strategy against collusion attacks, the querier first needs to obtain a high level of trust through long-term interaction with the target user, and second, the querier needs to query the friends through thet,n threshold function. On the one hand, the anticollusion attack strategy sets a fully trusted querier to help with the query when there are fewer than n queriers. On the other hand, it avoids the situation where all of the malicious queriers have a high trust value.In the worst case, the number of collusion attackers needed for unpopular nodes is only 2, which requires at least two queries, while the number of collusion attackers needed for popular nodes is 3, which requires at least three queries. When querying by thet,n threshold function, the worst case of the class A has nA−1 malicious attackers among the queriers. The subsequent security analysis will verify and analyze the security of the friendships privacy protection strategy with the worst-case number of malicious attackers against the collusion attack.


## 5.2.1. Collusion Attack Strategy Analysis

According to the collusion attack model in [3], the collusion attack model has different probabilities of success for collusion attacks on popular and unpopular nodes. The probability of a successful conspiracy attack is mainly related to four factors, such as the degree d of the query node, the number of friends k allowed to be displayed, the layer of the friend relationship tree, and the rank r of the query user among the friends in that layer.Given a user node of degreed, assume that the probability that one of his friends is ranked among the top k is k/d. Randomly choose the victim node N0 and one of his top k friends N0.i with degree d0.i; then, the probability that N0 is among the top k friends of N0.i is(8)kd0.i,d0.i>k,1,d0.i≤k.Simplify it asmink/d0.i,1.Assuming that the probability ofN0 becoming one of the top k friends of any of its friends is independent, the probability of N0 becoming a popular node is p. Then, p is denoted by(9)pN0=∏i=1kminkd0.i,1.IfN0 is an unpopular node, the probability of easily destroying the privacy of the target user’s friendships by direct query at the first level is(10)pAttackatlayer1=1−∏i=1kminkd0.i,1.The number of collusion attackers required is(11)NumAttackersforunpop=1+k.IfN0 is a popular node, according to the attack flow of compromising the privacy of popular nodes, a malicious attacker cannot directly make N0 reveal the k+1th friend by querying its first layer friends. Therefore, the collusion attackers make the target user N0’s first friend N0.1 occupied and thus compromise the target user’s friendship privacy by passively displaying it with probability:(12)pAttackthroughN0.1=1−∏i=1r0.1minkd0.1.i,1,where r0.1 is the ranking of N0 among the friends of N0.1.


## 5.2.2. Anticollusion Attack Strategy Analysis

According to the analysis of the attack success probability of the collusion attack and the total number of malicious attackers required, the probability of successful attack is equation (10), and the number of collusion attackers required is k+1. The attack on popular nodes is more complicated. Generally, this attack cannot destroy the privacy of the target user’s friendships by querying the first friend only, and the probability of destroying the target user’s privacy by occupying the first friend N0.1 of the target user is equation (12), where the number of conspiracy attackers required is at least k+2.In the friendship protection strategy against collusion attacks, the querier first needs to obtain a high level of trust through long-term interaction with the target user, and second, the querier needs to query the friends through thet,n threshold function. On the one hand, the anticollusion attack strategy sets a fully trusted querier to help with the query when there are fewer than n queriers. On the other hand, it avoids the situation where all of the malicious queriers have a high trust value.In the worst case, the number of collusion attackers needed for unpopular nodes is only 2, which requires at least two queries, while the number of collusion attackers needed for popular nodes is 3, which requires at least three queries. When querying by thet,n threshold function, the worst case of the class A has nA−1 malicious attackers among the queriers. The subsequent security analysis will verify and analyze the security of the friendships privacy protection strategy with the worst-case number of malicious attackers against the collusion attack.


## 5.3. Performance Analysis

In this section, we analyze the rationality of the trust calculations and the security of the anticollusion attack strategy usingt,n threshold function access control.


### 5.3.1. Credibility Calculation Rationality

In this article, we propose a trust measure based on the interaction behaviors between users. Considering the number of interactions between two users in a period of time, interaction evaluation, interaction event weight, and other factors, the direct trust degree is calculated by regulating the function. Based on the direct trust degree, the calculation methods of the recommended trust degree and comprehensive trust degree are derived. In this section, the rationality of the trust calculation method is verified by relevant experiments.As Figure4 shows, when the time period spanned by user interactions is 2, the time decay coefficient is approximately 0.135; while when the time period spanned by user interactions is 3, the time decay coefficient has dropped to less than 0.1. When the number of user interactions was 9, the ratio of the interaction number conditioning function (INCN) to the number of interactions (IN) was 0.105, while when the number of interactions was 10, the ratio of the interaction number conditioning function to the number of interactions was 0.095. The number of time decays and the ratio of the interaction number conditioning function to the number of interactions were too low to show the more obvious experimental data results. Therefore, the number of interactions between users selected for the experiment ranged from 1 to 9, and the time period spanned by user interactions was selected as 1 or 2.Figure 4
Schematic diagram of data selection.Based on random numbers, the values of direct trust and recommended trust are calculated by equations (1) and (2), respectively, and the value of the user’s comprehensive trust is calculated by equation (3). We selected 1000 sets of data to prove the correctness of the trust calculations. The results are shown in Figure 5.Figure 5
Trust values. (a) Direct trust. (b) Recommend trust. (c) Comprehensive trust.
(a)(b)(c)Figures5(a)–5(c) show that the results of the direct trust, recommend trust, and comprehensive trust calculations, respectively, are normally distributed. In addition, they are in line with realistic expectations.


### 5.3.2. Security Analysis

To improve the security and usability of the friend search engine, we assume that OSN administrators can be fully trusted in regard to the friend search engine. When the number of requestors is less than the number of query requests, the administrators can help the requestors complete the query.In this work, we compare the proposed anticollusion strategy with the original collusion attack. The security of the proposed strategy is verified and analyzed in four aspects, such as limit rate, the number of victims, the number of collusion attackers, and the success rate of the collusion attack. It is assumed that the original conspiracy attacker uses a minimum number of malicious attackers and can compromise the privacy of the target user with a minimum number of queries, and the probability of success of its attack is1; i.e., the conspiracy attacker can successfully compromise the privacy of the target’s friendships in each query.Limit Rate (LR). The LR of the system is defined as the ratio of the number of users in category B to the number of all users, that is, the proportion of users who cannot successfully query in the friend search engine among all requestors. Based on equation (3) OTij=u⋅DTij+v⋅RTiju+v=1,u>v, where DTij, RTij∈0,1. The direct trust weight coefficient u is set to 0.6, and the trust threshold is set to 0.5, 0.6, 0.7, 0.8, and 0.9. A total of 1000 experiments are conducted to verify the LR of the proposed strategy.Figure6 shows the LR and trust threshold results of the strategy. The value of the direct trust weight coefficient u is 0.6. When the trust threshold is 0.5, the LR of the strategy is approximately 40%. When the trust threshold is 0.6, the LR increases to 80%. At 0.7, the LR increases to almost 100%. Therefore, when the trust threshold is 0.7, almost no user reaches the trust threshold, and the friend search engine will not allow any querying. When the trust threshold is 0.6, 80% of users in the OSN cannot reach the threshold. Thus, the number of requestors in the friend search engine is limited, and the safety of the friend search engine is increased.Number of Victims. Consider the trust threshold of 0.5 as an example. Sixty percent of users can make normal queries. In the worst case of the friend search engine query, the number of malicious requestors is not limited, and malicious requestors can destroy the privacy of the target user via a one-time collusion attack at the first layer. The probability of successfully destroying the user’s privacy is equation (10). The attack can destroy the privacy of 80% of the nodes in OSNs [3].Figure 6
Limit rate under the trust threshold withu = 0.6.In a one-time collusion attack, the maximum number of malicious requestors isnA−1, and the collusion attack performs at least two queries. Thus, the probability of one collusion attack that destroys the target user’s privacy at the first layer is(13)nA−1nA2⋅pAttackatlayer1.When the trust threshold is set to 0.5 (lowest threshold), 40% of users’ queries will be restricted. In this case, the anticollusion attack strategy can reduce the number of users whose privacy is breached by at least 47.9%. Accordingly, the number of users whose privacy is violated decreases. By comparing the Facebook, Gowalla, and Slashdot datasets, we obtain the results shown in Figure7.Figure 7
Comparison of the number of victims with a compromised strategy.Due to the limitation of the trust threshold, the number of users whose privacy is breached is significantly reduced. The number of users whose privacy is breached in the Facebook and Slashdot datasets is reduced by approximately 20, 000, while the number of users whose privacy is breached in the Gowalla dataset is reduced by approximately 60, 000. In the three datasets, the number of users whose privacy has been violated will be reduced by at least 40%. The proposed strategy greatly reduces the number of users whose privacy is violated, which improves the privacy security of users in OSNs.Number of Collusion Attackers. Based on the t,n threshold function, in the query process of the friend search engine, n inquirers are required to participate in the query, and at least t requestors are required to perform secret reconstruction. Therefore, in a single query process, to ensure that malicious requestors can successfully query, it is necessary to ensure that t requestors are malicious requestors and that the comprehensive trust is higher than the trust threshold. In the best situation, two malicious requestors can destroy the privacy of the target user by making two queries. The total number of attackers required is 2n, while in the comparison strategy, the number of inquirers required is only 2. Therefore, when the value of n set by the system is larger, more malicious attackers will be needed.Figure8 shows that the number of colluding attackers varies with the number of queries n. The number of attackers in the proposed strategy is twice that of the comparison strategy. Under the same conditions, the colluding attackers will need more entities or accounts to make queries with the proposed strategy.Probability of a Successful Collusion Attack. Assume that malicious requestors who have not interacted with the target user in the OSN want to query the target’s friendships. First, excellent long-term interactions with the target are needed to obtain the trust of the target. A successful collusion attack requires multiple malicious requestors to cooperate to coordinate their query order and target, and each malicious requestor can successfully query the friend list of the query target. Therefore, multiple malicious requestors need to maintain excellent interactions with users in the OSN, which will require colluding malicious requestors to spend a substantial amount of time disguising their intentions to obtain the trust of the target user.Figure 8
Number of collusion attackers.Consider the successful collusion attack process in Table2 as an example. The collusion attack was coordinated by four malicious requestors. MR1 makes the first requests, and MR2 determines the target to be queried based on the query results of MR1. MR3 queries based on the query result of MR2 Thus, user N0.2.2 will be “occupied,” and the new friend N0.2.3 of user N0.2 can be queried. MR4 makes a query based on the query result of MR3 and obtains the k+1th friend of N0, i.e., fourth friend N0.4. The privacy of the friendships of user N0 is destroyed.Undert,n threshold function access control, four malicious requestors, i.e., MR1, MR2, MR3, and MR4, want to complete this query. First, they need to obtain the high trust of the target nodes, i.e., N0, N0.2, N0.2.1, N0.2.2, and N0.2.3, and all four malicious requestors must have excellent long-term interactions with the target. If a malicious requestor cannot obtain the trust of the target, then Tij<Tt, and the previously described attack cannot be successfully carried out. Therefore, a successful malicious attack by colluding attackers requires that all malicious requestors reach the trust threshold.If malicious requestors already exist in the OSN and have interacted with the target user, this strategy restricts requestors whose trust level is below the trust threshold. A requestor cannot query the target user’s friend list undert,n threshold function access control. Therefore, when the trust threshold is 0.5, 40% of users who do not reach the trust threshold will not be able to query. As described in the second part of this section, for the collusion attack strategy in [3], if t,n threshold function access control is not adopted, the probability that colluding attackers will successfully destroy a user’s privacy is 1 for each query. In the t,n threshold secret sharing anticollusion attack strategy combined with trust, the comprehensive trust of the requestors who can successfully query the friendships of the target user must be higher than the trust threshold; that is, malicious requestors need to be in category A. Next, we take the trust threshold of 0.5 as an example to discuss the probability that colluding attackers will successfully destroy the privacy of a user’s friendships under t,n threshold function access control.If there is a collusion attack, the worst case is that there are enough colluding attackers, and the privacy of the target user is destroyed by just two queries. During a single query, the maximum number of malicious requestors isnA−1.For unpopular nodes, the maximum probability of malicious requestors who make two requests is(14)0.6nA−1·nA−1nA2.For popular nodes, the maximum probability of malicious requestors who make three requests is(15)0.6nA−1·nA−1nA3.In Facebook, Gowalla, and Slashdot, we observe that regardless of whether a popular node or an unpopular node is considered, the number of malicious requestors required to conduct a successful collusion attack can reach 10,000, which is the best case of a successful collusion attack in the three datasets. Therefore, as Figures9(a) and 9(b) show, in the case of nA≥2, when there are at most nA−1 malicious requestors, the probabilities of successful collusion attacks for unpopular nodes and popular nodes are p≤0.09 and p≤0.027, respectively.Figure 9
Comparison of the probabilities of a successful collusion attack based on the number of collusion attackers. (a) Unpopular nodes. (b) Popular nodes.
(a)(b)Figure9 shows that when the number of malicious requestors is 2, the anticollusion attack strategy based on t,n threshold secret sharing can reduce the probability of a successful collusion attack from 1 to 0.09 and the probability of a successful conspiracy attack on popular nodes from 1 to 0.027. When the number of malicious requestors increases to 18, the anticollusion attack strategy reduces the probability of a successful collusion attack to 0. When the system trust threshold is higher, it is more difficult for malicious requestors to conduct collusion attacks.Therefore, the trust-based SSS anticollusion attack strategy proposed in this work can substantially reduce the number of users whose privacy is compromised by means of credibility calculations, the trust threshold and thet,n threshold function. This strategy restricts user queries based on trust and uses the t,n threshold function of the SSS for access control. This strategy can also reduce the probability of successful collusion attacks, which has a significant effect on resisting collusion attacks and can protect the friendship privacy of users in OSNs.


## 5.3.1. Credibility Calculation Rationality

In this article, we propose a trust measure based on the interaction behaviors between users. Considering the number of interactions between two users in a period of time, interaction evaluation, interaction event weight, and other factors, the direct trust degree is calculated by regulating the function. Based on the direct trust degree, the calculation methods of the recommended trust degree and comprehensive trust degree are derived. In this section, the rationality of the trust calculation method is verified by relevant experiments.As Figure4 shows, when the time period spanned by user interactions is 2, the time decay coefficient is approximately 0.135; while when the time period spanned by user interactions is 3, the time decay coefficient has dropped to less than 0.1. When the number of user interactions was 9, the ratio of the interaction number conditioning function (INCN) to the number of interactions (IN) was 0.105, while when the number of interactions was 10, the ratio of the interaction number conditioning function to the number of interactions was 0.095. The number of time decays and the ratio of the interaction number conditioning function to the number of interactions were too low to show the more obvious experimental data results. Therefore, the number of interactions between users selected for the experiment ranged from 1 to 9, and the time period spanned by user interactions was selected as 1 or 2.Figure 4
Schematic diagram of data selection.Based on random numbers, the values of direct trust and recommended trust are calculated by equations (1) and (2), respectively, and the value of the user’s comprehensive trust is calculated by equation (3). We selected 1000 sets of data to prove the correctness of the trust calculations. The results are shown in Figure 5.Figure 5
Trust values. (a) Direct trust. (b) Recommend trust. (c) Comprehensive trust.
(a)(b)(c)Figures5(a)–5(c) show that the results of the direct trust, recommend trust, and comprehensive trust calculations, respectively, are normally distributed. In addition, they are in line with realistic expectations.


## 5.3.2. Security Analysis

To improve the security and usability of the friend search engine, we assume that OSN administrators can be fully trusted in regard to the friend search engine. When the number of requestors is less than the number of query requests, the administrators can help the requestors complete the query.In this work, we compare the proposed anticollusion strategy with the original collusion attack. The security of the proposed strategy is verified and analyzed in four aspects, such as limit rate, the number of victims, the number of collusion attackers, and the success rate of the collusion attack. It is assumed that the original conspiracy attacker uses a minimum number of malicious attackers and can compromise the privacy of the target user with a minimum number of queries, and the probability of success of its attack is1; i.e., the conspiracy attacker can successfully compromise the privacy of the target’s friendships in each query.Limit Rate (LR). The LR of the system is defined as the ratio of the number of users in category B to the number of all users, that is, the proportion of users who cannot successfully query in the friend search engine among all requestors. Based on equation (3) OTij=u⋅DTij+v⋅RTiju+v=1,u>v, where DTij, RTij∈0,1. The direct trust weight coefficient u is set to 0.6, and the trust threshold is set to 0.5, 0.6, 0.7, 0.8, and 0.9. A total of 1000 experiments are conducted to verify the LR of the proposed strategy.Figure6 shows the LR and trust threshold results of the strategy. The value of the direct trust weight coefficient u is 0.6. When the trust threshold is 0.5, the LR of the strategy is approximately 40%. When the trust threshold is 0.6, the LR increases to 80%. At 0.7, the LR increases to almost 100%. Therefore, when the trust threshold is 0.7, almost no user reaches the trust threshold, and the friend search engine will not allow any querying. When the trust threshold is 0.6, 80% of users in the OSN cannot reach the threshold. Thus, the number of requestors in the friend search engine is limited, and the safety of the friend search engine is increased.Number of Victims. Consider the trust threshold of 0.5 as an example. Sixty percent of users can make normal queries. In the worst case of the friend search engine query, the number of malicious requestors is not limited, and malicious requestors can destroy the privacy of the target user via a one-time collusion attack at the first layer. The probability of successfully destroying the user’s privacy is equation (10). The attack can destroy the privacy of 80% of the nodes in OSNs [3].Figure 6
Limit rate under the trust threshold withu = 0.6.In a one-time collusion attack, the maximum number of malicious requestors isnA−1, and the collusion attack performs at least two queries. Thus, the probability of one collusion attack that destroys the target user’s privacy at the first layer is(13)nA−1nA2⋅pAttackatlayer1.When the trust threshold is set to 0.5 (lowest threshold), 40% of users’ queries will be restricted. In this case, the anticollusion attack strategy can reduce the number of users whose privacy is breached by at least 47.9%. Accordingly, the number of users whose privacy is violated decreases. By comparing the Facebook, Gowalla, and Slashdot datasets, we obtain the results shown in Figure7.Figure 7
Comparison of the number of victims with a compromised strategy.Due to the limitation of the trust threshold, the number of users whose privacy is breached is significantly reduced. The number of users whose privacy is breached in the Facebook and Slashdot datasets is reduced by approximately 20, 000, while the number of users whose privacy is breached in the Gowalla dataset is reduced by approximately 60, 000. In the three datasets, the number of users whose privacy has been violated will be reduced by at least 40%. The proposed strategy greatly reduces the number of users whose privacy is violated, which improves the privacy security of users in OSNs.Number of Collusion Attackers. Based on the t,n threshold function, in the query process of the friend search engine, n inquirers are required to participate in the query, and at least t requestors are required to perform secret reconstruction. Therefore, in a single query process, to ensure that malicious requestors can successfully query, it is necessary to ensure that t requestors are malicious requestors and that the comprehensive trust is higher than the trust threshold. In the best situation, two malicious requestors can destroy the privacy of the target user by making two queries. The total number of attackers required is 2n, while in the comparison strategy, the number of inquirers required is only 2. Therefore, when the value of n set by the system is larger, more malicious attackers will be needed.Figure8 shows that the number of colluding attackers varies with the number of queries n. The number of attackers in the proposed strategy is twice that of the comparison strategy. Under the same conditions, the colluding attackers will need more entities or accounts to make queries with the proposed strategy.Probability of a Successful Collusion Attack. Assume that malicious requestors who have not interacted with the target user in the OSN want to query the target’s friendships. First, excellent long-term interactions with the target are needed to obtain the trust of the target. A successful collusion attack requires multiple malicious requestors to cooperate to coordinate their query order and target, and each malicious requestor can successfully query the friend list of the query target. Therefore, multiple malicious requestors need to maintain excellent interactions with users in the OSN, which will require colluding malicious requestors to spend a substantial amount of time disguising their intentions to obtain the trust of the target user.Figure 8
Number of collusion attackers.Consider the successful collusion attack process in Table2 as an example. The collusion attack was coordinated by four malicious requestors. MR1 makes the first requests, and MR2 determines the target to be queried based on the query results of MR1. MR3 queries based on the query result of MR2 Thus, user N0.2.2 will be “occupied,” and the new friend N0.2.3 of user N0.2 can be queried. MR4 makes a query based on the query result of MR3 and obtains the k+1th friend of N0, i.e., fourth friend N0.4. The privacy of the friendships of user N0 is destroyed.Undert,n threshold function access control, four malicious requestors, i.e., MR1, MR2, MR3, and MR4, want to complete this query. First, they need to obtain the high trust of the target nodes, i.e., N0, N0.2, N0.2.1, N0.2.2, and N0.2.3, and all four malicious requestors must have excellent long-term interactions with the target. If a malicious requestor cannot obtain the trust of the target, then Tij<Tt, and the previously described attack cannot be successfully carried out. Therefore, a successful malicious attack by colluding attackers requires that all malicious requestors reach the trust threshold.If malicious requestors already exist in the OSN and have interacted with the target user, this strategy restricts requestors whose trust level is below the trust threshold. A requestor cannot query the target user’s friend list undert,n threshold function access control. Therefore, when the trust threshold is 0.5, 40% of users who do not reach the trust threshold will not be able to query. As described in the second part of this section, for the collusion attack strategy in [3], if t,n threshold function access control is not adopted, the probability that colluding attackers will successfully destroy a user’s privacy is 1 for each query. In the t,n threshold secret sharing anticollusion attack strategy combined with trust, the comprehensive trust of the requestors who can successfully query the friendships of the target user must be higher than the trust threshold; that is, malicious requestors need to be in category A. Next, we take the trust threshold of 0.5 as an example to discuss the probability that colluding attackers will successfully destroy the privacy of a user’s friendships under t,n threshold function access control.If there is a collusion attack, the worst case is that there are enough colluding attackers, and the privacy of the target user is destroyed by just two queries. During a single query, the maximum number of malicious requestors isnA−1.For unpopular nodes, the maximum probability of malicious requestors who make two requests is(14)0.6nA−1·nA−1nA2.For popular nodes, the maximum probability of malicious requestors who make three requests is(15)0.6nA−1·nA−1nA3.In Facebook, Gowalla, and Slashdot, we observe that regardless of whether a popular node or an unpopular node is considered, the number of malicious requestors required to conduct a successful collusion attack can reach 10,000, which is the best case of a successful collusion attack in the three datasets. Therefore, as Figures9(a) and 9(b) show, in the case of nA≥2, when there are at most nA−1 malicious requestors, the probabilities of successful collusion attacks for unpopular nodes and popular nodes are p≤0.09 and p≤0.027, respectively.Figure 9
Comparison of the probabilities of a successful collusion attack based on the number of collusion attackers. (a) Unpopular nodes. (b) Popular nodes.
(a)(b)Figure9 shows that when the number of malicious requestors is 2, the anticollusion attack strategy based on t,n threshold secret sharing can reduce the probability of a successful collusion attack from 1 to 0.09 and the probability of a successful conspiracy attack on popular nodes from 1 to 0.027. When the number of malicious requestors increases to 18, the anticollusion attack strategy reduces the probability of a successful collusion attack to 0. When the system trust threshold is higher, it is more difficult for malicious requestors to conduct collusion attacks.Therefore, the trust-based SSS anticollusion attack strategy proposed in this work can substantially reduce the number of users whose privacy is compromised by means of credibility calculations, the trust threshold and thet,n threshold function. This strategy restricts user queries based on trust and uses the t,n threshold function of the SSS for access control. This strategy can also reduce the probability of successful collusion attacks, which has a significant effect on resisting collusion attacks and can protect the friendship privacy of users in OSNs.


## 6. Conclusion

To address the problem of collusion attacks that compromise users’ friendship privacy, we propose an anticollusion attack strategy that combines the trust metric andt,n threshold function. The trust metric is based on the interaction behaviors between users, and the calculation methods of direct trust, recommendation trust, and comprehensive trust are determined by considering the number of interactions, interaction time, interaction evaluation, and event weight. Meanwhile, by converting friendships into secrets and using the t,n threshold function to share and reconstruct the secrets, the conspiracy queries of malicious attackers are effectively restricted. The experimental results show that the proposed strategy can significantly reduce the probability of successful conspiracy attacks, reduce the number of victims, and protect the privacy of users’ friendships while ensuring normal user queries.Theoretically, this work simplifies the complex privacy protection of a user’s friendships to the user’s access control strategy in the friend search engine. This research starts by theoretically analyzing the calculation of trust between two users and applies thet,n threshold function to control querying in the friend search engine to protect the privacy of the user’s friendships.Overall, the proposed strategy can successfully decrease the probability of collusion attacks in friend search engines. Specifically, attacking the same number of users requires more attackers, and the number of users who violate the same number of attackers is greatly reduced.



---

*Source: 9717747-2021-07-05.xml*