J Guo

A Marshall
email: amarshall@qub.ac.uk

B Zhou
email: b.zhou@qub.ac.uk

A Trust Management Framework for Detecting Malicious and Selfish Behaviour in Ad-Hoc Wireless Networks using Fuzzy Sets and Grey theory

Keywords: trust management framework, Fuzzy Set, Grey theory, wireless networks

As wireless network applications evolve, they require interaction between many entities (protocols, middleware etc), and an increasing requirement for the design of secure applications among the entities is trust management. Consequently, many new attacks against networks are aimed at the trust management. In this paper, we develop a new trust management framework (TMF) for wireless networks. The proposed framework applies Grey theory combined with Fuzzy Sets to calculate a node's trust value based on observations from neighbour nodes'. The new TMF employs multiple rather than a single parameter to decide the resulting trust value. Simulations conducted in an 802.11 based wireless network show that the new framework can not only identify abnormal trust behaviour, but can also effectively find which aspect of the metrics used to establish the trust value for a node are abnormal, and hence identify the strategy the attacker is using against the TMF.

Introduction

Wireless network technologies have greatly changed our daily lives by offering access to the Internet anywhere and anytime. However attacks and intrusions against wireless networks, Internet fraud and high-tech crimes have kept raising in recent years, and security has become a major concern for those who intend to use wireless technologies and Internet services. Substantial resources have been deployed to tackle this issue; firewalls, anti-virus software, encryption algorithms, and intrusion detection and prevention systems are examples of the tools to secure network applications. A networked application involves interactions among many entities, such as networking protocols from physical layer to application layer, middleware, various algorithms, etc. An essential challenge when designing a secure application is therefore to determine how one network entity can trust another network entity. In today's business communications systems, trust plays an important role in virtual organizations, where it is used to counter uncertainty caused by the business requirement for openness. The requirement seeks to make marketable services openly available to all potential, highly autonomous clients, which increases a service provider's vulnerability to an attack [START_REF] Li | Future Trust Management Framework for Mobile Ad Hoc Networks[END_REF]. Especially in distributed environments, trust management can provide a basis for more detailed and better-informed authorization decisions, while allowing for a high level of automation. Researchers want to design trust management systems in order to establish trust relationships, dynamically monitor, and adjust any existing trust relationships [START_REF] Li | Future Trust Management Framework for Mobile Ad Hoc Networks[END_REF] [START_REF] Hu | Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks[END_REF].

In recent years, various models and algorithms for describing trust and designing trust management in distributed systems or wireless networks have been considered, such as policy language, public-key cryptography, the resurrecting duckling model, and the distributed trust model [START_REF] Li | Future Trust Management Framework for Mobile Ad Hoc Networks[END_REF][2][3] [START_REF] Lindsay Sun | Information Theoretic Framework of Trust Modelling and Evaluation for Ad Hoc Networks[END_REF]. The distributed trust models are usually applied in peer-to-peer (P2P) systems and wireless ad hoc Networks; these networks rely on all participants actively contributing to network activities such as routing and packet forwarding. The particular characteristics of a wireless network's nodes, such as limited memory, battery power, and bandwidth, can provide incentives for them to act selfishly (refuse to participate in routing and provide services to other nodes, for example). Trust management can help mitigate nodes' selfish behaviors and advantage the efficient utilization of network resources. Recent research has considered how to evaluate the trust of communication entities in wireless networks, and various theories such as Probabilistic Estimation [START_REF] Li | Future Trust Management Framework for Mobile Ad Hoc Networks[END_REF], Information Theory [START_REF] Lindsay Sun | Information Theoretic Framework of Trust Modelling and Evaluation for Ad Hoc Networks[END_REF], Fuzzy theory, and Game theory have been used for designing the trust metrics [START_REF] Anh | A Game-Theoretic Analysis of Trust Management in P2P Systems[END_REF] [START_REF] Zhiwei Qin | Fuzzy Dynamic Programming based Trusted Routing Decision in Mobile Ad Hoc Networks, Embedded Computing[END_REF]. For evaluating trust values from more aspects, some researchers introduce Grey theory to improve existing trust management or network performance [START_REF] Julong | Introduction to Grey Theory[END_REF][8][9] [START_REF] Song | Network Selection in An Integrated Wireless LAN and UMTS Environment Using Mathematical Modeling and Computing Techniques[END_REF].

In this article, we focus on designing a new trust management framework which uses algorithms based on Fuzzy Sets and Grey theory. Grey theory has been widely applied in many fields like economics, agriculture, aerographs, the environment and materials. In [START_REF] Julong | Introduction to Grey Theory[END_REF][9], Deng Julong proposed the grey relational analysis method to make a quantitative analysis of the dynamic development process of systems. The basic idea of Grey theory is to determine the relationship of different factors according to the degree of similarity between curves. The research presented here takes the idea of Grey theory in order to rank trust values. A major advantage of this method is that it does not require a high quantity of sample data. Moreover, it does not require the data to be consistent with any kind of distribution rule in order to produce very convincing results, which are consistent with qualitative analysis. In [START_REF] Cai | Grey Theory Based Nodes Risk Assessment in P2P Networks[END_REF], Fu Cal et al applied an improved traditional analysis method to the problems mentioned above. This method can effectively deal with data that has multiple attributes, while obtaining grey relational grades that can be compared with each other, no matter what the units of the original data are [START_REF] Cai | Grey Theory Based Nodes Risk Assessment in P2P Networks[END_REF]. It can therefore be considered a feasible method for risk assessment of peer nodes in P2P networks and wireless ad-hoc networks.

The rest of this article is organized as follows: first, the classification of trust relationships is introduced, then the application of Grey theory to the design of a new trust management framework is described. Several simulation cases are then described that use the proposed algorithms and their performance examined. Conclusions and further research are then detailed.

Trust relationships

Current trust management research in wireless networks, usually views the neighbourhood from three levels [

A new Trust Management Framework for Wireless Networks using Fuzzy Set and Grey Theory

This section presents a TMF for a pure mobile ad hoc network environment, using Grey Theory. The TMF is designed to be robust against attacks that are aimed to deceive the trust relationships, such as Selective Misbehaviour attack, On-off attack, Conflicting attack, and Bad Mouthing attack [1][11]. In wireless ad-hoc and mesh, the links between communicating nodes can be one-hop, and multi-hop, only singlehop links are considered in this paper.

The framework

For a node in a distributed environment, such as in a wireless ad hoc network, the trust management of the network views the node as an agent for obtaining the trust information. The functional blocks of the framework are shown in Figure 1.

In Figure 1, the nodes in the TMF firstly collect the input information for subsequent computation of trust. Many existing trust models for distributed environments choose the probability of successful interactions, which is generally viewed as corresponding to the packet loss rate, as the main parameter in calculation of the trust value. However, in fact the probability of one node cooperating with other nodes is influenced not only by the packet loss rate, but also signal strength, data rate, and other physical factors that are not considered in current trust models.

For example, an attacker/selfish node may make use of the knowledge that the packet loss rate is the main parameter used in trust calculation. Due to this limitation, the attacker can obtain a very high trust value by just interacting with close neighbours, while dropping or abandoning communications with nodes far away. In comparison, normal behaving nodes will communicate with all neighbours (near and far). However when a normal node interacts with a far away neighbour, the packet loss rate may be higher than that of the attacker which communicates only with near neighbours. Thus, if only the packet loss rate is used as the deciding parameter, it will lead to a normal node's trust value being lower than the attacker's who intends to choose partners. This leads to the conclusion that any TMF should consider multiple parameters, including those involved in the communications processes in order to avoid such duplicity.

Input Output

Observation;

Input parameters

Weight vector for indexes

Trust value

Node weight

Total trust value

Relationship weight

Total trust value

Input parameters Whitenization Figure 1 -functional blocks of the TMF The input parameters include: packet loss rate, signal strength, data rate, end-toend delay, and throughput. These parameters are chosen as the basic minimum set of parameters required to cover all types of attacks against lower level protocols as they can easily be obtained from MAC, data link and network layer protocols.

Using Grey Theory

For multiple input parameters, we can use Grey Theory to proceed and calculate trust value. From Grey theory, let X be a grey relational set which is used as the evaluation index set,

              ...(1) (0,1)  
is the distinguishing coefficient [START_REF] Cai | Grey Theory Based Nodes Risk Assessment in P2P Networks[END_REF]. Also we define the worst reference sequence 1) and (2), when normally setting ρ=1/2, the value area of a grey relational coefficient is from 0.33 to 1. In order to make the grey relational coefficient to be in [0, 1], it can convert the values by using the mapping y=1.5x-0.5 (x is the grey relational coefficient).

