It appears (after doing some light research) that for encrypted databases to be

Question

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...

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.