Page 97 - Read Online

Page 90 Salmani et al. J Surveill Secur Saf 2020;1:79–101 I http://dx.doi.org/10.20517/jsss.2020.16

Table 1. Comparison of related works
Properties Curtmola et al [4] (2011) Cao et al [9] (2014) Liu et al [12] (2014) Xia et al [16] (2016) Guo et al [18] (2018) LRSE
Preserving access pattern No No No No No No
Server computation O(1) O(n) O(n) O(n) O(n) O(n)
Server storage O(n) O(n) O(n) O(n) O(n) O(n)
Communication O(1) O(1) O(n) O(1) O(1) O(1)
Preserving search pattern No Yes Yes No No Yes
Preserving co-occurrence terms No No No No No Yes
Boolean/multi-keyword search Boolean Multi Boolean Multi Multi Multi

5 PRIVACY AND PERFORMANCE ANALYSIS
Our main goal in this section is to prove the proposed schemes in Section 4 provide privacy and security, as
definedinSection2.1. Wealsoshowthatincomparisonwithrelatedworks, LRSEhasanacceptablecomplexity
in various criteria among previous SSE schemes (see Table 1). This property along with preserving the search
pattern and co-occurring terms demonstrate the efficiency of our scheme.

In Section 4.1 we explained that to preserve the user privacy, our goal is to make the document and query
vectors as uniform as possible (without compromising the efficiency). Hence, the cloud server is not able to
distinguish the high frequency keywords in the encrypted documents. Entropy measure can evaluate the uni-
formity of document vectors and is employed in many approaches [20–22] to evaluate the privacy. By comparing
theentropyoftheLRSEdocumentvectorswithoriginaloneswedemonstratehigherentropyandconsequently
higher privacy of the document vectors generated by LRSE.

5.1 Entropy of LRSE Document Vectors
We prove that by expanding the document vectors using our approach, privacy and security of the outsourced
data increases. Note that, adding dummy keywords [4,9] to extend the length of the data vectors does not
necessarily ensure an increase of the security, and in some case it may even decrease the privacy and security
of the outsourced data (see Example 1).

The main idea behind expanding/extending the length of the document vectors is to add more uncertainty to
document and query vectors, which results in higher entropy. Although, adding to the length of the document
vector can lead to higher entropy, in Example 1 we demonstrate that just extending the document vector’s
length does not guarantee having a more uniform vector and higher entropy.

Example1. Consideradocument D 1 with3keywords. Assumethefrequencyofeachkeywordin D 1 is (2,3,4),
so term-frequency(t f) vector is ( , , ). The entropy of this vector is equal to 1.06.
2 3 4
9 9 9
Now, to increase privacy and security to D 1, we add a new dummy keyword with the frequency of 15. The
2
modified frequency vector is (2,3,4,15) and the new term-frequency(t f) vector is ( , 3 , 4 , 15 ) The first im-
24 24 24 24
pression is because of adding a dummy keyword, the entropy increases; however the entropy of the new vector
is 1.059 which is less than the entropy of the original vector.
In Example 1 we showed that adding dummy keywords to the document/query vectors does not necessarily
providemoresecurity/privacy. Definingthepropertyofthenewdummykeywordsthatensureshigherentropy,
are not considered in the related literature and we leave it as a future work. However, in Theorem 1 we prove
that LRSE scheme provides more security/privacy.

Theorem 1. Given any document vector T i for document D i, valid in the LRSE scheme,

0
H(T i ) ≥ H(T i )
where H is the entropy measure and LRSE(T i ) = T i.
0