Data Leakage from Encrypted Databases
Matthew Green has a super-interesting blog post about information leakage from encrypted databases. It describes the recent work by Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson.
Even the summary is too much to summarize, so read it.
Jon • March 1, 2019 8:37 AM
Fascinating article.
Had a thought, though, about implementing ‘fuzzy’ database records as a counterattack.
Imagine:
a) The database contains some small percentage (5%?) of records that are ‘fuzzy’ records – they will occasionally (not always!) return from unrelated queries.
b) Query specifics are encrypted (e.g. range), and identical plaintext queries are NOT encrypted into the same ciphertext!
c) The client, when decrypting the returned records, can easily recognize a ‘fuzzy’ record and discard it.
Eventually an attacker could by probability determine which records are ‘fuzzy’ and ignore them, but the hope here is that by adding a small amount of ‘fuzzy’ records it makes the number of samples required very much larger for the same error rate.
And, of course, there’s overhead.
Anyhow, I’m very sure I don’t know how to do the math on this idea. Have fun.
J.