In any non-trivial application, key sizes and the encryption of a single bit are measured in gigabytes. Storage is of order 1010 larger, and computations take much longer. One estimate is that Gentry's 2009 system gives one a 1012 slowdown. There is much current work to speed this up (e.g., Smart and Vercauteren, 2010), and orders of magnitude improvements have been obtained in the last few years. Even so, the inefficiencies of fully homomorphic encryption will severely limit its applications. Another, related, concern is that one is always dealing in encryptions of large quantities of data under a public key, something that is impractical even with non-homomorphic schemes. Researchers have shown that symmetric key AES decryption may itself be done as a data operation under a fully homomorphic public key scheme, but the result of such an AES decryption is still an encryption of data under a public key.