[Cryptography] Pragmatic, column-level data encryption at rest. Possible?

[Jerry Leichter]

[Questions about encryption of databases.]
There have been three major streams of work on this general field.

A number of years back, a couple of papers were published on ways to encrypt an entire record in such a way that you could give away keys for subfields, and someone with a key could only decrypt those subfields.  There was some pretty math involved here (extensions of RSA) but as far as I know no one ever managed to turn this into a practical solution, and the papers remain academic curiosities.

More recently, a group at MIT took a more pragmatic approach, in which they choose different kinds of algorithms for different fields depending on the access and security requirements for each of those fields.  The project page is a https://css.csail.mit.edu/cryptdb/.  This work has been criticized for leaking information - e.g., some encryptions need to be order-preserving, which inherently leaks information and, in some situations, can leak a great deal of information.  The CryptDB people have basically responded that, yes, this is a tradeoff you have to make.  The jury is out on this.  For some kinds of data and CryptDB-style encryptions, the resulting database would arguably not be, say, HIPAA compliant.  (E.g., imagine a row of SSN's encrypted with an order-preserving encryption.  If I can cause records with arbitrary SSN's to be added to the database, I can look to see where they fall and triangulate on the record for a particular SSN - and at the least determine if it's present in the database, probably already a privacy violation.)

The third stream is more general and centers on homomorphic encryption, which allows you to do arbitrary computations on encrypted data producing encrypted results.  (Note that the party doing the computations *doesn't learn anything about the actual data*; all they see is the encrypted data and results.)  Cool idea, cool and complex mathematics - but no generally usable results yet as far as I know.

Given the constraints you're under, CryptDB *with very careful specification of the required security properties, followed by proper mapping to the CryptDB primitives available*, might give you something useful and practical.  But you'd have to do the up-front work to be sure - and look at the papers on attacks against CryptDB, not just the papers by the designers, before going this route.

An orthogonal alternative is to encrypt the entire database and use hardware to ensure the even if the whole thing is stolen the keys are lost.  Put the computer and storage inside a safe with various security features that detect an attempt to open it and zero the internal record of the keys.  Get your keys back from a properly designed KDC.

What attacks were you trying to secure against again?  :-)

                                                        -- Jerry