10 Secure Outsourcing of Geographical Data
221
words can then be outsourced to the third-party. According to this scheme, when a
user needs to search for a keyword W, it generates the encrypted word E k (W) and
computes E k (W) ⊕ S , where S is the corresponding pseudorandom number. This
simple scheme allows the third-party to search for keyword W in the encrypted data,
by simply looking for E(W) ⊕ S , thus without gaining any information on the clear
text. Since occurrences of the same word are combined using the exclusive OR operator with different pseudorandom numbers, by analyzing the distribution of the
encrypted words, no information could be inferred regarding the clear text. According to the above-introduced basic scheme, to formulate a query, users need to know
information about the pseudorandom numbers. Indeed, the scheme proposed in [26]
is defined in such a way that users are able to locally compute pseudorandom numbers without any interaction with the data owner. Let us see in more detail how the
scheme works. In what follows, we briefly summarize the encryption and query evaluation process proposed by Song et al., and also we refer the readers interested in the
decryption process to [26]. The scheme exploits a symmetric encryption function E()
and two pseudorandom number generator functions, namely F and f .
4 Given as input a set of clear-text words W 1 , W 2 , . . . , W l , with the same length n,
5 the encryption
process implies the following steps:
• Data owner generates a sequence of pseudorandom values S 1 . . . S l of length
n−m; parameter m can be properly adjusted to minimize the number of erroneous
answers due to collision of pseudorandom number generators F() and f ().
• For each word W j , the outsourced ciphered word C j is generated according to
the following formula: C j = E k (W j )⊕ < S j , F K j (S j ) >, where K j = f k (FB j ) and
FB j denotes the first n − m bits of E k (W j ).
Let us see now how by having only a set of ciphered words, the third-party is
able to search an encrypted word. When a user needs to search for a keyword W i ,
he/she sends the third-party E k (W i ) and key K i , which can be locally computed by
the user. Then, for each outsourced ciphered word C i , the third-party (1) calculates
C i ⊕ E k (W i ); (2) takes the first n − m bits bts of the resulting value, and computes
F K i (bts), where K i is the key received by the user; (3) if the result of F K i (bts) is equal
to the n − m + 1 remaining bits, then the ciphered word C i is returned. Indeed, if C i
contains the searched encrypted word, then E k (W i )⊕ < S i , F K i (S i ) > ⊕E k (W i ) <
S i , F K i (S i ) >, for the properties of the XOR operator.
10.3.2 Authenticity and Integrity
Authenticity and integrity are usually enforced through the use of digital signatures
[27]—one of the most widely used techniques relying on asymmetric encryption.
4 In what follows, we denote by E k (x) (F k (x), f k (x), respectively) the result of applying E
(F, f , respectively) to input x with key k.
5 This set of words can be obtained by partitioning the input clear-text into atomic quantities
(on the basis of the application domain) and by padding and splitting the shortest and
longest words.
221
words can then be outsourced to the third-party. According to this scheme, when a
user needs to search for a keyword W, it generates the encrypted word E k (W) and
computes E k (W) ⊕ S , where S is the corresponding pseudorandom number. This
simple scheme allows the third-party to search for keyword W in the encrypted data,
by simply looking for E(W) ⊕ S , thus without gaining any information on the clear
text. Since occurrences of the same word are combined using the exclusive OR operator with different pseudorandom numbers, by analyzing the distribution of the
encrypted words, no information could be inferred regarding the clear text. According to the above-introduced basic scheme, to formulate a query, users need to know
information about the pseudorandom numbers. Indeed, the scheme proposed in [26]
is defined in such a way that users are able to locally compute pseudorandom numbers without any interaction with the data owner. Let us see in more detail how the
scheme works. In what follows, we briefly summarize the encryption and query evaluation process proposed by Song et al., and also we refer the readers interested in the
decryption process to [26]. The scheme exploits a symmetric encryption function E()
and two pseudorandom number generator functions, namely F and f .
4 Given as input a set of clear-text words W 1 , W 2 , . . . , W l , with the same length n,
5 the encryption
process implies the following steps:
• Data owner generates a sequence of pseudorandom values S 1 . . . S l of length
n−m; parameter m can be properly adjusted to minimize the number of erroneous
answers due to collision of pseudorandom number generators F() and f ().
• For each word W j , the outsourced ciphered word C j is generated according to
the following formula: C j = E k (W j )⊕ < S j , F K j (S j ) >, where K j = f k (FB j ) and
FB j denotes the first n − m bits of E k (W j ).
Let us see now how by having only a set of ciphered words, the third-party is
able to search an encrypted word. When a user needs to search for a keyword W i ,
he/she sends the third-party E k (W i ) and key K i , which can be locally computed by
the user. Then, for each outsourced ciphered word C i , the third-party (1) calculates
C i ⊕ E k (W i ); (2) takes the first n − m bits bts of the resulting value, and computes
F K i (bts), where K i is the key received by the user; (3) if the result of F K i (bts) is equal
to the n − m + 1 remaining bits, then the ciphered word C i is returned. Indeed, if C i
contains the searched encrypted word, then E k (W i )⊕ < S i , F K i (S i ) > ⊕E k (W i ) <
S i , F K i (S i ) >, for the properties of the XOR operator.
10.3.2 Authenticity and Integrity
Authenticity and integrity are usually enforced through the use of digital signatures
[27]—one of the most widely used techniques relying on asymmetric encryption.
4 In what follows, we denote by E k (x) (F k (x), f k (x), respectively) the result of applying E
(F, f , respectively) to input x with key k.
5 This set of words can be obtained by partitioning the input clear-text into atomic quantities
(on the basis of the application domain) and by padding and splitting the shortest and
longest words.