Deterministic and Searchable Encryption

The idea of efficiently searchable encryption (ESE) is introduced recently.
Efficiency here means an untrusted server can index, retrieve or update the
encrypted data on request just as efficiently as if the data is unencrypted.
ESE is a public key (asymmetric) encryption. Its basic idea is to use a 
deterministic encryption (with some additional property, refer to the 
technicalities) to encrypt the data, which makes a given plaintext always
will be encrypted to the same ciphertext. If the ciphertext of distinct 
messages under a given public key rarely coincide, indexing the ciphertext
is essentially the same as on unencrypted ones.

ESE is proposed for the outsourced database model, but not for our privacy
preserving operations. However, one may apply ESE in our scenario if a 
central party is assumed to join the databases faithfully based on the 
encrypted data.

Weaknesses : As noted in , a small plaintext space means offline dictionary
attack is possible, one can test if a ciphertext corresponding to a given
plaintext by a public key encryption, which can be done by anyone, including
the central party. This weakness also appears in some query processing 
systems over encrypted data. So the security of ESE is based on an additional
assumption that the plaintext space has high entropy, which is not (necessary)
true in equijoin, where only primary keys are encrypted.

Commutative Encryption : The idea of using deterministic encryption also
appear in prior work in privacy preserving operations outside the outsourced
database model (e.g. a protocol between two data owners). The encryption
scheme is deterministic and is realized by a modular exponentiation. Despite
of the use of modular arithmetic, it is a symmetric encryption scheme.
Again, due to the deterministic nature, multiple runs of the protocol may leak
partial information about different queries.

, , , , , , , ,

  1. #1 by Linda Thema on November 14, 2011 - 6:57 pm

    It’s very nice topic

    Thanks again.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: