Abstract: many cryptographic techniques have been proposed. These

Abstract:  Cloud computing is a shared collection of
computing resources, where data can be provided on request through internet.
Cloud should be responsible for accountability of customer data. To ensure
privacy and security of user data, many cryptographic techniques have been
proposed. These include searchable encryption(SE), use of an encrypted index
tree, trapdoor, multi-keyword search, ranking the searched files based on
relevance score etc. In this paper, the technique that uses ECC/B+ tree is
tested for multi-user environment. It is observed that ECC/B+ tree search technique
computation time is approximately 1.60 sec for 5 users whereas it takes just
approximately 1.63 sec for 20 users. Further,
with 5 keywords, the CPU utilization is found to be around 3% for 1 user and around
4.2% for 5 users. The study is carried out using Microsoft azure platform.

computing, Multi-user, Searchable Encryption, Elliptic Curve Cryptography,
Microsoft Azure, B+ tree

1.      Introduction


definitions and interpretations of “cloud computing” exist depending on the extent
of usage. The National Institute of Standards and Technology (NIST) and Mather
et al. 1 provide a working and official definition of cloud computing 2. “Cloud
Computing is a model for enabling ubiquitous, convenient, on-demand network
access to a shared pool of configurable computing resources (e.g., networks,
servers, storage, applications, and services) that can be rapidly provisioned
and released with minimal management effort or service provider interaction”.
In 1 and 3 cloud computing is defined as a platform or infrastructure in
which dynamically scalable (elastic) resources are provided as a service
through internet, enabling users to process the data outside the boundaries of
the company, providing economic benefits through virtualized and shared
infrastructure without the need of expertise nor knowledge over the underlying


PAAS, IAAS are service delivery models of cloud, through which end users get
benefit of required service at low cost and with minimum management efforts. Cloud
stands on trust between user and provider. To maintain trust cloud needs to
provide privacy and security of user data 4. Many techniques have been
developed to solve the issues related to security and privacy of data. Cryptography
is one such efficient technique. The encrypted data is outsourced to cloud. By
using an efficient technique like searchable encryption, authorized users can
retrieve their private data without any loss of security and privacy.


this paper the ECC/B+ tree scheme 19 is tested for scalability by allowing
multiple users to search simultaneously using multiple keywords on encrypted
data. The performance in terms of CPU utilization and search time under multi-user
environment is compared with its performance for single user.


1.      Literature Review

5, authors have proposed practical symmetric searchable encryption method. In
this scheme the file is encrypted word by word. To search for a keyword, user
sends the encrypted keyword and the key to the cloud. This key shall be used to
operate on the encrypted user data and then decrypted keyword shall be used to
search in decrypted data. The drawback of this scheme is that the word
frequency will be revealed. In 6, the first public key encryption with
keyword search (PEKS) was proposed that lead to asymmetric searchable
encryption method. The scheme suffers from
inference attack (illegitimate knowledge of data in cloud) on trapdoor searchable
encryption method. In 7 8, different techniques
that work on encrypted data were discussed, along with comparative study of
different searchable and homomorphic encryption schemes. 


These existing solutions are not sufficient to protect data in cloud from unauthorized
users because of low degree of transparency. Since the cloud user and the cloud
provider are in the different trusted domain, the outsourced data may be
exposed to the vulnerabilities 10 11 12 13 14 15. To preserve the
data privacy we need to design a searchable algorithm that works on encrypted
data 16. The search techniques may use single keyword or multiple keywords
17. In larger database the search may result in many documents to be matched
with keywords. This causes difficulty for a cloud user to go through all
documents. Search based on ranking is another solution, wherein the documents
are ranked based on their relevancy to the keywords 18.


searchable encryption related studies, computation time and computation
overhead are the two most frequently used parameters for analyzing the
performance of their schemes. Computation time (also called “running
time”) is the length of time required to perform a computational process
for example searching a keyword, generating trapdoor etc. Computation overhead
is related to CPU utilization in terms of resource allocation measured in time. Thus, an effective high performance multi-keyword ranked
search over the encrypted cloud data is required. In
9 19, authors have proposed & analyzed performance of two efficient searchable
encryption schemes: CRSA/B+ tree and ECC/B+ tree.


this paper, the performance of ECC/B+ tree is analyzed under multi-user
environment and compared the same with single user.




Searchable Encryption technique is a
cryptographic method to maintain the security and privacy of client’s data in
cloud environment. The searchable encryption scheme involves multiple
techniques like cryptography, searching, internet, cloud data base etc. Mainly the architecture of searchable encryption consists of 3 actors,
i.e., the data owner, data user and the cloud server as shown in Figure 1.


Figure 1: Architecture of SE Scheme

