Easy methods to Search on Encrypted Information: Introduction (Half 1) //

⁶/Oct 2013

That is the primary a part of a sequence on looking on encrypted information.
See elements

2,
3,
4,
5.

I lately completed giving a sequence of talks on one in all my favourite matters:
looking on encrypted information. My slides can be found
here,
however given the present curiosity on this subject I believed it could be helpful to
flip the discuss right into a sequence of posts.

Through the years, the issue of encrypted search has grow to be an vital drawback
in safety and cryptography. I believe this is because of a mix of three
issues: (1) search is now the first manner we entry our information; (2) we’re
outsourcing increasingly more of our information to 3rd events; and (3) we belief these
third events much less and fewer (for apparent causes!).

Due to this, the issue of encrypted search is now of curiosity to many
sub-fields in laptop science (e.g., databases, safety, cryptography,
privateness) but additionally to trade and to governments.

Whereas a-priori looking on encrypted information might sound unattainable and
even contradictory, we all know of some ways to do it. Some strategies are
extra sensible than others, some are safer than others and a few are extra
practical/versatile.

Some Historical past

The issue of looking on encrypted information was first thought-about explicitly by
Track, Wagner and Perrig in this
paper from 2001. Once I
first learn this paper as a graduate scholar, I believed this was wonderful! I had
by no means imagined one may do something like this with encryption and, amazingly,
the development even appeared sensible. Mixed with the apparent sense that
these “searchable encryption” schemes may have a huge effect, I received actually
enthusiastic about this drawback.

I later understood that maybe I should not have been so shocked (however no much less
impressed!) concerning the risk of looking on encrypted information since
prior work on
oblivious RAMs by
Goldreich and Ostrovsky and on
secure two-party computation
by Yao additionally offered options to this problem—albeit a
lot much less effectively.

It has been about 10 years because the Track, Wagner and Perrig paper, 20 years
because the Goldreich and Ostrovsky paper and 30 years since Yao’s paper. So
the place can we stand with respect to encrypted search?

The brief reply is that we have made a ton of progress and we’ re on the level
the place encrypted search within reason nicely understood , environment friendly and might be
deployed. After all, like every cryptographic know-how there are tradeoffs one
has to think about and one of many objectives of this sequence shall be to make these
tradeoffs clear.

The Setup

To construction our dialogue and to permit for comparisons of the completely different
options, we’ll assume the next setting. We’ve two events: a consumer and
a server; that work together in two phases: a setup part and a search part.

In the course of the setup part, the consumer will take $n$ paperwork $(D_1, dots, D_n)$
and generate:

1. an encrypted database (EDB),
2. a set of encrypted paperwork $(c_1, dots, c_n)$.

We’ll assume the paperwork are encrypted utilizing
a normal encryption scheme (e.g., AES utilizing your favourite mode of operation)
so the fascinating half shall be how precisely the EDB is constructed.

See Also

Can we consider git commits as diffs, snapshots, and/or histories?

In order a concrete instance if the paperwork are an e mail assortment, the consumer
will generate an EDB after which encrypt every e mail individually utilizing, say, AES.
After producing the EDB and encrypted paperwork, it is going to ship all the pieces to the
server, concluding the setup part.

In the course of the search part, the consumer desires the server to ship again all of the
encrypted paperwork related to some key phrase $w$. To do that, the consumer
will ship a token that encapsulates $w$ with out revealing details about
it. The server will then use the token with the EDB to in some way determine
out which encrypted paperwork it ought to ship again.

Conclusions

We all know of six other ways to go looking on encrypted information, every
based mostly on one of many following cryptographic primitives:

• property-preserving encryption
• practical encryption
• fully-homomorphic encryption
• searchable symmetric encryption
• oblivious RAMs
• safe two-party computation

In the remainder of this sequence we’ ll undergo a few of these approaches and see
the assorted tradeoffs they supply between effectivity, safety and
performance.