B t =( b 1 t ,…, b m t ),
              ...(2) (0,1)   is distinguishing coefficient. From (
We define the index set X's weight vector H={h 1 ,…, h m }, ∑h j =1. At period t, node k's Grey Relational Grades with best and worst reference sequence are ,, ,

t t t t k j k j k j k j jj hh      
, respectively.

Then, by using the least-square methods [START_REF] Hong | Grey theory based reputation system for Secure Neighbor Discovery in Wireless Ad Hoc Networks[END_REF], we can obtain the integrated expected value at period t as node k's trust value:

2 2 1 () 1 () t k t k t k T     ...(3)

Overall Trust Value with Fuzzy Set and Whitenization Weight Function

The trust models currently used consider the influence of different nodes' viewings; moreover, they also set the weights of the opinions as fixed values, usually average values. This means the important degrees of opinions about trust information from a normal node and a selfish node (or an attacker) are equal. Therefore, our approach is to set the weights as changeable parameters in order to express the degree of trust of a node or nodes, based on their historical behaviour.

We can obtain the trust assessment by using classes of grey clusters and a whitenization weight function. Grey whitenization weight function can be used to measure the utility value of expected revenue [9][13]. This means that whitenization weight functions can describe one value's weights in different clusters, which can be viewed as the degree of how much the value belongs to a cluster. We define n grey clusters c 1 , c 2 , …, c n for evaluating trust degrees, the corresponding whitening functions f 1 (x), f 2 (x), …, f n (x), and the threshold values σ 1 , σ 2 , …, σ n [START_REF] Julong | Introduction to Grey Theory[END_REF]. Three classes of grey clusters are defined as shown in table

.(6)

When node A gets various trust values of node B from different neighbor nodes. The whitenization weight of a trust value T Bk (node B's trust value evaluated by node k, also named as T k ) belonging to the j class c j is f j (T Bk ). According to max j {f j (T Bk )}, we can know the grey cluster class of node B based on T Bk .

2 1 1 (max{ ( )}) (max{ ( )}) 2 2 2 1 (max{ ( )}) 22 k R total j direct direct j k k j j k R I k k I j k k j k R I k w N T f T T f T T N N w w N f T T N N w          ...(7)
Here, ρ=1/2; Nr means the number of recommendation nodes, while Ni means the number of indirect nodes. The Nr and Ni can express the effect levels of different trust relationships, to compose relationship weights. w k (or w kA ) is the weight value of node k that is set by node A. From max j { f j (T total ) }, it can get the total grey cluster class for node B.

Simulation and analysis

The experiment scenario used ns-2 to create a wireless environment, using 802.11 standards, to simulate 6 wireless nodes in a distributed MANETs like structure shown in Figure 2. node 0 wants to get the trust value of node 1 based on trust opinions from node 0 and its neighbouring nodes 2, 3, 4 & 5.The DSDV routing protocol is used. From Grey Theory, we can use the input parameters of a node to calculate the target node's (node 1) trust value, from the view of a specified node like node 0, compared with the neighbour nodes of node 0. That means by Grey Theory, we get node 1's trust value from node 0, which has neighbouring nodes node 2 and node 3. The TMF gets the three nodes' (node 1, 2, 3) trust values for node 0 over a period of 10 seconds, which is T 10 =0.44509 as the direct trust value of node 1. Here ρ=0.5, H={0.2,0.2,0.2,0.2,0.2}, N R =2, N I =0, which means the indirect nodes 4, 5 are not included. All the initial weight values w k0 are set to 1.

The framework also gets T 12 =0.22490, and T 13 =0.20000, which are the recommendation values from nodes 2 and 3 about node 1. After the whitenization functions, the total value of node 1 for node 0 with 3 neighbor nodes is T 10- 3nodes =0.30433, as shown in Figure 3.

Direct, Recommendation and Indirect trust values

Here, the system calculates the trust values among 6 nodes, considering several additional links. ρ=0.5, H={0.2,0.2,0.2,0.2,0.2}, w k0 =1, N R =2, and N I =2.

From the simulating data, we get T 10 =0.44509, and T 12 =0.22490, T 13 =0.20000, T 14 =0.80000, and T 15 =0.50000. From these it is possible to calculate the total trust value with 5 neighbor nodes T 10-5nodes =0.37726, as shown in Figure 3. From max j {f j (T 10-5nodes ) }, we can know node 1's grey cluster class is c 1 .

Analysis

In Figure 3, there are the trust values of node 1 from node 0, 2, 3, 4, 5, and the total values with 3 nodes and 5 nodes, the average value T 10-average of T 10 ~T15 .

Figure 3 trust values From the figure, the results show that taking different relationship factors will affect the total value. T 10-average is higher than T 10-3nodes and T 10-5nodes , due to not including the relationship weights. If the simulation just considers the opinions of nodes 0, 2, 3, the result will be lower than that including nodes 0, 2, 3, 4, 5 because T 15 is higher than T 13 , and T 14 is higher than T 12 .

Figure 4 -Trust values calculated by grey theory and PDR Figure 4 shows the trust values calculated by grey theory, and PLR (Packet Loss Rate) which is often the single metric selected by current TMF approaches such as OTMF (Objective Trust Management Framework) [START_REF] Li | Future Trust Management Framework for Mobile Ad Hoc Networks[END_REF]. Existing trust management schemes like OTMF, often choose the probability of successful interactions as their input parameter in order to calculate their trust values. For nodes 0, 1, the simulation takes a 10-second CBR/UDP traffic from node 0 to node 1. Every second as an interval, the simulator calculates and records the grey trust value of node 1 from node 0, compared with the good-put trust values obtained from the packet delivery rate (PDR) of node 1. The good-put trust value obtained from the packet delivery rate is equal to 1-PLR . T 10 in Figure 3 is the grey trust value of node 1 from node 0 for the period of 10 seconds, while the good-put trust value of node 1 for the period of 10 seconds is 0.463517. The result clearly shows that the individual good-put sample values are very close to the good-put value for the period of 10 seconds, while the grey values have significant variation from T 10 . That means when PLRs are similar, trust values also tend to be similar, by using existed trust management schemes which choose PLR as the main parameter, though these schemes may process PLR with various formulas or algorithms, i.e., Bayesian approach. However, the new TMF described uses multiple parameters with Grey Theory to measure trust values. This is based on the assertion that any one node's behaviour, whether that interaction is successful or not, is affected by various factors, for example the node's signal strength, data rate, throughout, and delay. Therefore, the judgement on whether any node should be trusted, is not only determined by the probability of successful interactions, but also from various parameters in the physical and MAC layers.In fact, the packet loss rates of nodes 1, 2, 3 have little variance over the period, while the throughput and delay times of node 1 are changing with time, compared with those of nodes 2 and 3; this is shown in Figure 5. These changing parameters have a significant impact on the grey trust values.

Selfish behavior detection

The simulations were modified so that one node behaved selfishly. In operation, the node tends to be normal during the initial time, and then behaves selfishly, by only communicating with its nearby neighbours. Using Grey theory, the trust values are affected by the change in received signal strength, although the packet loss rate maintains the same value as with normal behaviours, this is shown in Figure 4. The main reason why the selfish node's trust value decreases is that its signal strength observed by the neighbour is increasing, leading to the drop in its signal strength grey value Currently Grey Theory has been considered for use in developing trust models for wireless networks that have fixed topologies [START_REF] Cai | Grey Theory Based Nodes Risk Assessment in P2P Networks[END_REF]. Some of these new trust models consider just three parameters; they also set fixed weight vectors for their input parameters in calculation of the Grey Relational Grade and the trust value; other research [START_REF] Song | Network Selection in An Integrated Wireless LAN and UMTS Environment Using Mathematical Modeling and Computing Techniques[END_REF] uses Grey Theory in other aspects such as network selection, and not for distributed network trust management. A problem with using fixed weight vectors is that once attackers know which aspect is the most important factor in the system, the malicious nodes can obtain high trust values by only behaving well in that specified aspect, while in fact they do not cooperate with other normal nodes. In this paper, the new TMF considers a greater number of input parameters that cover all aspects of the lower level network protocols to calculate the trust values, hence making it more difficult for any malicious node to replicate all of them. Moreover, it uses several weight vector groups in order to obtain different trust values for a node; this can identify which aspect of a node's behaviour is abnormal, compared with other neighbour nodes. With this idea, the new TMF can also deduce selfish nodes' behaviour strategies.

Different weight vectors H may be used to calculate the grey value, and the new TMF uses multiple weight vectors from which it can calculate various trust values.

These different values can help to show differences between abnormal and normal behaviours; therefore in order detect the strategy that a selfish node employs, a range of vectors are used to identify the attempt to deceive the TMF. Figure 6 shows the results obtain when using the following vectors the : H={0.2,0.2,0.2,0.2,0.2} for (a), H={0.6,0.1,0.1,0.1,0.1} for (b), while H={0.1,0.6,0.1,0.1,0.1} for (c), and H={0.1,0.1,0.1,0.6,0.1} for (d), H={0.1,0.1,0.1,0.1,0.6} for (e), H={0.1,0.1,0.6,0.1,0.1} for (f). The weight configuration is such that for 5 input parameters, we use 6 vectors: one vector with equal weigh assigned to all input parameters, and 5 vectors each with one of the parameters having higher priority. Using this approach, we can not only detect general abnormal behavior, but also identify which of the input parameters are more responsible for it. . Generally, the system can find the difference in trust values between a normal node and a selfish one, when the five parameters have equal weight values, shown in Figure 6(a). Then, by using other weight vector groups, it can be clearly seen that there is a very large gap between normal and selfish trust values whenever the signal strength is set as the most important factor (weight value 0.6), in Figure 6(c). This reveals that the observed node is likely to be behaving selfishly on the aspect of signal strength, due to the abnormal value in Figure 6(c). By setting the weight vectors, the trust management framework can detect more covert (intelligent) selfish behavior. For example, a node may maintain the packet loss rate at a normal level, but just cooperate with other nodes less frequently compared with normal nodes. By using the new framework, the results in Figure 7 (a) show that a selfish node with lower throughput results in a lower trust value, when setting H={0.2,0.2,0.2,0.2,0.2}. Moreover, if the framework uses H={0.1,0.1,0.1,0.1,0.6}, it may be observed that the selfish behavior is largely linked with the parameter throughput, shown in Figure 7 (e). Similar results can be obtained for other selfish strategiies such as delaying packets.

Conclusions

In this paper, a new trust management framework for ad-hoc wireless networks is presented. The new TMF employs multiple metrics to calculate a node's trust values rather than current approaches such as OTMF that consider only one parameter. The approach also uses Grey theory and Fuzzy sets to improve the trust value generation algorithms. Unlike other trust management frameworks, the TMF described in this paper sets a weight vector for each of the input parameters. This provides a significant new benefit for the TMF as it can detect not only selfish or anomalous behaviour, but can also help identify the type of parameters used in the strategy of the attacker or selfish node. Simulation results are presented that reveal the proposed framework can show clearly the difference in the trust values between a normal and selfish node on a specific parameter by setting an appropriate weight vector. In addition, the total trust value is calculated by using relation factors and weights of neighbour nodes, not just by simply taking an average value. Further research will test the proposed framework in more comprehensive environments with more network alternatives and selection criteria.

Figure 2

 2 Figure 2 Topology of the 6 wireless nodes 4.1 Direct and Recommendation trust values In this part, the simulation sets 6 nodes and calculates 4 nodes' trust values from them. All the nodes are static. Each link from node i to node j has a 10-second

Figure 5 -

 5 Figure 5 -Trust Parameters of nodes 1, 2, 3 for 10 seconds For nodes 0, 1, the simulation takes a 10-second CBR/UDP traffic from node 0 to node 1. Every second as an interval, the simulator calculates and records the grey trust value of node 1 from node 0, compared with the good-put trust values obtained

Figure 6

 6 Figure 6 Different weight vectors (attack strategy detected in (c)) In Figure 6, the TMF sets different weight values for the signal strength and other parameters. The weight of signal strength is 0.2 Figure 6(a), 0.6 for Figure 6(c), while 0.1 for Figure 6(b), (d), (e) and (f). Generally, the system can find the difference in trust values between a normal node and a selfish one, when the five parameters have equal weight values, shown in Figure6(a). Then, by using other weight vector groups, it can be clearly seen that there is a very large gap between normal and selfish trust values whenever the signal strength is set as the most important factor (weight value

Figure 7 A

 7 Figure 7 A selfish node's grey trust values (throughput behavior (e))

  Indirect trust can be transited through the third entities. For example, node E and F are the indirect trust nodes, which have interactions with B, but not with A. Recommendation trust is a special type of trust relationships. We assume the nodes have a common node to communicate. This common node is denoted as the recommendation node. For example, nodes A and B have a common node C. If A wants to know the trust records of B from C, C will calculate the trust value of B based on the observations of interactions between B and C.

	1][4][11]. For the neighbourhood of one node,
	according to the link conditions, we can classify as direct, indirect, and
	recommendation relationships, on behalf of node A's different neighbours' trust
	opinions.
	Direct trust is established through observations on whether the previous interactions
	between the nodes have been successful [11]. For example, node A wants to know
	node B's information, for which observations from A to B are for direct trust.

  , while x j is an evaluation index. Here, we assume that X={packet loss rate, signal strength, data rate, delay, throughput}.During a time period t (t=1,2,…T), from the view of a node that observes its neighbouring node k's behaviour and calculates its trust values, k's value of the evaluated index x j is a kj

	t	min	k	, k j	t		g	j	t	max	k	, k j	t	g	j	t
	, kj			, k j	t	g	j	t			max	k	, k j	t	g	j	t
	X		1 { ,..., } m x x
																t =
	{a kj t }, j=1,2,…,m, and the sample matrix for all the neighbouring nodes at t, A t = [a kj t ],
	j=1,2,…,m, k=1, 2,…, K.
	We define at period t, the best reference sequence G t =( g 1 t ,…, g m chosen best index from {a kj t }. From Grey theory, we can obtain the Grey Relational t t is the ), while g j
	Coefficient [6] between node k's sample and the best reference sequence about x j at
	period t as:

t (j=1,2,…,m). We can get node k's sample sequence A k

  while b j t is the chosen worst index from {a kj From Grey theory, we can obtain the Grey Relational Coefficient between node k's samples and worst reference sequence about x j at period t as:

		t	t	t	t
	min		max bb
	k	,, k j j k k j	j
	t
	, kj
	t	t	t	t
		max bb
	,, k j j k k j	j

t }.

Acknowledgments. The authors would like to acknowledge the financial support from the China Scholarship Council (CSC) for this research. Also the authors would like to express their gratitude to Doctor F. Cai for offering useful information and constructive comments on the experiment studies this paper.


Yanbin Lu
email: yanbinl@uci.edu

Gene Tsudik

Enhancing Data Privacy in the Cloud

Due to its low cost, robustness, flexibility and ubiquitous nature, cloud computing is changing the way entities manage their data. However, various privacy concerns arise whenever potentially sensitive data is outsourced to the cloud. This paper presents a novel approach for coping with such privacy concerns. The proposed scheme prevents the cloud server from learning any possibly sensitive plaintext in the outsourced databases. It also allows the database owner to delegate users to conducting content-level fine-grained private search and decryption. Moreover, our scheme supports private querying whereby neither the database owner nor the cloud server learns query details. Additional requirement that user's input be authorized by CA can also be supported.

Introduction

Cloud computing involves highly available massive compute and storage platforms offering a wide range of services. One of the most popular and basic cloud computing services is storage-as-a-service (SAAS). It provides companies with affordable storage, professional maintenance and adjustable space.

On one hand, due to above-mentioned benefits, companies are excited by the public debut of SAAS. On the other hand, companies are reticent about adopting SAAS. One of the major concerns is the privacy as cloud service is generally provided by the third party. In the following, we call the company, who uses SAAS, the database owner. We call anyone who queries the company's database, the database user. And we call the cloud servers, which store the database, the cloud server. Now we start to clarify different types of privacy challenges during the deployment of cloud service.

From the perspective of the database owner, three challenges arise.

-Challenge 1: how to protect outsourced data from theft by hackers or malware infiltrating the cloud server? Encryption by the cloud server and authenticated access by users seems to be a straightforward solution. However, careful consideration should be given to both encryption method and its granularity. -Challenge 2: how to protect outsourced data from abuse by the cloud server? A trivial solution is for the owner to encrypt the database prior to outsourcing. Subsequently, users (armed with the decryption key(s)) can download the entire encrypted database, decrypt it and perform querying in situ. Clearly, this negates most benefits of using the cloud. A more elegant approach is to use searchable encryption. Unfortunately, current searchable encryption techniques only support simple search (attribute=value), as opposed to complicated SQL, queries.

-Challenge 3: how to realize content-level fine-grained access control for users? This challenge is even harder to solve as it requires variable decryption capabilities for different users. Even trivial solution to the second challenge does not solve this challenge as it gives each user equal decryption capability (same decryption key). An ideal solution would entail the database owner issuing a given user a key that only allows the user to search and decrypt certain records.

From user's perspective, three more challenges arise.

-Challenge 4: how to query the cloud server without revealing query details? Learning user's query details means learning user's possibly sensitive search interest. In addition, by learning user queries, the cloud server gradually learns the information in the encrypted database. -Challenge 5: how to hide query contents (e.g., values used in "attribute=value" queries) from the database owner. For the database owner to exercise access control over its outsourced data, a user should first obtain an approval from the database owner over its query contents. However, in some cases, the user may want to get the approval without revealing its query contents even to the database owner. This is the case when the user happens to be a high-level executive who is automatically qualified to search any value and is not willing to reveal query to anyone. -Challenge 6: how to hide query contents while assuring database owner the hiden contents are authorized by some certificate authority (CA). Such challenge surfaces, for example, when the user is FBI who does not want to reveal the person it is investigating while database owner wants to get some confidence by making sure FBI is authorized by the court to do this investigation.

To address the above challenges, we need a scheme for the scenario shown in Fig. 1. In the initial deployment phase, the owner encrypts its database and transfers it to the cloud server. The encryption scheme should guarantee that no plaintext is leaked in the encrypted database, thereby addressing challenges 1-2. When user poses an SQL query, such as: "select from sample where ((last name='Lobb' AND birth date='3/26/1983') OR blood type='B')" it first obtains a search token and decryption key from the database owner. Then, the user supplies the search token to the cloud server who uses the token to search the encrypted database. Matching encrypted records are returned to the user who finally decrypts them. The search token and the decryption key should only allow user to search and decrypt records meeting the conditional expression in the specific query, therefore addressing challenge 3. The search token should not reveal the conditional expression specified by user, therefore solving challenge 4. Further, user should be able to get the search token and decryption key without letting database owner know the query contents in order to solve challenge 5. Finally, to solve challenge 6, database owner, even though not knowing the query contents, should be able to verify if these contents are authorized by a CA.

In this paper, we present a new scheme that addresses aforementioned requirements. It relies on attribute-based encryption [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] and blind Boneh-Boyen weak signature scheme [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF]. In fact, we amend the standard attribute-based encryption to make it privately searchable in the cloud computing scenario. Furthermore, we use the blind Boneh-Boyen signature scheme to let user obliviously retrieve a search token and decryption key. Moreover, blind search token and decryption key extraction procedure can be coupled with CA authorization on user's input.

This paper aims to make four contributions: First, we define the adversary and security model for an encryption scheme aimed at the cloud database system. Second, we construct an encryption scheme that protects data privacy and allows access control. Third, we develop techniques for a user to retrieve search token and decryption key from database owner without revealing query contents. Fourth, we make it possible that the database owner, without knowing query contents, can make sure these contents are authorized by CA.

The rest of the paper is organized as follows. Sec. 2 overviews related work. Next, Sec. 3 defines the function and security model. Then, Sec. 4 discusses some background issues. The new scheme is presented in Sec. 5, followed by Sec. 6 that analyzes its performance. An in-depth performance evaluation is shown in Sec. 7. Limitations of our scheme are discussed in Sec. 8. Finally, Sec. 9 concludes this paper. A complete security proof is provided in the full version [START_REF] Lu | Enhancing data privacy in the cloud[END_REF].

Related Work

Private Information Retrieval and Oblivious Transfer: Private Information Retrieval (PIR) [START_REF] Chor | Private information retrieval[END_REF] allows a user to retrieve an item from a server's (public) database without the latter learning which item is being retrieved. While PIR is not concerned with privacy of the server database, Oblivious Transfer (OT) [START_REF] Rabin | How to exchange secrets by oblivious transfer[END_REF] adds an additional requirement that the user should not receive records beyond those requested. Several results [START_REF] Reardon | Relational-complete private information retrieval[END_REF][START_REF] Olumofin | Privacy-preserving queries over relational databases[END_REF] apply PIR/OT concepts to relational databases in order to hide user SQL queries from the database server.

There are significant differences between these approaches and our work. First these approaches target a user/server scenario and it is unclear how to extend them to the cloud setting with the additional requirement of protecting data from untrusted cloud server. Second user can query any items inside the database and there is no way to enforce access control in these approaches.

Search on encrypted database: Searching on encrypted data (SoE), also known as privacy preserving keyword-based retrieval over encrypted data, was introduced in the symmetric key setting by Song, et al. [START_REF] Song | Practical techniques for searches on encrypted data[END_REF]. This scheme allows a user to store its symmetrically encrypted data on an untrusted server and later search for a specific keyword by giving the server a search capability, that does not reveal the keyword or any plaintext. Its security and efficiency was later improved in [START_REF] Chang | Privacy preserving keyword searches on remote encrypted data[END_REF] and [START_REF] Yang | Privacy-preserving queries on encrypted data[END_REF]. Golle, et al. [START_REF] Golle | Secure conjunctive keyword search over encrypted data[END_REF] developed a symmetric-key version of SoE that supports conjunctive keyword search. Boneh, et al. [START_REF] Boneh | Public key encryption with keyword search[END_REF] later proposed a public-key version of encryption with keyword search (PEKS), where any party in possession of the public key can encrypt and send encryption to an untrusted server, while only the owner of the corresponding private key can generate keyword search capabilities. The server can identify all messages containing the searching keyword, but learn nothing else.

Our work is different from SoE and PEKS since it supports flexible access control (any monotonic access structure) on encrypted data, i.e. the database owner can issue a user a decryption key that only decrypts data meeting a certain conditional expression. Also, our scheme supports oblivious (search token/decryption key) retrieval.

Attribute-based encryption: Sahai and Waters [START_REF] Sahai | Fuzzy identity-based encryption[END_REF] introduced the concept of Attribute-Based Encryption (ABE) where a user's keys and ciphertexts are labeled with sets of descriptive attributes and a particular key can decrypt a particular ciphertext only if the cardinality of the intersection of their labeled attributes exceeds a certain threshold. Later, Goyal, et al. [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] developed a Key-Policy Attribute-Based Encryption (KP-ABE) where the trusted authority (master key owner) can generate user private keys associated with any monotonic access structures consisting of AND, OR or threshold gates. Only ciphertexts that satisfy the private key's access structure can be decrypted. Bethencourt, et al. [START_REF] Bethencourt | Ciphertext-policy attribute-based encryption[END_REF] explore the concept of Ciphertext-Policy Attribute-Based Encryption where each ciphertext is associated with an access structure that specifies which type of secret keys can decrypt it. Ostrovsky, et al. [START_REF] Ostrovsky | Attribute-based encryption with non-monotonic access structures[END_REF] extended [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF] by allowing negative constraints in a key access structure.

Our scheme is derived from that in [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF]. However, compared to traditional ABE, there are several notable differences. First, ABE only achieves payload hiding, i.e., attributes are revealed in plaintext, while our scheme hides the attributes. Second, ABE does not support private search on encrypted data, while our scheme does. Third, ABE does not support oblivious private key retrieval from the authority, while our scheme does.

Predicate encryption: Predicate encryption can be considered as attribute-based encryption supporting attribute-hiding. Ciphertexts are associate with a set of hidden attributes I. The master secret key owner has the fine-grained control over access to encrypted data by generating a secret key sk f corresponding to predicate f ; sk f can be used to decrypt a ciphertext associated with attribute I if and only if f (I) = 1.

Several results have yielded predicate encryption schemes for different predicates. Waters, et al. constructed an equality tests predicate encryption scheme [START_REF] Waters | Building an encrypted and searchable audit log[END_REF]. Shi and Waters [START_REF] Shi | Delegating capabilities in predicate encryption systems[END_REF] constructed a conjunction predicate encryption scheme. In [START_REF] Shi | Multi-dimensional range query over encrypted data[END_REF], Shi, et al. proposed a scheme for range queries. Boneh and Waters [START_REF] Boneh | Conjunctive, subset, and range queries on encrypted data[END_REF] developed a scheme that handles conjunctions and range queries while satisfying a stronger notion of attribute hiding. Katz, et al. [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF] move a step further by making predicate encryption support inner products, therefore supporting disjunction and polynomial evaluation.

Our approach is different in several respects. First, no concrete private search scheme exists in predicate encryption. Although a predicate-only version is enough for private search [START_REF] Katz | Predicate encryption supporting disjunctions, polynomial equations, and inner products[END_REF], requiring private search on a cloud server and access control for users probably means that two separate implementations of predicate encryption are needed. Second, our scheme supports more flexible access control; although, range queries are not covered. Finally, no oblivious retrieval of decryption key for predicate encryption exists so far. U may issue S any SQL query with monotonic access structure. By monotonic access structure, we mean a boolean formula only involving 'AND/OR' combinations. We use an access tree (see Sec. 4.2 for details) to describe any monotonic access structure. In our context, the access tree describes a combination of 'AND/OR' of attribute names, without specifying their values. For example, Fig. 2 depicts one type of access tree corresponding to a conditional expression ((last name=? AND birth date=?) OR blood type=?). If concrete values are supplied together with an access tree, a complete conditional expression can be defined. For example, if a value set (Lobb, 3/26/1983, B) is specified, the expression will be ((last name='Lobb' AND birth date='3/26/1983') OR blood type='B'). We use T γ to denote an access tree constructed over a subset γ of Ω and use v γ to describe a set of values for T γ to completely define a conditional expression. A complete record can be viewed as v Ω . We use T γ (v γ , v γ ′ ) to test whether a set of values v γ ′ satisfies the conditional expression defined by T γ and v γ .

Our basic encryption scheme is a set of components: Setup, Encrypt, Extract, Test, Decrypt. Before starting, the CA runs Setup to initialize some parameters. Then DO runs Encrypt over each record in its table to form an encrypted database. The encrypted database is exported to S (off-line) and DO can insert new encrypted items later. Whenever U forms an SQL query, it runs Extract with DO to extract a search token and decryption key. Then, U hands the search token to S and the latter runs Test over each encrypted record, in order to find matching records. After that. S sends matching records back and U runs Decrypt to recover plaintext records. If additional requirement that DO learns nothing about query content is needed, U can run Blin-dExtract instead of Extract with DO. If further requirement that U's query should be Authorized by CA is needed, U can engage in AuthorizedBlindExtract with DO. We define each function in more detail below.

Basic Scheme Definition

The basic scheme includes following components: and

Setup(1 k ): on input a
a ciphertext C = Encrypt(msk DO , v ′ Ω ), outputs "yes" if T γ (v γ , v ′ Ω ) = 1
and "no" otherwise. Decrypt(U(params, tk (Tγ ,vγ ) sk (Tγ ,vγ ) , C)): U on input params, a search token tk (Tγ ,vγ ) , a decryption key sk (Tγ ,vγ ) and a ciphertext

C = Encrypt(msk DO , v ′ Ω ), outputs v ′ Ω if T γ (v γ , v ′ Ω ) = 1 and ⊥ otherwise.

Blind Extraction Definition

In order to protect U's query from DO, we need to replace Extract with a blinded version, called BlindExtract. BlindExtract(U(params, T γ , v γ ), DO(params, msk DO )): U on input (params, T γ , v γ ) and DO on input (params, msk DO , T γ ) engage in an interactive protocol. U's output is a search token tk (Tγ ,vγ ) and a decryption key sk (Tγ ,vγ ) , and DO's output is T γ . Sometimes, it makes more sense to require U to prove that its input in BlindExtract is authorized by a CA before U can get anything useful. In order to realize that, we introduce two other functions Authorize and AuthorizedBlindExtract. Authorize helps a U get a commitment ψ and a signature σ from a CA. In AuthorizedBlindExtract, DO is provided with T γ , ψ, σ while U can prove statements about commitment ψ using zero-knowledge proof.

Authoriz(U(params, T γ , v γ ), CA(params, msk CA )): CA generates a commitment ψ over U's input (T γ , v γ )
, the randomness open used to compute ψ and a signature

σ over ψ. CA's output is (T γ , v γ , ψ, open, σ). U's output is (ψ, open, σ). AuthorizedBlindExtract(U(params, T γ , v γ , ψ, open, σ), DO(params, msk DO )): U on input (params, T γ , v γ , ψ, open, σ) and DO on input (params, msk DO ) en- gage in an interactive protocol. DO's output is (T γ , ψ, σ). If ψ = Commit((T γ , v γ ),
open) and Vrfy pkCA (ψ, σ) = 1, U's output is a search token tk (Tγ ,vγ ) and a decryption key sk (Tγ ,vγ ) , and otherwise, U outputs ⊥.

Adversary Model and Security Requirement

In this paper, we assume the malicious adversary model (as opposed to semi-honest, aka "honest-but-curious") . A malicious adversary can arbitrarily deviate from the prescribed protocols. We also assume that U may collude with S. However, DO does not collude with any party. In the full version of this paper [START_REF] Lu | Enhancing data privacy in the cloud[END_REF], we will prove our scheme is secure against malicious adversary according to Def. 1, 2 and 3.

For the basic scheme, we define adversary's advantage by defining a security game under chosen plaintext attack in a selective set model, similar to [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF]. BlindExtract must satisfy two security properties: Leak-free Extract [START_REF] Green | Blind identity-based encryption and simulatable oblivious transfer[END_REF] and Selective-failure Blindness [START_REF] Camenisch | Simulatable adaptive oblivious transfer[END_REF]. Informally, the former means that a malicious U cannot learn more by executing the BlindExtract with an honest DO than by executing Extract with an honest DO. Whereas, Selective-failure Blindness means that a malicious DO cannot learn anything about U's choice of v γ during BlindExtract. Moreover, DO cannot cause BlindExtract to fail based on U's choice. Now we formally define Leak-free Extract and Selective-failure Blindness: Definition 2. (Leak-Free Extract). BlindExtract protocol is leak free if, for all p.p.t. adversaries A, there exists an efficient simulator such that for every value k, A cannot determine whether it is playing Game Real or Game Ideal with non-negligible advantage, where Game Real: Run Setup(1 k ). As many times as A wants, A chooses its T γ , v γ and executes BlindExtract(•) with DO. Game Ideal: Run Setup(1 k ). As many times as A wants, A chooses its T γ , v γ and executes BlindExtract(•) with a simulator which does not know msk DO and only queries a trusted party to obtain tk (Tγ ,vγ ) and sk (Tγ ,vγ ) .

Access Tree

We use T to denote a tree representing an access structure. T represents a combination of 'AND/OR' of attribute names without specifying their values, as shown in Fig. 2. An access structure T γ defined over a set γ of attributes, coupled with a set of values v γ defined over the same set, completely defines a conditional expression (See Sec. 3.1 for example). We use T γ (v γ , v) to test whether another set of values v satisfies the condition defined by T γ and v γ . Each non-leaf node represents a threshold gate, described by its children and a threshold value. Let num x be the number of children of a node x. The threshold value associated with node x is denoted by k x that is either 1 or num x , depending on the threshold gate. In case of an OR gate, k x = 1; in case of an AND gate, k x = num x . Each leaf node x is described by an attribute with a threshold k x = 1. Standard tree data structures can be used to represent and store T . Since T γ is exposed to S in Test, to prevent S from learning database schema, each leaf node can store an attribute index instead of the attribute name.

To facilitate working with the access trees, we define a few functions. We denote the parent of the node x as parent(x). node(α i ) returns the leaf node corresponding to attribute α i . attr(x) is defined only if x is a leaf node; it returns the attribute index i of α i associated with x. Access tree T also defines an ordering between the children of every node, i.e. each child y of a node x are numbered from 1 to num x . index(y) returns this number associated with the node y. Let S x denote a set [1, . . . , num x ]. Finally, let child i (x) return the ith child of node x.

We also define Γ Tγ as a set of minimum subsets of γ that satisfies T γ . By "minimum", we mean the subset cannot become smaller while still satisfying T γ . For example, in Fig. 2, Γ Tγ = {{1, 2}, {3}} where 1, 2, 3 is the index of attribute last name, birth date, blood type respectively. Here Γ Tγ means that either {last name, birth date} or {blood type} can satisfy T γ . We can determine Γ Tγ in a down-top manner. For each leaf node, define S x = {attr(x)}. For any other node x,

S x = ∪ i∈Sx S childi(x) if k x = 1. Otherwise if k x > 1, S x = {x ′ : x ′ = ∪ 1≤i≤kx x ′ i , ∀x ′ i ∈ S childi(x) }.
And the resulting S r at root node r is Γ Tγ . For γ ′ ∈ Γ Tγ , we define T γ ′ as a subgraph of T γ with only attributes in γ ′ as leaves. For example, in Fig. 2, if γ ′ = {1, 2}, then T γ ′ would be the left-hand subtree of the root node. Note in T γ ′ each non-leaf node x's k x should be its number of children, i.e., a conjunctive gate, since γ ′ is a minimum satisfiable subset.

Homomorphic Encryption

There are several additively homomorphic public key encryption schemes [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF][START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. We elect to use Paillier encryption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] due to its easy implementation and amenability to proofs of knowledge. Let n denote an RSA modulus, h = n + 1 and g be an element of order φ(n) mod n 2 . Let sk = {φ(n)} and pk = {g, n}. Encryption is defined as c = Enc hom pk (m) = h m g r mod n 2 where r ∈ R Z φ(n) . Corresponding decryption is defined as:

Dec hom sk (c) = (c φ(n) mod n 2 )-1 n • φ(n) -1 mod N . Note that, to encrypt,
we use h m g r instead of standard h m r n . If the order of g has no factor of n and is greater than 2, g r is a random element from the same subgroup as r n . Therefore h m g r has the same distribution as h m r n . The purpose of using the former is to facilitate zeroknowledge proofs.

Zero-Knowledge Proof

Our scheme uses various protocols to prove knowledge of, and relations among, discrete logarithms. To describe these protocols, we use the notation introduced by Camenisch and Stadler [START_REF] Camenisch | Efficient group signature schemes for large groups[END_REF]. For instance, P K{(a, b, c) : y = g a h b ∧ y = g a h c ∧ s ≤ b ≤ t} denotes a zero-knowledge proof of knowledge of integers a, b, c such that y = g a h b and y = g a h c holds and s ≤ b ≤ t. The convention is that everything inside parentheses is only known to the prover, while all other parameters are known to both prover and verifier.

The technique for a proof of knowledge of a representation of an element y ∈ G with respect to several bases z 1 , . . . , z v ∈ G, i.e., P K{(a [START_REF] Chaum | An improved protocol for demonstrating possession of discrete logarithms and some generalizations[END_REF]. A proof of equality of discrete logarithms of two group elements y 1 , y 2 ∈ G to bases g ∈ G and h ∈ G, respectively, i.e., P K{(a) : y 1 = g a ∧ y 2 = h a }, is given in [START_REF] Chaum | Zero-knowledge undeniable signatures[END_REF]. Generalizations to proving equalities among representations of elements y 1 , . . . , y v ∈ G to bases g 1 , . . . , g v ∈ G are straightforward [START_REF] Camenisch | Efficient group signature schemes for large groups[END_REF]. Boudot [START_REF] Boudot | Efficient proofs that a committed number lies in an interval[END_REF] demonstrates proof of knowledge of a discrete logarithm of y ∈ G with respect to g ∈ G such that log g y lies in integer interval [s, t], i.e., P K{(a) : y = g a ∧ a ∈ [s, t]} under the strong RSA assumption and the assumption that the prover does not know the factorization of the RSA modulus.

1 , • • • , a v ) : y = z a1 1 • • • z av v }, is presented in

Bilinear map

We now review some general notions about efficiently computable bilinear maps.

Let G 1 and G 2 be two multiplicative cyclic groups of prime order q. Let g be a generator of G 1 and ê be a bilinear map, ê :

G 1 × G 1 → G 2 .
The bilinear map ê has the following properties:

1. Bilinearity: for all u, v ∈ G 1 and a, b ∈ Z p , we have ê(u a , v b ) = ê(u, v) ab 2. Non-degeneracy: ê(g, g) = 1.

We say that G 1 is a bilinear group if the group operation in G 1 and the bilinear map ê : G 1 × G 1 → G 2 are both efficiently computable.

Cryptographic Assumption

Our scheme's security is based on the decisional bilinear Diffie-Hellman (BDH) assumption [START_REF] Boneh | Efficient selective-id secure identity based encryption without random oracles[END_REF] and Boneh-Boyen Hidden Strong Diffie-Hellman (BB-HSDH) assumption [START_REF]Short signatures without random oracles[END_REF].

Assumption 1 (Decisional Bilinear Diffie-Hellman (BDH) assumption.) Let a, b, c, z ∈ Z q be chosen at random and g be a generator of G 1 . We say that the BDH problem is hard if for all p.p.t. adversaries A there exists a negligible function negl such that |Pr[A(g a , g b , g c , ê(g, g) abc ) = 1] -Pr[A(g a , g b , g c , ê(g, g) z ) = 1]| ≤ negl(n) where in each case the probabilities are taken over the random choice of the generator g, the random choice of a, b, c, z in Z q and the random bits consumed by A.

Assumption 2 (Boneh-Boyen Hidden Strong Diffie-Hellman (BB-HSDH)

). Let x, c 1 , • • • c t ∈ R Z q . On input g, g x , u ∈ G 1 , h, h x ∈ G 2 and the tuple {g 1/(x+c l ) , c l } l=1...t , it is computationally infeasible to output a new tuple (g 1/(x+c) , h c , u c ).

Scheme

We present our scheme Π which consists of following algorithms.

Setup(1 k ): Run G(1 k ) to obtain (q, G 1 , G 2 , ê, n, g, n, g, h). n is an RSA modulus larger than 2 k q 2 with generator g. Let sk DO = φ(n) and pk DO = {g, n}. In other words, only DO knows the factors of n. n is another RSA modulus with generator g and h. Note neither factors of n nor log g h is known to any party. Pick secret parameters t, t ′ , y, y ′ which are only known to DO. Make Y = ê(g, g) y , Y ′ = ê(g, g) y ′ , T = g t , T ′ = g t ′ , e t = Enc hom pkDO (t), e t ′ = Enc hom pkDO (t ′ ), and π s proving e t and e t ′ are well formed. Output params ← (Y, Y ′ , T, T ′ , e t , e t ′ , π s , pk DO , pk CA , n, g, h), msk DO ← (t, t ′ , y, y ′ , sk DO ).

Encrypt(DO(params, msk DO , m)):

To encrypt a record m = v Ω = {v 1 , . . . , v w }, DO chooses random values s, s ′ ∈ R Z q and outputs the ciphertext as:

C = (E, E ′ , {E i , E ′ i } i∈Ω ) .
where

E = Enc sym Y s (m), E ′ = Y ′ s ′ , E i = g s•(t+H(i,vi)) and E ′ i = g s ′ •(t ′ +H ′ (i,vi)) .
Extract(U(params, T γ , v γ ), DO(params, msk DO )): This is an interactive protocol between U and DO.

1. U chooses an attribute set γ and constructs T γ and v γ to fully define a conditional expression it wants to query. Then it submits T γ and v γ to DO.

2. DO defines a polynomial Q x (•) of degree k x -1 for each node x in T γ in a topdown manner. For the root node r, it sets Q r (0) = y and k r -1 other points of Q r randomly to fully define Q r (•). For any other node x, it sets Q x (0) = Q parent(x) (index(x)) and chooses k x -1 other points randomly to completely define Q x (•). Then it outputs decryption key sk (Tγ ,vγ

) = {{sk i } i∈γ , T γ , v γ } where sk i = g Q node(α i ) (0)/(t+H(i,vi)) . DO defines Q ′ x (•) in the same way as Q x (•) except that Q ′ r (0) = y ′ . And it outputs search token tk (Tγ ,vγ ) = {{tk i } i∈γ , T γ } where tk i = g Q ′ node(α i ) (0)/(t ′ +H ′ (i,vi))
. Last, DO sends tk (Tγ ,vγ ) and sk (Tγ ,vγ ) to U.

Test(S(params, tk (Tγ ,vγ ) , C)): To test whether an encrypted record

C = Encrypt(msk DO , v ′ Ω ) matches a search token tk (Tγ ,vγ ) = {{tk i = g Q ′ node(α i ) (0)/(t ′ +H ′ (i,vi)) } i∈γ , T γ }, it first calculates Γ Tγ from T γ .
The search operation starts from the first γ ′ ∈ Γ Tγ . Let i = attr(x). For each node x in T γ ′ , it computes a value z x in a down-top manner. For each leaf node x in T γ ′ , S computes

z x = ê(tk i , E ′ i ). We use v ′ i to denote the value embedded in E ′ i . Note if v i = v ′ i , z x = ê(g Q ′ x (0)/(t ′ +H ′ (i,vi)) , g s ′ •(t ′ +H ′ (i,v ′ i )) ) = ê(g, g) s ′ •Q ′ x (0) . For each non-leaf node x, it sets z x = i∈Sx (z childi(x) ) ∆i,S x . Note if {v i = v ′ i } i∈γ ′ , z x = i∈Sx (ê(g, g)) s ′ •Q ′ child i (x) (0)•∆i,S x = i∈Sx (ê(g, g)) s ′ •Q ′ x (i)•∆i,S x = ê(g, g) s ′ •Q ′ x (0)
. The procedure continues until it reaches the root node r. If z r = E ′ , S outputs 'yes'. Otherwise, it continues to test the next γ ′ . If all γ ′ s do not meet the criteria, it outputs 'no'.

Decrypt(U(params, tk (Tγ ,vγ ) , sk (Tγ ,vγ ) , C)): The decryption algorithm first identifies γ ′ satisfying tk (Tγ ,vγ ) as Test algorithm does. Note this step can be omitted if γ ′ is provided as input after it is identified by Test. Then it follows a down-top manner in T γ ′ . Let i = attr(x). Then for each leaf node x ∈ T γ ′ , it computes z x = ê(sk i , E i ). Note since

v i equals to v ′ i , z x = ê(g Qx(0)/(ti+t•vi) , g s(ti+t•v ′ i ) ) = ê(g, g) s•Qx(0) . For non-leaf node x ∈ T γ ′ , it computes z x = i∈Sx (z childi(x) ) ∆i,S x = i∈Sx (ê(g, g)) s•Q child i (x) (0)•∆i,S x = i∈Sx (ê(g, g)) s•Qx(i)•∆i,S x = ê(g, g) s•Qx(0)
. The procedure continues until it reaches root r and z r = ê(g, g) s•Qr(0) = ê(g, g)

s•y = Y s is computed. Then user recovers m = Dec sym H(Y s ) (E).
BlindExtract(U(params, T γ , v γ ), DO(params, msk DO )):

1. U first verifies π s . If π s passes verification, then the user chooses

r i,1 , r ′ i,1 ∈ R Z q and r i,2 , r ′ i,2 ∈ R [0, . . . , 2 k q]
and computes

e i = ((e t ⊕ Enc hom pks (H(i, v i ))) ⊗ r i,1 ) ⊕ Enc hom pks (r i,2 • q), ∀i ∈ γ e ′ i = ((e t ′ ⊕ Enc hom pks (H ′ (i, v i ))) ⊗ r ′ i,1 ) ⊕ Enc hom pks (r ′ i,2
• q), ∀i ∈ γ It also computes a zero-knowledge proof π c proving e i , e ′ i are well formed and r i,1 , r i,2 , r ′ i,1 , r ′ i,2 are in appropriate interval. Then it sends {e i , e ′ i } i∈γ , T γ , π c to DO. 2. DO verifies π c to make sure e i , e ′ i , r i,1 , r ′ i,1 , r i,2 , r ′ i,2 are correctly embedded. Then DO starts to define a polynomial Q x (•) of degree k x -1 for each node x in T γ in a top-down manner. For the root node r, it sets Q r (0) = y and k r -1 other points of Q r randomly to fully define Q r . For any other node x, set Q x (0) = Q parent(x) (index(x)) and choose k x -1 other points randomly to completely define Q x . DO defines another polynomial Q ′

x (•) in the same way as

Q x (•) except that Q ′ x (0) = y ′ . Next, for each i ∈ γ, DO decrypts d i = Dec hom skDO (e i ), d ′ i = Dec hom
skDO (e ′ i ) and sends a i = g Q node(α i ) (0)/di and a

′ i = g Q ′ node(α i ) (0)/d ′ i to U. 3. U computes sk i = a i ri,1 = g Q node(α i ) (0)/(t+H(i,vi)) and tk i = a ′ i r ′ i,1 = g Q ′ node(α i ) (0)/(t ′ +H ′ (i,vi)) for i ∈ γ.
Then U checks the validity of sk i s. To do that, it computes p i = e(sk i , T • g H(i,vi) ) = e(g, g) Q node(α i ) (0) for all i ∈ γ. After that, it starts to compute a value q x for each node x in T γ in a down-top manner starting from leaves. For each leaf node x in T γ , its q x is set to p attr(x) . For a non-leaf node x, q x is dependent on k x . If k x = 1, user first verifies that each q childi(x) , for all i ∈ S x , is the same. Then it sets q x = q childi(x) , for arbitrary i ∈ S x . If k x > 1, it sets q x = i∈Sx (q childi(x) ) ∆i,S x . The procedure continues until it reaches the root node r. Finally, the user checks whether q r ? = Y . If any above verification fails, U quits. U checks tk i in the same way as it does sk i except that q r should be equal to Y ′ this time. U outputs decryption key sk (Tγ ,vγ ) = {{sk i } i∈γ , T γ , v γ } and search token tk (Tγ ,vγ ) = {{tk i } i∈γ , T γ }.

Authorize(U(params, T γ , v γ ), CA(params, sk CA )): U submits T γ , v γ to CA. CA verifies that U has the right to search for the conditional expression defined by (T γ , v γ ). If it approves user request, then CA, on U's behalf, makes pedersen commitments c vi , c ′ vi on each v i ∈ v γ , i.e. c vi = g H(i,vi) h rv i and c ′ vi = g H ′ (i,vi) h r ′ v i . Next, CA maps T γ to a Merkle hash tree. Specifically, it computes a hash value for each node x in T γ . For each leaf node x, its hash value is h x = H(k x ). For non-leaf node, its hash value is defined as the hash of concatenations of its k x and its children's hash values, i.e. h x = H(k x ||h child1(x) || • • • ||h childnum x (x) ). Let h r denote the hash value for the root node r. CA issues a signature σ on h r and {c vi , c ′ vi } i∈γ , i.e. σ = Sign skCA (h r , {c vi , c ′ vi } i∈γ ), and send {{r vi , c vi , r ′ vi , c ′ vi } i∈γ , σ} back to U.

AuthorizedBlindExtract(U(params, T γ , v γ , ψ, open, σ), DO(params, msk DO )): This protocol is detailed in [START_REF] Lu | Enhancing data privacy in the cloud[END_REF]. Here ψ = {c vi , c ′ vi } i∈γ and open = {r vi , r ′ vi } i∈γ . The protocol basically follows the BlindExtract protocol except that U needs to prove statements about commitments using zero-knowledge proof.

Performance Analysis

Before presenting performance analysis, we point out two possible improvements to the scheme. First, in Test algorithm, if the identified matching set γ ′ is sent to U, then Decrypt algorithm does not need search token to seek γ ′ again. Second, as pointed out in [START_REF] Goyal | Attribute-based encryption for fine-grained access control of encrypted data[END_REF], instead of exponentiating at each level during the computation of z x in Decrypt, for each leaf node in γ ′ , we can keep track of which Lagrange coefficient is multiplied with each other. Using this, we can compute the final exponent f x for each leaf node x ∈ T γ ′ by doing multiplication in Z q . Now z r is simply i∈γ ′ ê(sk i , E i ) f node(α i ) . The same optimization applies to Test algorithm. We now consider the efficiency of the scheme.

Performance Evaluation

We implemented the proposed scheme in C++ using PBC (ver. 0.57) [START_REF] Lynn | PBC: The Pairing-Based Cryptography Library[END_REF] and OpenSSL (ver. 1.0.0) [START_REF]OpenSSL[END_REF] library. This section discusses the performance of each function in our scheme. All benchmarks were performed on a Ubuntu 9.10 desktop platform with Intel Core i7-920 (2.66GHz and 8MB cache) and 6GB RAM.

Since performance of each function only depends on the access tree, we do not consider the performance impact of the contents associated with leaf nodes. We use a random access tree (in all tests) that is generated as follows. First we fix the number of leaves, n leaves . Then a random tree height n height between 1 and 5 is chosen. The node degree is computed as n degree = ⌈n 1/n leaves leaves ⌉. After n leaves , n height , n degree is determined, the random tree is constructed in a down-top manner. At depth l, one parent node is constructed for every n degree nodes at depth l + 1. If less than n degree nodes are left at depth l + 1, one parent node is constructed for these remaining nodes. The procedure continues until only one parent (root) can be constructed. For simplicity, we assume the total number of attributes w = |γ| = n leaves .

First we test the speed of Encrypt. Fig. 3 (Encryption Speed line) shows the overhead to compute Y s , E ′ , {E i , E ′ i } i∈Ω versus the number of attributes |γ|. As we can see, its overhead increases linearly with |γ|. Fig. 4 shows the performance of symmetric encryption, which is needed to compute E = Enc sym H(Y s ) (m). Extract and BlindExtract performance is also shown in Fig. 3. In this test, the threshold gates in the access tree are chosen randomly. The overhead of Extract (Extraction (Data Owner) line) is solely at DO side and it increases linearly with |γ|. The overhead of BlindExtract is at both U side and DO side. The overhead at DO side (Blind Extraction (Data Owner) line) is almost nine times that of normal extraction. The overhead at U side (Blind Extraction (User) line) doubles that at DO side.

To test Decrypt, we assume γ ′ = γ, i.e., all attributes should be involved in the decryption. Since all threshold gates in T γ ′ should be conjunctive gates, we make them conjunctive in the random access tree T γ as well. Fig. 3 (Decryption Speed line) shows the speed to recover Y s . We find that decryption overhead increases linearly with |γ| and it is even cheaper than extraction. The reason is because pairing operation and exponentiation in G 2 is faster than exponentiation in G 11 . Fig. 5 shows the speed of computing f x for all leaf node x, which is necessary for the optimization of decryption. Its speed is almost linear with the product of |γ|, tree height and tree degree. Note this part of operation can be conducted offline and only needs to be computed once for one type of access tree. The performance of Dec sym H(Y s ) (E) is same as Enc sym H(Y s ) (m) as shown in Fig. 4.

As to Test performance, it highly depends on the access tree. During the following test, the performance is recorded in the worst case, i.e. all possible subtrees T γ ′ of T γ are tried. Fig. 3 shows the conjunction-only Test and disjunction-only Test performance. As we can see, they all increases linearly with |γ|. The reason why they are almost the same is because conjunction-only Test has 1 test involving |γ| pairing and |γ| exponentiation in G 2 while disjunction-only Test has |γ| tests involving 1 pairing. To further test Test operation, we use random access tree. We restrict |γ| to be 10, which is usually enough for normal query, and set each threshold gate in the tree randomly. Fig. 6 shows the results of 100 test cases. As we can see the maximum Test time is 170ms and the average Test time is 85ms. In cloud computing scenario, multiple Test operations can run simultaneously and therefore spending average 85ms on each record is acceptable.

The proposed scheme has some limitation and it should be considered in future work. First it only supports equality testing. Practical privacy-preserving comparison is not available yet. Second, it only hides concrete value in the conditional expression and the structure T γ is revealed to the adversary. Third, join operations between two tables are not supported. Fourth, if the set of possible attribute values in γ is small, the adversary can always try to encrypt something under all possible values and run Test over the encryptions to see if there is a match. This would reveal v γ within tk (Tγ ,vγ ) . However, the complexity of such brute force attacks against this intrinsic weakness of public keybased searchable encryption, grows exponentially with |γ|. Fifth, DO is required to be online to help U extract search tokens and decryption keys. However, we expect that this functionality can be finished by some secure hardware that can be safely installed at U side without compromising msk DO .

Conclusion

This paper provides an overview of privacy challenges facing cloud storage and develops a novel encryption scheme for coping with these challenges. The scheme hides the plaintext of database and user's query content from the cloud server. It allows data owner to do content-level fine-grained access control by issuing users appropriate search tokens and decryption keys. The scheme also supports blind retrieval of search tokens and decryption keys in the sense neither data owner nor cloud server learns the query content. Additional feature of user input authorization by CA can also be supported. Our evaluation shows that its performance falls within the acceptable range.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Cloud storage architecture.

Definition 1 .

 1 (Selective-Set Secure (IND-SS-CPA)). Let k be a security parameter. Above scheme is IND-SS-CPA-secure if every p.p.t. adversary A has an advantage negligible in k for the following game: (1) Run Setup(1 k ) to obtain (params, msk DO ), and give params to A. (2) A outputs two records m 1 , m 2 to be challenged on (3) A may query an oracle O Extract (params, msk DO , T γ , v γ ) such that T γ (v γ , m 1 ) = 1 and T γ (v γ , m 2 ) = 1. (4) Select a random bit b and give A the challenge c * ← Encrypt(params, msk DO , m b ). (5) A may continue to query oracle O Extract (•) under the same conditions as before. (6) A outputs a bit b ′ . We define A's advantage in the above game as |Pr[b ′ = b] -1/2|.

Definition 3 .

 3 (Selective-Failure Blindness). BlindExtract is selective-failure blind if every p.p.t. adversary A has a negligible advantage in the following game: First, A outputs params and a pair of(T , v 1 ), (T , v 2 ). A random bit b is chosen. A is given blackbox access to two oracles U(params, T , v b ) and U(params, T , v 1-b ). The U algorithm produces local output s b = (tk (T ,v b ) , sk (T ,v b ) ) and s 1-b = (tk (T ,v 1-b ) , sk (T ,v 1-b ) ) respectively. If s b = ⊥ and s 1-b = ⊥ then A receives (s 0 , s 1 ). If s b = ⊥ and s 1-b = ⊥ then A receives (⊥, ǫ). If s b = ⊥ ands 1-b = ⊥, then A receives (ǫ, ⊥). If s b = ⊥ and s 1-b = ⊥, then A receives (⊥, ⊥). Finally, A outputs its guess bit b ′ . We define A's advantage in the above game as |Pr[b ′ = b] -1/2|.

4. 1

 1 NotationLet {0, 1} l denote the set of integers of maximum length l, i.e. the set [0, 2 l -1] of integers. we employ the security parameters l φ , l H where l φ (80) is the security parameter controlling the statistical zero-knowledge property, l H (160) is the output length of the hash function used for the Fiat-Shamir heuristic. H(•) and H ′ (•) denote two distinct hash function. We use Enc hom pk and Dec hom sk to denote homomorphic encryption and decryption (respectively) under public key pk (or secret key sk). We use Enc sym k and Dec sym k to denote symmetric encryption and decryption under key k. We define Lagrange Coefficient as ∆ i,S = j∈S,j =i j j-i . Let Ω denote attributes index set, i.e. Ω = {1, • • • , w}. DO's private and public keys are sk DO and pk DO , respectively. server's master key is msk DO . CA's private and public keys are sk CA and pk CA .

Fig. 3 .Fig. 4 .

 34 Fig. 3. Performance of Encryp, Extract, Decrypt vs. number of attributes.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Decryption preparing time.

  security parameter 1 k , outputs parameters params, DO's master key msk DO . Encrypt(DO(params, msk DO , v Ω )): DO on input params, msk DO and a record v Ω , outputs a ciphertext. Extract(U(params, T γ , v γ ), DO(params, msk DO )): U on input (params, T γ , v γ ) and DO on input (params, msk DO ) engage in an interactive protocol. At the end, U outputs a search token tk (Tγ ,vγ ) and a decryption key sk (Tγ ,vγ ) , and DO outputs (T γ , v γ ). Test(S(params, tk (Tγ ,vγ ) , C)): S on input parameters params, a search token tk (Tγ ,vγ )

  The Encrypt algorithm takes 2n group exponentiations in G 1 . The Extract algorithm takes 2 • |γ| group exponentiations in G 1 . In BlindExtract algorithm, DO spends 20 • |γ| group exponentiations in G 1 . U spends 28 • |γ| group exponentiations in G 1 plus some verification time dependent on access tree. The Test algorithm's performance depends on the access tree T γ . In conjunction-only case, it involves 1 test of |γ| pairing and |γ| exponentiation in G 2 . In disjunction-only case, it involves |γ| tests of 1 pairing operation. Compared to |γ| pairing overhead in [17,19,20], our scheme has similar overhead while supporting more flexible queries. The optimized Decrypt algorithm takes |γ ′ | pairing and |γ ′ | group exponentiations in G 2 .

In our benchmark of Type A pairing family in[START_REF] Lynn | PBC: The Pairing-Based Cryptography Library[END_REF], one exponentiation in G1 takes 1.9 ms, one exponentiation in G2 takes 0.18 ms while one group pairing takes 1.4 ms.


Pam Briggs Pactlab
email: p.briggs@northumbria.ac.uk

The Evolution of Trust

Keywords: Trust, credibility, privacy

In this paper I discuss the evolution of trust from early studies of interpersonal trust to current research on the role of trust in computer-mediated communication. I reflect on the ways in which the context for the investigation of trust has led to very different views about just what trust is and how it changes over time and I conclude with examples from my own work about the development of trust online and the potential for new trust tools.

A story appeared in the news a few years ago about a circus touring in Scotland that posted an advert for a knife-throwers assistant in a local town. Twenty-three people applied for the post, but only six were brave enough to turn up for an audition, when they were asked to stand against a board while 10 knives were hurled at them at speeds of up to 45 miles per hour. The knife-thrower -a Mr Hanson -said he had never inflicted major injury although he had given people nicks and cuts in the past. He said was looking for someone who was willing to have a laugh but who also had serious qualities and trusted him. Seonaid Wiseman, a 29-year-old post-graduate student at Aberdeen University was the first of the candidates to audition. Following the ordeal she said she had been "blank with terror" when the first knife hit the board, but added: "It wasn't bad after the first one. After the first one I had every confidence in him." Understanding the development of just this kind of interpersonal trust was one of the first challenges for early trust researchers where the focus was on the critical dimensions by which people evaluate how others will behave. In early contexts trustworthiness was defined as "the extent to which people are seen as moral, honest and reliable" [START_REF] Wrightsman | Measurement of philosophies of human nature[END_REF] -a definition which while perfectly valid (although defining 'moral' is not an enviable task) says little about what trust is, nor why its perception will vary between individuals.

The term trust can imply so many different things, because it presupposes some risk, but isn't explicit about the nature of that risk. Inevitably, then, over time, different approaches to trust research have evolved, depending upon the trust context. Within the workplace trust presupposes risks such as loss of reputation and self-esteem, damage to career and loss of salary. Yet trust between colleagues is vital. Robert Levering, author of 'A great place to work' [START_REF] Levering | A Great Place to Work[END_REF] and co-author of 'The 100 best places to work for in America' [START_REF] Levering | The 100 Best Companies to Work for in America[END_REF] has argued that "trust between managers and employees is the primary defining characteristic of the very best workplaces" and Dennis and Michelle Reina [START_REF] Reina | Trust and NBetrayal in the Workplace: Building Effective Relationships in Your Organization[END_REF] described the betrayals that undermine modern working relationships -the colleague taking credit for your work, the boss failing to deliver on a promise, the assistant passing on confidential information -and have concluded that we live in an era where corporate leaders have lost the loyalty, trust and commitment of their workforce, to devastating effect.

Political philosopher Onora O'Neill has argued that trust can be lost by the very systems set up to preserve it. In delivering the 2002 Reith Lectures [8, lecture 3], O'Neill describes the ways in which various systems of public accountability have provided consumers and citizens with more information and more complaints systems, but which have ultimately built a culture of suspicion and low morale likely to generate professional cynicism and ultimately public mistrust. Thus the trend towards audit and transparency which is evident in indicators such as school league tables, University research ratings, hospital waiting lists and transport punctuality figures means that workers gear their actions towards the accountable targets, and have less time to spend on those aspects of the work that cannot be explicitly measured. In this way some of the metrics that can be used (rather unsuccessfully) as proxies for trust can start to drive organisational behaviour.

A different approach to trust was discussed by Francis Fukuyama who set trust in the context of vastly different societies and cultures [START_REF] Fukuyama | Trust: The Social Virtues and the Creation of Prosperity[END_REF]. He identified to 'high trust' societies like Japan, where, he argued, life can be much easier on the individual as a result of the strong social ties binding Japanese citizens together, and observed that these, coupled with relatively low instances of deviance, meant that the enhanced sense of trust within that society is palpable. However, crucial to Fukuyamas argument was that many societies are suffering an erosion of trust that is having devastating effects on both individuals and society. He cited America as an example of a society previously high in trust, in which individualism grew at the expense of community, creating a crisis of trust signalled by a huge increase in litigation and a corresponding fortress mentality. He described the effects of such a decline: 'people who do not trust one another will end up cooperating only under a system of formal rules and regulations, which have to be negotiated, agreed to, litigated, and enforced, sometimes by coercive means. This legal apparatus, serving as a substitute for trust, entails what economists call "transaction costs". Widespread distrust in a society, in other words, imposes a kind of tax on all forms of economic activity, a tax that high-trust societies do not have to pay.' [3, pg. 28].

Against this background -of interpersonal, workplace and societal trust -what can we learn from current studies of trust that take place in the context of computer-mediated communication? Certainly, in the wake of significant amounts of e-commerce research, we know that it is meaningful to talk about trust online and that there are arguably high-trust cultures that flourish online (such as early versions of eBay, where there were fewer guarantees and a greater willingness to trust in a transaction). Furthermore the context for trust online has become extremely diverse with the rise of social networks and an increased tendency for people to use Internet-based information to inform important life decisions across a number of domains (in my own work I have explored trust decisions in the contexts of e-government [START_REF] Marsh | Trust in digital government -social issues[END_REF], privacy [START_REF] Little | Trust and privacy permissions for an ambient world[END_REF] and health [START_REF] Sillence | Going online for health advice: Changes in usage and trust practices over the last five years[END_REF]). Such domains of trust enquiry have led to the proliferation of trust models that capture different aspects of online trust or that model the dynamics of trust development. In my own work I have tried to capture the evolution of trust over time and consider the role of different contextual factors at early and late stages of the trust relationship [START_REF] Sillence | How do patients evaluate and make use of online health information[END_REF] including an analysis of the impact of those factors -such as personalised communication -that can help cement longer-term trust. Yet perhaps the most exciting new developments in trust research are moving beyond this simple transactional model of trust in information offered to capture a more complex set of parameters in relation to the ways in which we might use technology in the form of a trusted companion. To this end I have been working towards refining the idea of an electronic life partner -the Biometric Daemon [START_REF] Briggs | Biometric daemons: authentication via electronic pets[END_REF] -which would be capable of not only authenticating identity across a number of different platforms, but also acting as a trust agent. Intrinsic in the Daemon model is the notion that a relationship must be sustained over time and that both parties -Daemon and individual -are capable of learning about trust from each other and are similarly capable of seeking different forms of reassurance from each other.

1 Introduction

 1 Trust. . . is not a commodity which can be bought very easily. If you have to buy it, you already have some doubts about what youve bought[1, page 23]