As is clear from Figure 1, the different steps
involved in the working of our proposed searchable encryption scheme 19 for multi-user
environment are as follows: 1. Encrypted data files along with encrypted index
file are uploaded to cloud server by data owner. B+ tree data structure is used
for indexing keywords and to search. ECC algorithm is considered for encryption
of both data files and index tree. 2. Multiple data users search for the
relevant files in encrypted cloud dataset by sending encrypted keywords
(trapdoor) simultaneously. The encrypted keywords preserve the security and
privacy of user data in cloud. 3. Cloud server uses encrypted keywords
(trapdoor) sent by multiple data users for searching relevant data files.4. The
resultant relevant data files are ranked based on relevance score and sent to
the data users.


In our proposed scheme 19, the research goals
included 1) Ranked keyword search: to explore different mechanisms for
designing effective ranked search schemes based on the existing searchable
encryption framework; 2) Security guarantee: to prevent cloud server from learning
the plaintext of either the data files or the searched keywords, and achieve
the “as-strong-as-possible” security strength compared to existing searchable
encryption schemes  3) Efficiency: to
study its performance in terms of computation time and computation overhead
with single user. We could observe that ECC/B+ tree scheme outperformed CRSA/B+
tree 9 for computation time & computation overhead. Looking into this
improvement we thought of studying its performance under multi-user environment
which is the objective of this research work.


3.      Searchable
encryption search framework for multiuser environment using ECC/B+ tree


Here the B+ tree algorithm is proposed which enables effective,
efficient and secure multi-user, multi-keyword ranked search over encrypted
cloud data. The architecture of multi-user search scheme is shown in Figure 2.

Figure 2:  Microsoft Azure Multi-user
Search Architecture

The searchable encryption utilizes a similar application of keyword
search provided by the

hence it could be said that the searchable encryption depends on the
availability of the keyword search application offered by the

workers. Multi-keyword search management
tends to be cumbersome if it is done manually. In order to automate the
multi-keyword search management we need a common syntax and a common searchable
encryption to interoperate. Here, we introduce the searchable encryption
through the Elliptical curve cryptographic method. The working of the B+ tree
search algorithm is as follows.

Firstly the cloud user will upload the contents on to the cloud.
Whenever the user wants to retrieve the data based on the user’s requirement,
the user will search through the documents with the set of keywords and
retrieves the required document. The user may input many keywords to search a
document. The set of all multi-keyword search is represented by

. The

represents the

search keyword in many keywords. The tree
structure algorithm consists of the encrypted tree data

, the encrypted keyword contents

 and the tree builder function

. The

derived from both the encrypted tree data

 and the encrypted keyword contents

of the Tree Structure Algorithm (TSA).

 is the contents derived from the


 by the tree builder function

. The tree builder function
extracts all the related keywords of

 present in the encrypted tree data

the TSA.

The workers in the B+ tree provide search encryption services which
support the multi-keyword search application. The workers are represented as


is the

 search provided by the worker. Each search
provided by the worker possess the encrypted tree data based documents/records
represented by


 is the

 encrypted tree data record available with the
azure cloud search provided by the worker

 on the

 search. The encrypted keyword contents of

 encrypted tree data records is given by

. The implementation of
all these are as follows.




 are the encrypted set available

search service provided by the worker.

The locally available encrypted data could be defined as 


In the current search deployments available, there exists a problem
where the encrypted data available with search service

 provided by the worker may not contain all the
possible keywords as the complete encrypted tree data set

. The purpose of the B+ tree is to
overcome the short comings by using efficient searching algorithms and search
encryption compositions.

The data of the cloud search provided by the worker
constitutes of both the encrypted tree data and encrypted keyword contents
which are humongous in nature and size. A search executed on huge databases
would affect the response times due to numerous disk read and disk write
operations involved in the search operation. To compress the data and create
cache the B+ tree utilizes a hierarchical data ordering algorithm.


Based on the record,

could be represented as
mentioned above which are
said to consist of triplets.


is the subject triplet,

 is the predicate triple and

 represents the object triplet.

The keywords extracted from the encrypted tree data
include some complex relations that cannot be represented in encrypted tree
data alone; hence the B+ tree presented here adopts representation of the
encrypted keyword contents through tree structure builder due to its benefits.

As the number of keywords increases, greater the
relations that exist, larger is the data size and increasing the number of disk
operation for the search operation. The number of occurrences of a keyword in
an encrypted data is directly proportional or equivalent to the number of

 of a keyword. It can be said that the number
of relations

of a keyword

and a function of the
tree depth

 of a keyword

 is equivalent to a constant

. Even if the number of

of a keyword

increases, the cache size
does not increase by a great extent.

The cloud space required to store the keyword

 is given by

. The space utilized in
storing the cache defined above is given by

The keywords require

cloud storage space per
keyword (

) and also only one entry
of a

 keyword is allowed in the cache. To compare
the normal caching strategy with the caching strategy used in B+ tree search,
the comparison ratio is established as

Hence the proposed caching strategy improves the cloud
storage space utilization by approximately


The azure cloud access cost for the caching strategy
is defined as


The probability of

 finding the keyword

in the encrypted data is
defined as

The access time of the cache to search for a keyword

within the encrypted data
with a probability

is defined as


 represents the branching factor of the
encrypted tree.

