Databases Reference
In-Depth Information
Speeding up encrypted keyword data
The approach described above to search over encrypted text has a limita-
tion. Essentially, it requires
O
(
n
) comparisons (cryptographic operations) at
the server to test if the document contains a given keyword, where
n
is the
number of keywords in the document. While such an overhead might be tol-
erable for small documents and small document collections, the approach is
inherently not scalable. Authors in [18] overcome this limitation by exploit-
ing
bloom filters
for indexing documents. More details about the bloom filter
based approach can be found in [18, 21].
2.5 Search over Encrypted XML Data
While management and querying of XML data have been addressed exten-
sively, there has been relatively little work in the area of encrypted XML
data management [45, 34]. The new angle that becomes important in case of
XML data is the structural information in the data. In [45] the problem of
supporting XPath queries in the DAS model is considered where the under-
lying data is in XML format and propose a Xpath expressions based method
to specify
security constraints
(SCs). They distinguish between two kinds of
constraints, one where the goal is to hide the values at the tree nodes and
another where one needs to hide the association between different attributes.
For example, in a medical database containing patient data, an user might
want to protect the information of the following nature: The insurance infor-
mation of each patient; which SSN matches which patient's name; association
between patient and disease etc. Such constraints can be specified in the form
of XPath expressions and may be classified as either
node-type constraints
or
association-type constraints
. SCs can be enforced by hiding away the contents
of some subset of nodes in the XML tree by encrypting their content. When
association between two elements need to be hidden, encrypting any one of
the nodes can enforce the SC. The optimization problem then requires one
to determine a minimal set of nodes that need to be encrypted in order to
satisfy all the SCs. But [45] employs deterministic encryption schemes where
a plaintext value is always mapped to the same ciphertext. Deterministic en-
cryption is not secure due to its vulnerability to statistical attacks. To avoid
this the authors propose using decoy values to hide the true frequencies.
The query processing follows the typical DAS approach we outlined in
the previous sections, wherein some metadata is stored on the server along
with the encrypted data to enable server-side query processing. The authors
propose using two indexes, one is the
structural index
to enable tree traversal
and the second one is a
value index
for enabling attribute value based queries
like range queries. The former is called the
discontinuous structural interval
(DSI) index
, which associates each node of the tree with intervals from a
range of an ordered domain (e.g., from [0
,
1]). The interval sizes are chosen in
a random manner so as not to give away any information about the number
