Lecture
Song’s scheme — an algorithm implementing encryption and search over encrypted data. Developed by Dawn Xiaodong Song, David Wagner, Adrian Perrig.
This work was part of a master's thesis at the Dresden University of Technology, supervised by Dr. Josef Spillner and Martin Beck.
In this paper the authors develop a set of algorithms that make it possible to search over encrypted data. These algorithms provide linear-time search (O (n)) per document and introduce relatively small space overhead. Proofs of security for their model are also included, showing that the server hosting the data “can learn nothing about the plaintext, given only the ciphertext.”
Let us first define the problem of searching over encrypted
data.
Suppose Alice has a collection of documents and stores them
on an untrusted server, Bob. For example, Alice might be a
mobile user who stores her email messages on an untrusted
mail server. Since Bob is not trusted, Alice wants to encrypt her documents and keep only the ciphertext on Bob's server.
Each document can be split into «words». Each word
can be any token; it could be a 64-bit block, an English
word, a sentence, or some other atomic unit, depending
on the application domain of interest. For simplicity we generally assume that these «words» are all of the same length (otherwise
we can either pad the shorter «words» or split the longer «words»
so that all "words" have the same length, or use some
simple extensions for variable-length «words»; see also Section 5.3). Since Alice may have only a low-bandwidth
network connection to Bob's server, she wants only to
retrieve the documents containing a given
word. To achieve this we need to design a scheme so that,
after performing certain computations on the ciphertext,
Bob can determine with some probability whether each document contains the
word, without learning anything else.
There seem to be two types of approaches. One possibility is to build an index that, for each word
of interest,
lists the documents containing it
. An alternative is to perform a sequential scan without an index. The advantage
of using an index is that it can be faster than a sequential
scan when the documents are large. The disadvantage
of using an index is that maintaining and updating the index can incur
substantial overhead. So the index-based approach
is better suited to data intended mainly for read-only access.
We first describe our scheme for searching over encrypted
data without an index. Since index-based schemes appear
to require less complex constructions, we defer
the discussion of index-based search to the end of the
paper (see Section 5.4)
Our scheme requires several fundamental primitives
from classical symmetric-key cryptography. Because we will
prove the security of our scheme, we use only primitives with
a well-defined notion of security. We list the necessary primitives here and also review the standard security definitions for them. The definitions can be skipped
on a first reading by those not interested in our theoretical
security proofs.
We adopt standard security definitions from
the provable-security literature, and we measure the strength
of cryptographic primitives in terms of the resources
needed to break them. We say that an attack breaks
a cryptographic primitive if the attack algorithm succeeds
in breaking the primitive with the stated resources, and
we say that a cryptographic primitive is secure if no algorithm can break it. Let
A be an arbitrary algorithm,
and let X and Y be random variables. The distinguishing probability
— sometimes called the advantage — for A and
is
our list of necessary primitives is as
follows: 1. A pseudorandom generator, i.e., a
stream cipher. We say that a generator
G is a (T, ε)-secure pseudorandom generator
if every algorithm with running time at
most T has advantage Adv < ε.
The adversary's advantage is defined as
are random variables distributed uniformly over the
domain. 2. A pseudorandom function F. We
say that F is a (T, q,
ε)-secure pseudorandom function if every oracle algorithm
makes at most q oracle queries and
has running time at most T and
has advantage Adv < ε. The advantage
is defined as Adv = |Pr[A^f_K() =
1] − Pr[A^R() = 1]|, where R
represents a random function chosen uniformly from
the set of all maps from the
domain to the range, and where the
probability is taken over the choice of
K and R. 3. A pseudorandom permutation,
i.e., a block cipher. We say that
a family of permutations E is a
(T, q, ε)-secure pseudorandom permutation if
every oracle algorithm makes at most
q queries to the oracle and
has running time at most T
and has advantage Adv < ε.
The advantage is defined as Adv
= |Pr[A^E_K() = 1] − Pr[A^π()
= 1]|, where π represents a
random permutation chosen uniformly from the
set of all bijections on the
domain, and where the probability is
taken over the choice of K
and π. Note that the adversary
is given an oracle for both
encryption and decryption; this corresponds to
an adaptive chosen-plaintext/chosen-ciphertext attack model. In
general, the intuition is that (T,
q, ε)-security represents resistance to attacks
using at most T offline work
and at most q adaptive chosen-text
queries. Of course, there is no
fundamental need for three separate primitives,
since in practice all three can
be built from a single standard
primitive. For example, given any block
cipher, we can build a pseudorandom
generator using counter mode, or a
pseudorandom function using CBC-MAC. We will
use the following notation. If F
is a pseudorandom function or permutation,
we write the result of applying
it to an input using key
K. We write x||y for
the concatenation of x and
y, and x⊕y for the
bitwise XOR of x
and y. For the
remainder of the paper
we let G be
a pseudorandom generator for
some l, let F
be a pseudorandom function,
and let E be
a pseudorandom permutation. Typically
we will have F:
{0,1}^k × D →
R, and E: {0,1}^k
× D → D.
In this section we present our solution
for searching with sequential scanning. We start
with a basic scheme and show that
its encryption algorithm provides provable secrecy. We
then show how the first scheme can
be extended to handle controlled search and
hidden search. We describe our final scheme,
which satisfies all the properties mentioned earlier,
including query isolation, at the end. 4.1
Scheme I: The Basic Scheme Alice wants
to encrypt a document containing a sequence
of words W = (W_1, W_2, ...,
W_n). Intuitively, the scheme works by computing
the bitwise exclusive-OR (XOR) of the plaintext
with a sequence of pseudorandom bits having
a special structure. This structure will make
it possible to search over the data
without revealing anything else about the plaintext.
More specifically, the basic scheme works as
follows. Alice generates a sequence of pseudorandom
values S = (S_1, S_2, ..., S_n)
using some stream cipher (namely, the pseudorandom
generator G), where each S_i has length
m bits. To encrypt the m-bit
word W_i appearing at position i,
Alice takes the pseudorandom S_i, sets
X_i = W_i
⊕ S_i, and
outputs the ciphertext
C_i = X_i,
so that only Alice can decrypt. Note
that only Alice can generate the pseudorandom
stream S = (S_1, ..., S_n)
for X_1, ..., X_n, so that no
one else can decrypt. Of course, encryption
can be performed online, so that we
encrypt each word as it becomes available.
There is some flexibility in how the
keys K_i can be chosen. One possibility
is to use the same key at
every position in the document. Another option
is to choose a new key K_i
for each position independently of all other
keys. More generally, at each position Alice
can either (a) choose K_i to be
the same as some earlier K_j (j<i),
or (b) choose K_i independently of all
previous keys. We will see later how
this flexibility lets us support a number
of interesting features. The basic scheme
provides provable secrecy if the pseudorandom
function F and the pseudorandom generator
G are secure. By this we
mean that at every position where
K_i is unknown, the values X_i
are indistinguishable from truly random bits
to any computationally bounded adversary. We
formalize the theorem below. Theorem 4.1.
If F is a (T, q,
ε)-secure pseudorandom function, and G is
a (T, ε')-secure pseudorandom generator, and
if the key material is chosen
as described above, then the sequence-generation
algorithm described above, S = (S_1,
..., S_n), is a (T', q,
ε'')-secure pseudorandom generator, where ε'' is
at most ε + n·ε', and
T' is a constant factor smaller
than T. In other words, we
expect the basic scheme to be
good for encrypting up to roughly
max(…) words, if the pseudorandom function
and pseudorandom generator are sufficiently secure.
See Appendix A for a more
precise statement of the theorem and
the full proof. The basic scheme
supports search over the ciphertext as
follows: if Alice wants to find
the word W, she can tell
Bob F and the K_i corresponding
to every position where the word
W may occur. Bob can then
search for W in the ciphertext
by checking whether X_i XOR S_i
is of the form C_j =
F_K(j) for some j. Such a
search can be performed in linear
time. At positions where Bob does
not know K_i, Bob learns nothing
about the plaintext. Thus the scheme
permits a limited form of control:
if Alice only wants Bob to
be able to search over the
first half of the ciphertext, Alice
need only reveal the K_i corresponding
Figure 1. The basic scheme to these
positions, and none of the K_i used
in the second half of the ciphertext.
As described above, the basic scheme is
not entirely satisfactory: if Alice wants to
help Bob find the word W, either
Alice must reveal all the K_i (thereby
potentially revealing the whole document), or Alice
must know in advance at which positions
W may occur (which seems to defeat
the purpose of remote search). However,
we will see next how to
solve this problem. 4.2 Scheme II:
Controlled Search Let F' be an
additional pseudorandom function to be introduced
independently of K. The basic idea
is to choose our keys as
K_i = F'_K(W_i). We require that
K be chosen uniformly at random
by Alice and never revealed. Then,
if Alice wishes to allow Bob
to search for the word W,
she reveals F' and K_i to
him. This lets Bob determine all
the positions where W may occur,
but reveals nothing about positions where
W does not occur. This achieves
our desired goal of controlled search.
We show the correctness of this
approach in the following theorem. Theorem
4.2. Suppose F is a (T,
q, ε)-secure pseudorandom function, F' is
a (T, q, ε)-secure pseudorandom function,
and G is a (T, ε')-secure
pseudorandom generator. If the key material
is chosen as described above, then
the sequence-generation algorithm described above, S
= (S_1, ..., S_n), will be
a (T', q, ε'')-secure pseudorandom generator,
where ε'' is at most 2q·ε
+ n·ε', and T' is a
constant factor smaller than T. This
shows that our controlled-search scheme is
roughly as good as the basic
scheme, provided the underlying primitives are
secure. See Appendix A for the
proof, as well as a more
precise statement. Various extensions of this
idea are possible. If the document
to be encrypted consists of a
series of chapters, an alternative
approach is to generate a
key K_i per word by
hashing the chapter number j
and the position i as
K_j,i = F''(j '' i).
This lets Alice control
which chapters Bob may
search, as well as
control which words Bob may search.
We can develop this idea further
by using a hierarchical key-management scheme.
Alice sets K_1 and K_2 for
the two halves of the key.
Then she can reveal either (1)
F'(K_1, j) for each chapter of
interest, or (2) K_1 itself, if
she wishes to briefly allow Bob
to search across all chapters.
This scheme still does not
support hidden search queries: for
Bob to be able to
find the position where the
word W occurs, Alice must
reveal W to Bob. We
will see next that this
problem can be easily solved
once and for all.
Suppose Alice now wants to ask Bob to find
the word W, but she does not wish to
reveal it to Bob. We propose a simple
extension to the scheme above to support this
goal. Alice should simply pre-encrypt each word W_i
of the plaintext separately using a deterministic encryption
algorithm π. Note that no randomness may be
used, and the computation of π may depend
only on W_i and must not depend on
the position in the document where W_i is
located. So we can think of this pre-encryption
step as ECB-encrypting the words of the document
using some block cipher. (Of course, if a
word is very long, internally the map π
could be implemented by CBC-encrypting W_i with a
fixed IV or some other method, but the
point is that this process must be the
same at all positions in the document.) L_i
= π(W_i). After the pre-encryption
phase, Alice has a
sequence of pre-encrypted words
L = (L_1, ...,
L_n) . She now
post-encrypts this sequence using
the stream-cipher construction described
above to obtain X_i
= L_i ⊕
S_i and S_i,
where S_i
= G_{K_i}(l)
and K_i
= F'_K(i).
To search
for the
word W,
Alice computes
L =
π(W) and
computes L = π(W) and sends
L to Bob. Note that this
Figure 2. The hidden-search scheme allows
Bob to search for W without
revealing W itself. It is easy
to see that this scheme satisfies
the hidden-search property, if the pre-encryption
is secure. 4.4 Scheme IV: The
Final Scheme Careful readers may have
noticed that Scheme III actually suffers
from a minor flaw: if Alice
generates the keys K_i as
K_i = F'_K(i), then Alice can
no longer recover the plaintext from
the ciphertext alone, because she needs
to know W_i (more precisely, the
last bits of W_i), before she
can decrypt. This defeats the purpose
of an encryption scheme, because even
legitimate principals with access to the
decryption keys would be unable to
decrypt. (Scheme II has a
similar inadequacy, but as we
show below, the best way
to fix it is to
introduce pre-encryption, as in Scheme
III.) We now show a
simple fix for this problem.
In the fixed scheme, we
split the pre-encrypted word L_i
into two parts, L_i' and
L_i'', where L_i' (respectively L_i''
)denotes the first m bits
(respectively the last bits) of
L_i . Instead of generating
S_i = G_{K_i}(l), Alice
should generate S_i as
X_i = π(W_i). For decryption
Alice can generate S_i using
the pseudorandom generator (since Alice
knows the seed), and with
S_i she can recover L_i'
by XORing S_i against the
first m bits of X_i
. Finally, knowing L_i' allows
Alice to compute L_i'' and
thereby finish the decryption. This
fix is not secure if
the L_i are not encrypted,
since it may be quite
likely that in some cases
different words have the same
first m bit. Pre-encryption eliminates
this problem, since with high
probability all the L_i are
distinct. (Assuming the pre-encryption is
a pseudorandom permutation, then by
the birthday paradox [15], the
probability that at least one
collision occurs after encrypting n
words is at most
n²/2 )m+1 = nWith
this fix, the resulting
scheme is provably secure,
and in fact we
can also show that
it provides query isolation,
meaning that even when
a single key K_i
is revealed, no additional
information leaks beyond the
ability to identify the
positions where the corresponding
word W_i occurs. Theorem
4.3. Suppose π is
a (T, ε)-secure pseudorandom
permutation, F is a
(T, q, ε)-secure pseudorandom
function, F' is a
(T, q, ε)-secure pseudorandom
function, G, is a
(T, ε')-secure pseudorandom generator,
and we choose the
key material as described
above. Then the sequence-generation
algorithm described above, S
= (S_1, ..., S_n),
will be a (T',
q, ε'')-secure pseudorandom generator,
where ε'' is at
most 2q·ε + n·ε'
+ n²/2 )m+1: and
T' is a constant
factor smaller than T.
Moreover, if we reveal
a single K_i and
consider the reduced sequence
obtained by dropping all
the S_j values at
positions where j ≠
i, then we obtain
a (T', ε''')-secure pseudorandom
generator, where ε''' is
at most ε + n·ε'. Strictly speaking, the
proof of the theorem does not actually require
a pseudorandom permutation: if π_m denotes the
map sending (with a key) the input
to the first m bits of π,
then we can get by with a
much weaker assumption, namely that collisions must
be rare. As a special case, if
the first m bits (π_m) can be
shown to be a pseudorandom function, then
the required property will necessarily hold, and
we can prove a result analogous to
Theorem 4.3. This suggests that for pre-encryption
Figure 3. The final scheme for long blocks may be
implemented, for instance, by taking π to be
the bit-reversal of CBC encryption under a key
K (using a fixed IV). After word-by-word encryption,
Alice can also permute the order of the
ciphertext according to some pseudorandom permutation (known only
to Alice). In this case, when Bob performs
a search for a word, he will not
be able to tell the position where
the word occurs in the actual plaintext.
We see that updates to this scheme are straightforward. For example, if Alice
wants to add a new document to Bob's data store, she can simply
encrypt it in the appropriate way and instruct Bob to append it to
the already-stored ciphertext. Moreover, since keys can be generated hierarchically from a master
key, key storage and management are also very convenient: Alice needs to remember
only a single password, the master key. The basic technique of embedding information
into pseudorandom bit streams may also be of independent interest: we expect
that this simple trick may prove useful for other applications as well.
The schemes we presented earlier solve the problem of searching
for only a single word. We show several examples to
illustrate that it is relatively easy to implement more advanced
search features using our scheme as a fundamental building block.
It is clear that we can easily support extended
search queries using boolean operators (e.g., W1 AND W2
), proximity queries (e.g., W1 NEAR W2 ) and
phrase search (e.g., W1 immediately precedes W2 ). We
can also support search where the query is given
as a regular expression, using, for example, wildcards in
a restricted form. For example, if Alice wants to
search for the word encrypt*, then she can actually
generate 26 search queries of the form encrypta, encryptb,
..., encryptz . However, the number of queries required
(and the information leaked to the server) clearly increases
dramatically as the search word becomes more general. For
many applications, the goal of the search is to
find documents that contain a given word, where the
position or number of occurrences does not matter. For
example, email search is one such application, in which
the query takes the form “find all messages from
Joe.” For these applications, the earlier search schemes leaked
information, since the server would learn the positions of
the word in the document, or at least the
frequency of the word in the document, even if
the order of the words is encrypted. Since we
only need to know whether a given document contains
the word, we can use the following trick. We
append a counter to each word, counting how many
times that word has occurred earlier in this document.
For example, the first occurrence of the word “urgent”
is stored as “urgent1,” the second occurrence as “urgent2,”
and so on. This lets Alice search only for
the first occurrence, if she just wants to identify
the documents in which this word occurs; and Bob
learns no information about the other positions of the
search word in the document. As an additional feature,
this encoding lets Alice search for documents containing k
or more occurrences of a word by searching for
In our scheme, the smallest unit we can search for is
a single word. So far we have assumed that the plaintext
can easily be split into a sequence of fixed length words.
But this may not be the case in an ordinary text
document. For example, if the smallest unit of search interest is
a single English word, then we must deal with the fact
that English words vary in length. One possibility is to choose
a fixed block size long enough to accommodate most words. Words
that are too short or too long can be padded out
to a multiple of the block size using some predetermined padding
format. (Note that the padding cannot be random, since Alice must
know the padding in order to perform the search.) However, such
a padding scheme would lead to inefficient use of space. Also,
for security reasons we cannot reduce the word length below a
certain limit. Another solution is to use variable-length words. In this
case, to support random-access decryption, the length of each word must
also be stored together with the word. One natural approach is
to store a length field before each word in the file
and to concatenate the length field and the word into a
single word for encryption and search using our standard scheme. When
word lengths can vary, it is important to hide the length
information from the server, because revealing the length of each word
could permit statistical attacks. Fortunately, in this case the server does
not need to know the lengths in order to perform a
search: it can simply scan the file and check for
a match at every possible bit boundary. In this case,
the cost of each scan increases, because the number of
operations is determined by the bit length of the document
rather than the number of blocks in the document. H
Nevertheless, such an approach can provide better
space efficiency compared to a block-oriented scheme.
Sequential scanning may not be efficient enough if the data set
is large. For some applications, such as large databases, a common
technique for speeding up search is to use a precomputed index.
Here we show how we can answer search queries using an
encrypted index without compromising security. The index contains a list of
keywords; with each keyword is associated a list of pointers to
the documents in which the keyword occurs. Keywords are the interesting
words that Alice may want to search for later. Alice can
certainly build an index of her plaintext documents, then encrypt the
plaintext and the index and store the ciphertext with Bob. An
interesting question is how to encrypt the index. The naive way
would be simply to encrypt the keywords in the index and
leave the position lists unencrypted. This makes it easy for Bob
to carry out search queries on Alice's behalf, but it also
reveals a great deal of information to Bob and could therefore
allow him to mount various statistical attacks. We therefore reject this
naive approach. A simple approach is to also encrypt the document
pointers in each list in the index. Consequently, when Bob searches
for a keyword and finds a match, he returns to
Alice the encrypted list of matching positions from the index.
Alice can decrypt the encrypted entries and send Bob another
request to retrieve the corresponding documents. One possible advantage of
this scheme is that the request can be embedded among
other searches, so that Bob may be unable to correlate
the search query with the request for the ciphertext. The
disadvantage is that Alice has to spend an extra round
trip to retrieve the documents. If Alice does not want
to wait for the extra round-trip time, or if Alice
wants Bob to merge the results of several search queries
for her, other techniques are available as well. For example,
she can encrypt the document pointers in the index using
a key linked to the keyword, i.e. K_w . Consequently,
when Alice wants to search for the word w, she
reveals K_w to Bob. So that Bob cannot carry out
a statistical analysis of the index, it is better to
keep the pointer lists as fixed-size lists. For words that
occur infrequently, Alice can pad the list out to a
fixed size. For more common words, Alice can split a
long list into several fixed-size lists; then, to find such
a word, Alice needs to ask Bob to carry out
and merge several search queries in parallel. Note that by
storing the pointer lists as fixed-size lists, we largely prevent
Bob from learning statistical information about keywords he has not
searched for. For keywords that Bob has searched for, he
can still learn some statistical information from Alice's access pattern.
This is acceptable from our point of view, since Alice
only wants to retrieve the relevant documents in the first
place. Note that a general drawback of index-based search is
that whenever Alice changes her documents, she must update the
index. There is a trade-off between how much of the
index Alice updates and how much information Bob is able
to learn. For example, if Alice does not modify the
document-pointer list for a single keyword entry when she adds
a new document to Bob's data store, Bob will be
able to tell that the keyword does not occur in
the new document. Alice therefore needs to update a substantial
portion of the index in order to hide the genuine
updates, which can be fairly expensive. This is an interesting
research question: to design schemes that support more efficient updates.
In all our schemes, by letting Bob search for the word W,
we effectively reveal to him a list of the potential positions where
W may occur. If we also let Bob search for many words,
he may be able to use statistical techniques to begin learning important
information about the documents. One possible defense is to lower the matching
threshold (so that false matches are more common, and Bob's information about
the plaintext is thereby “noised”), but we have not analyzed the cost-effectiveness
of this trade-off in any detail. A better defense for Alice is
to periodically change the key, re-encrypt all the documents under the new
key, and reorder the ciphertext according to some pseudorandom permutation (known to
Alice, but not to Bob). This will help prevent Bob from
learning correlations or other statistical information over time. This technique can
also be useful if Alice wants to hide from Bob the
positions where the search word occurs in the documents of interest.
In all the schemes we have discussed so far, we must
trust Bob to return all the search results. If Bob cheats
us and returns only some (but not all) of the search
results, Alice has no way to detect it. For the purposes
of our interest, we assume that Bob does not behave maliciously
in this way. Even when this type of attack
is present, our scheme can be combined with hash-tree
techniques [17] to ensure data integrity and detect
such attacks, although a full description of this
countermeasure is beyond the scope of this paper.
Many researchers have investigated the problem of ensuring secrecy and integrity when
using an untrusted file server or external untrusted storage [5, 12, 1,
6]. But as far as we know, no prior work has provided
a solution for searching over encrypted data. Secure multi-party computation and oblivious
functions have also been studied intensively (see, for example, [14, 8]). We
believe there may be a solution to the problem of searching over
encrypted data using multi-party computation, but this would require substantial overhead, such
as multiple servers. Our solution needs only a single server for searching
over encrypted data and is therefore a more practical solution. Several researchers
have studied the private information retrieval (PIR) problem, whereby clients can access
records in a distributed table without revealing which records they are interested
in. The PIR literature typically aims for very strict information-theoretic security guarantees,
which makes it difficult to find practical schemes: PIR schemes often require
multiple non-colluding servers, consume large amounts of bandwidth, do not guarantee
the privacy of the data itself, do not support private keyword
search, and do not support controlled search or query isolation (but
see, e.g., [16, 13, 10, 7] for notable exceptions that lift
some — but not all — of these restrictions). In contrast,
although our scheme does not solve the PIR problem, it needs
only a single server (without impractical trust assumptions), has low computational
complexity, and supports private keyword search with very strong security characteristics.
We have described new techniques for remote search over encrypted data using
an untrusted server, and provided proofs of security for the resulting cryptosystems.
Our techniques have a number of important advantages: they are provably secure;
they support controlled and hidden search and query isolation; they are simple
and fast (more precisely, for a long document the encryption and search
algorithms need only stream-cipher and block-cipher operations); and they introduce almost no
space or communication overhead. Our scheme is also very flexible, and it
can easily be extended to support more advanced search queries. We conclude
that this provides a new and powerful building block for constructing secure
services on untrusted infrastructure. Acknowledgments We would like to thank Doug
Tygar for his valuable suggestions and advice. We would also like
to thank John Kubiatowicz for supporting work on the problem of
searching over encrypted data. We would also like to thank Bob
Briscoe for helpful comments on the paper.
Authors: Dawn Xiaodong Song, David Wagner, and Adrian Perrig.
Comments