Page 100 - Read Online

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

for w i (case 1). However, if f i ≤ φ i (case 2), D 3 may get excluded from the results due to not possessing the
same versions that are employed in the query q. If k is set to 1,2, or 3, this issue does not effect the result
accuracy because the user is only interested in the first top-k documents and d 3 will not be placed in the top-k
list. The problem occurs when users demands all of the documents containing w i (case 4).

To tackle this challenge (case 4), in Scheme I, we can inject the missed ciphertexts in the corresponding docu-
ments. In Scheme II, we do not even need to touch the encrypted documents; the only action is to adjust the
corresponding document vectors regarding the missed ciphertexts. In order not to effect the relevance score,
we employ the same strategy the related literature employs by adding dummy keywords while not affecting the
relevance score [9,14] .

5.4 Security
The secure asymmetric inner product [14] is widely used in many existing secure search schemes [9,10,16,18,24]
and it has been proved to be secure in known ciphertext attacks. In this section we show that chaining the
ciphertexts are not weakening the underlying secure symmetric encryption scheme; and we give the security
proofs for the schemes presented in Section 4.

[4]
Definition8. (Symmetricencryptionscheme) . Asymmetricencryptionschemeisasetofthreepolynomial-
time algorithms (G,ξ,D) such that G takes an unary security parameter k and returns a secret key K; ξ takes
a key K and n-bit message m and returns ciphertext c; D takes a key K and a ciphertext c and returns m if K
was the key under which c was produced. We refer to Curtmola et al. [4] for formal definition of security for
symmetric encryption schemes.
Definition9. (Indistinguishability). Let G and E betworandomvariablesdistributedon {0,1} . ASSEscheme
n
n
is indistinguishable secure if for all non-uniform probabilistic polynomial-time adversaries A : {0,1} →
{0,1},forallpolynomial“poly”andallsufficientlylarge k thedistinguishableprobability(alsocalledadvantage
of adversary) is:

1
AdvA = | Pr[A(G)] − Pr[A(E)]| ≤ (4)
poly(k)
Definition 10. (Novel chaining notion). Let (G,ξ,D) be an indistinguishable secure symmetric encryption
scheme with ξ : {0,1} ×{0,1} → {0,1} . Let w i ∈ {0,1} be a keyword in the dictionary ∆ d. Given a natural
n
k
n
n
number of ℓ The novel chaining notion of w i (NCN(w i )) is defined as:
(1) (2) (ℓ)
NCN(w i ) = (NCN (w i ), NCN (w i ), . . ., NCN (w i ))
where , NCN (w i ) = ξ(w i ),
(1)
(j)
and NCN (w i ) = ξ(w i ⊕ NCN (j−1) (w i )) ∀j ∈ {2,. . .,ℓ}.
Theorem 2. The novel chaining notion is indistinguishable secure against known plaintext attack.

k
Proof. Let (G,ξ,D) be the an indistinguishable symmetric encryption scheme. Moreover, recall ξ : {0,1} ×
{0,1} → {0,1} , so an encrypted vector V is a valid vector as an input for ξ (because both encrypted (V) and
n
ˆ
ˆ
n
plain (V) vectors are in {0,1} ). Hence for any w i in the dictionary ∆ d and for any j, NCN (w i ) is in {0,1} .
n
n
j
Since (G,ξ,D)isindistinguishablesecurescheme,theattackerisnotabletofindanyrelationbetweeninputand
[4]
output except for a negligible amount , so the outputs is independent of the inputs, otherwise the encryption
(1) (1)
function (ξ) is not indistinguishable. Hence, keyword w i is independent from NCN (w i ) and NCN (w i )
(2) (j)
is independent from NCN (w i ). Now we have to prove that every pair of the chains such as NCN (w i )
and NCN (j+i) (w i ) is indistinguishable. By contradiction, let’s assume NCN (w i ) and NCN (j+i) (w i ) are distin-
(j)
(j)
guishable,theneventhepairwise NCN (w i )and NCN (j+1) (w i )isdistinguishabletoo,whichisacontradiction.
Therefore, NCN(.) is secure.