Databases Reference
In-Depth Information
Encoding
Document ID
T
1
00101
d
….
T
k
T
k+1
….
T
l
r
0
Random Seq
01100
=
….
….
1101
d
T
l+m
r
1
0100
=
Fig. 6.
Supporting deletions from a trustworthy inverted index. The term encoding
E
i
stored in each posting element has been XORed with a random sequence. The
random sequence is stored in a separate file that is discarded when the record expires.
Each posting list entry must also mention which random sequence to use to decrypt
the encrypted term encoding (not shown).
required record deletion rate in the future. Thus this option is too expensive
to be practical.
If document identifiers are encrypted with a per-document secret key be-
fore being stored in the index, one can still perform a join on the encrypted
document identifiers to recover the document contents. Encrypting the docu-
ment identifiers with a single key for each epoch is also problematic; Section
5 of [50] offers some solutions for the case of generalized hash trees.
An alternative for trustworthy inverted indexes is to merge posting lists
together as usual, then encrypt the term encoding associated with each posting
element and store it in the merged posting list entries (see Figure 6). One
possible encryption technique is to replace the keyword encoding
E
in the
posting element with its XOR with a random secret, which can be stored
with the record and deleted upon its expiration. While the key is present (the
record has not expired), the encoding
E
can be extracted from the posting
element. Once the secret has been deleted, the keyword encoding
E
cannot
be retrieved from the stored XOR value. The adversary will not be able to
determine which of the
q
merged keywords corresponds to the posting element,
after the secret is discarded.
We can generalize this scheme to handle multiple keywords per record,
in such a manner that an adversary cannot determine which of the merged-
together keywords a specific posting element corresponds to. The scheme does
not achieve strongly secure deletion, though it is immune to a variety of pos-
sible attacks. Moreover, the scheme allows compression of posting list entries
and has a modest space overhead. It does not require the records to be dis-
posed of in epochs, and hence it can support litigation holds. However, the
