Functional Encryption Systems From Hard Lattice Problems

Data security challenges faced in the modern world demand functionality from encryption systems that traditional public key cryptography falls far short in delivering.

Take the example of cloud computing, a paradigm which allows users to outsource their data storage and computing needs to a powerful third party server such as Amazon. Though such a service is very useful, users may be reluctant to trust third party servers with sensitive data. Organizations utilizing these services must also ensure that their clients are secure from each other. At the same time, meaningful functionality must be provided. For example a server storing medical data might be required to grant users access to certain useful functions computed on the entire user database, such as the success rate of some medication for a given disease, while making sure that individual medical privacy is not compromised.

To address these emerging needs, a new paradigm of encryption was recently put forward – Functional Encryption. In functional encryption, a user's secret key can be associated with its holder's credentials, while the ciphertext can be associated with an access policy. We may ask that decryption succeed if and only if the credentials satisfy the access policy.

I will describe several special cases of functional encryption that we have constructed -- systems for the identity function (identity based encryption or IBE), threshold function (fuzzy IBE) and linear functions. I will describe ongoing work to provide a general framework for these constructions and challenges faced in supporting more general functions. The technical tool we use in these constructions is the worst-case hardness of lattice problems. Lattices have traditionally been used in cryptography for breaking cryptosystems and their use in building cryptosystems is surprising and elegant.