The cache created based on the encrypted tree data and
encrypted keyword content is encoded in a binary format for faster access. The
encrypted relevance score is a ratio between the query keyword and the response
keyword based on the encryptions constructed. The encrypted relevance score is
used by the Search Application in ranking the search responses received by the

service provided by workers considered in the B+ tree search.

The search query

 could be defined as a set of keywords and
relational operators. The search query

 could be represented as a


the number of keywords queried for and

the number of relations, logical operators and special characters defined for
querying amongst the

The search response

also be represented as a


number of responses obtained for the search query in

The encrypted relevance score is represented




Normalization is considered to represent the encrypted
relevance score to a scale of


The encrypted relevance score is


Let us consider search keyword set

 and two keywords


. There exists 4 possible
relations amongst keywords


. The possible relations
could be defined by using the subsume represented by

and defined as



 represents the conditional true relation and

represents a
conditionally false relation.

Let us consider a parameter

of the search service
provided by the worker

and a parameter

of the search service
provided by the worker

. If the parameters

 then the cloud search service could be called
if only



represents the 

 cloud search service offered by search service
provided by the worker


Each cloud search service offered by search worker

 required a set of inputs denoted as

if the set of inputs is provided in an orderly fashion the cloud search service provides a set of output
keywords denoted by


. The efficient ranked
keyword search cloud service composition algorithm discovers the cloud search
services available on

. Let
the ranked keyword search cloud service composition be
represented as

  then the cloud search service composition is
said to successfully process all the requests if


 represent a service provided by worker on
search function based on a keyword

which provides all
the set of cloud search services available defined as




Also it
could be stated that


Let us define a function

 which performs the

tree search
algorithm is defined as




 represents the input query set,

 is the desired response,

represents the
current temporary cloud services identified,

 represents the height and

represents the
resultant cloud service identified.




The privacy preserved multi-user, multi-keyword search based on the
encrypted cloud data has been implemented. The system model presented has been
developed on Visual Studio 2010 framework 4.0 with C#. The overall system has
been developed and implemented with Microsoft Azure platform. Different
parameters like computation overhead, computation time have been considered to analyze
and compare the performance of multi-user scheme of ECC/B+ tree with single-user
scheme 19.


Computation Overhead (CPU Utilization): Figure 3 depicts the
computation overhead in percentage based on the number of keywords for multi-user
environment. The performance based comparison is done between multi-user
scheme (up to 5 keywords, 5 users) of ECC/B+ tree with that of single user
scheme (up to 5 keywords, 1 user) 19. Results clearly show that, the
computation overhead using ECC/B+ tree single user scheme is low as compared to
ECC/B+ tree multi-user scheme. For example, ECC/B+ tree single user scheme 19
with 5 keywords takes approximately 3% of cpu time,  whereas it takes approximately 4.2% of cpu
time for 5 users and 5 keywords.



Figure 3: Computation


Computation Time: Figure 4 shows the computation time in
seconds against up to 5 keywords for analysis. As per the experimental result the computation time for ECC/B+ tree
single user scheme 19 takes less time compared to our ECC/ B+ tree multi-user
scheme. Here the computation time for 5 keywords and 5 users in multi-user environment
takes approximately 1.7 secs, whereas for single user environment it takes
approximately 1.5 sec, reduced by 0.2 sec.



4: Computation time for keyword search

Computation Time (ECC/B+ Tree multi-user): Figure 5
depicts the computation time in seconds based on the number of users for multi-user
environment. Here, we considered max of 5 users. We studied the performance of ECC/B+ tree for multi-user environment with
5 keywords. The result clearly shows that
ECC search computation time is increased when we increase the number of users. For example the
computation time required for 3 users is 1.6 sec whereas the same for 5 users
is 1.8 sec.  From Figure 5, it is clear
that as the number of users increased the computation time also increases.



Figure 5: Computation
time for ECCB+ Tree multi-user


Average Computation time (ECC/B+ tree
multi-user): As depicted in Figure 6,
the average search computation time for multi-user ECC/B+ tree scheme increases
with the increase in number of users (5,10.15,20), however, the increase in
time is negligible. For example for 5 users the average time is 1.60, whereas
the average search time for 20 users is 1.63.



Figure 6: Average computation
time ECC/B+ tree multi-user

     6. Conclusion


The insights of privacy-assured searchable cloud data storage
services are discussed in this paper. Despite the attractiveness of cloud
services and their extensive realization by enterprises and governments, cloud
providers are deficient in services that guarantee both data privacy and
privacy preserving search operation on encrypted data. The proposed algorithm
in 19 is tested for its scalability by allowing multi-user environment and
its performance is studied through analytical model in
this current work.


analysis which examines the privacy and search efficiency of proposed model
19 with multi-user environment is given. The experimental results prove that
our proposed model 19 with multi-user environment induces low overhead on the
overall system. Using the ECC, the computation overhead and byte overhead is
much reduced compared to other cryptographic methods. Based on this
comprehensive performance analysis, we conclude our scheme using ECC/B+ tree is
more secure, efficient and practical than existing schemes and also can be used
for multi-user environment.