Monday, September 04, 2006

The Negated Database

The Economist has an interesting article on a new cryptography idea: instead of securing the data with encryption that may be compromised, why don't we just store the negation of the data? i.e. The database contains everything except the intended data (if the data space is small, we may need to put some extra paddings to increase the entropy). Say a database of 8-digit phone numbers, that database will contain all 8-digit numbers, except those valid ones. So to check whether a phone number is valid, we need to make sure that number is not in the database.

The advantage of this could be the leakage of confidential data may be contained if the said database is breached. However, I can think of the following shortcomings:

  1. Any change of data formats (e.g. adding one more field) will warrant a respawning of the whole negative database. This will not be trivial if the data space is big enough.
  2. Searching and sorting will be a challenge as special algorithms must be in place to ensure the database is responsive enough.
I feel the underlying theory has something to do with entropy: This negative database has a much higher entropy than the normal ones, and therefore it will take more effort to deal with it (this applies for legitimate and illegitimate users!).

Update:
Author's homepage.
He has a paper with more information about this scheme, however it seems my two concerns are still not addressed...

Friday, September 01, 2006

First Post

After some pushing encouragement from my friend Flowing Stream, finally I have come out with the blog of my own. Now I guess it's my turn to get pushed for more blog postings. This blog will consist mostly technical-related stuff and occasionally some rants on life. Read at your own peril. ;)