A new way to think about data encryption: two-level keys

Current encryption methods are far from perfect—a fact highlighted by the numerous data security breaches that have occurred over the past few years. Technological limitations in the "trusted server" model for encryption and psychological barriers hinder the robust protection of data. A trio of computer science researchers has set out to simplify encryption systems. Their research, which began in 2005, has led to a novel encryption system that they term "functional encryption" greatly simplifies the problem of key complexity.

In a functional encryption system, keys are personalized and only one is needed for a person to gain access to all the data that should be available to them. In addition to simplifying the key process, this idea allows users—with proper access rights—to search encrypted volumes for specific information.

The problems with trusted servers 

According to Prof. Amit Sahai, there are issues with the current model of storing encrypted data on a "trusted server." In this scheme, data is uploaded to a server and that server is given the task of determining who has access to it. These servers represent a technological problem because they are a tempting target for malcontents who are eager to get their hands on the data.

As the data needed to be stored grows in size, organizations often add more servers to handle it and add redundant backup servers in case one fails. As the number of servers increases, the number of targets for hackers increases as well. Beyond the physical problems, psychological issues exist—how many users simply run everything as an administrator or superuser? Working in this mode can nullify any encryption or security protocols that may be in place.

I spoke with Prof. Sahai about his work, and he likened current encryption systems to a simple lock and key approach. Data is kept locked away on a server, and everyone who needs access is given a copy of the same key. He and his colleagues sought to make encryption both more robust and simpler than current schemes. The idea behind their work is that a personal key is more than just a key: it holds a person's information and policies that will mathematically determine what locks they should be allowed to open. It is this new type of decryption key that is—pardon the pun—the key idea behind this work

Two levels of protection 

The researchers' scheme requires two things to be protected: actual data and the policy for the data. The policy is essentially an embedded description of who can have access to encrypted data. While we know how to secure the data, how should the policy be secured? According to Prof. Sahai, ideally both should have equal levels of security. As he put it, the person "who satisfies the policy should only know that they satisfy the policy," not why. If one can protect both the policy and the data, then a whole new range of applications is possible. 

One such application is searching encrypted data. Prof. Sahai and colleagues presented their latest work on a new scheme that allows for expressive searching of encrypted data at Eurocyrpt 2008, a premier international cryptography conference. A preprint—for the mathematically inclined—of the paper can be obtained from the Cryptology ePrint Archive. In prior work on searching encrypted data, searchers could use search predicates that consisted only of equality matches and conjunctions. For example, if have have all of my e-mail encrypted on a remote server, I could search for e-mails where (sender=Mom) AND (month=February).

Previous work was unable to handle disjunctions—OR operators. Using the prior example, previously, I would have been unable to search my encrypted archive for (sender=Mom) OR (sender=Dad) AND (month=February). In the above paper, Sahai and coworkers developed a new mathematical formalism for the creation of keys and encryption that allows full searches of encrypted data in both conjunctive and disjunctive normal forms.

In addition to the ability to search encrypted data, the new encryption scheme allows for the implementation of a "fuzzy" identity encryption scheme. In an identity based encryption scheme, the public key is something tied to your identity—your name, your e-mail, or, in the example Prof. Sahai relayed to me, your fingerprint. In their new system, this public key holds not only your identity but the policies about the data that you can have access to. In the fingerprint example, suppose you encrypt your information under a given impression of your fingerprint. At a later date you attempt to decrypt the information with you fingerprint, but small changes—dust, scratches, growth—will cause the key (your fingerprint) to be slightly different. The new formalism developed here allows for a "fuzzy" check, so the key can be off within a specified threshold.