It appears (after doing some light research) that for encrypted databases to be practical enough to be usable, deterministic encryption is required, specifically with regard to the type of encryption that always produces the same ciphertext for a given plaintext and key pair. I understand that deterministic encryption allows equal plaintext values to be detected, is possibly vulnerable to frequency analysis and lacks semantic security i.e. is vulnerable to chosen plaintext attack.

However, is it possible to minimize or remove these drawbacks by:

  1. ensuring only authorised use of the database (to prevent chosen plaintext attacks), and
  2. by injecting known encrypted tuples of carefully selected (bogus) values to balance out the cyphertexts to deflect frequency attacks? These bogus values would be dropped from a user's query results at the user's end prior to being presented to the user.

Of course, this would mean possibly doubling the database size, but I would like to ignore that for now...

  • $\begingroup$ "deterministic encryption allows equal plaintext values to be detected" => this really doesn't work that way. I think you should read about the different block cipher modes of operation as a starter. $\endgroup$ – Dillinur Jan 28 '15 at 12:27
  • $\begingroup$ Thanks for your comment. Sorry for being vague but I was actually referring to the case where a given plaintext and key would produce the same ciphertext each time. I have updated the question to make it more obvious. $\endgroup$ – user3150164 Jan 28 '15 at 13:26
  • $\begingroup$ Your question is still very strange. Why don't you use a different IV for each plaintext? What are your constraints on the crypto system you're using? $\endgroup$ – Dillinur Jan 28 '15 at 15:16
  • $\begingroup$ @Dillinur If you use a different IV for each plaintext, it's not deterministic encryption. Most block cipher modes are not deterministic. $\endgroup$ – cpast Jan 28 '15 at 18:52

How a database is encrypted depends entirely on the types of queries you want to be able to make on it and the security of its design is considered in terms of a leakage function L (analogous to a random oracle). If the server can't tell the difference between a leakage function and an encrypted database with actual data, then the scheme is called L-semantically-secure (making it a generalized version of the game of distinguishing a random oracle from a PRF).

Deterministic encryption modes (like SIV) leak equality and are only semantically secure (in the traditional sense) if you can ensure that the way the data is structured prevents redundant information.

A good example would be encrypting user information: the user's id and username would be encrypted deterministically to allow fast retrieval on either of those keys and the rest of their information would be encrypted probabilistically. Because user ids and usernames are always unique, the database can't derive any knowledge (besides length / block size) from the encryptions that it doesn't already know about the data set in general.

In some cases, though, there's nothing wrong with just telling the server know how you're partitioning data because it would be leaked by an SSE (Searchable Symmetric Encryption) scheme, as well, anyway.

Things like OPSE (Order-Preserving Symmetric Encryption) leak inequality (and, optionally, equality) to allow the server to sort encrypted data. SSE constructions typically have more complex leakage functions but allow for free text search.

All of these schemes satisfy #1 already--search requires knowledge of a secret key.

The idea in #2 is completely a case-specific consideration. In most SSE schemes, the server is allowed to learn how many documents match a keyword, even if it's not allowed to learn which, because it's simply too expensive to prevent in general. Although, if a specific case affords an efficient solution then implementing it would yield a more powerful leakage function.

|improve this answer|||||
  • $\begingroup$ Thanks for your answer. With respect to #2, would you be able to re-word your last two sentences, because I can't seem to understand the phrases "... even if it's not allowed to learn which(?)..." (please explain what is "which"), and "...if a specific case..." - not sure what you mean by that. Thanks! $\endgroup$ – user3150164 Jan 29 '15 at 7:13
  • $\begingroup$ "Even if it's not allowed to learn which documents match the query" and "a specific use case of SSE" (free text search would obviously not be that case, but certain kinds of tagged search might) $\endgroup$ – Bren2010 Feb 1 '15 at 3:12

I work in the area of data-at-rest encryption, so I feel fairly qualified to answer your questions.

Re. 1: Access control is well and good but it typically isn't modeled in cryptographic proofs of security because it's an extra assumption, and proofs try to use as few assumptions as possible. It's obviously important for the real-world security of a database, but to be safe you have to assume everybody is an attacker, even someone with valid credentials.

re. 2: Your strategy for deflecting frequency analysis is usually called 'homophonic encryption' in the literature. It is indeed useful for making certain statistical attacks much more difficult, but its efficacy is highly dependent on the particulars of the type and number of bogus values injected, and crucially also on the distribution of the plaintext data.

If your database will primarily be doing information retrieval and/or search-type stuff, a much more secure (in theory and practice) primitive is searchable symmetric encryption. It gets you the functionality without needing deterministic encryption.

|improve this answer|||||
  • $\begingroup$ Thanks for your answer. I'm not actually using homophonic encryption, because although I have considered it, it would cost too much in terms of performance doing searches for all the synonyms. As an example of what I am doing, to thwart frequency analysis attacks on things like English words, I would insert encryptions of lower frequency words (bogus data) into the database, so the difference between typically lower and higher frequency words is negligible. The database is updateable, but I will need to have a look at searchable encryption although I have a feeling it may not be what I want... $\endgroup$ – user3150164 Jan 29 '15 at 7:06
  • $\begingroup$ Can you explain how does searchable symmetric encryption (SSE) primitive does not need deterministic encryption ? I think that even if SSE is being used, encryption needs to be deterministic, at least when querying so that cipher-texts can be compared. I think that SSE is more advantageous is on how you organize your data structure (e.g: reversed index) which can also be achieved in encrypted databases. $\endgroup$ – aks Mar 11 '19 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.