You might be interested in Parallel Homomorphic Encryption [PDF: http://eprint.iacr.org/2011/596.pdf], a Microsoft Research paper covering MapReduce on encrypted data.
It's entirely possible to move encrypted data into the cloud, process it, retrieve the results, then decrypt. Welcome to the future.
Yeah but… If you had a $600million budget, wouldn't you just call up Amazon and say "Hey, you know your Availability Zones and Regions? How much to build me a couple of them, along with all your management and accounting software, so we can run pretty much all of AWS (front and back end) inside our own data centers?"
It'd be much easier for recruitment, to be able to advertise for developers/data-scientists/sysadmins with AWS experience, than just about _any_ alternative…
That's probably what someone asked for. By the time it got approved, GSA signoff, and past contracts and vendor management, they have a micro instance in us-east-1 to run www.cia.gov off of.
It's "possible". The problem is that the number of known operations that works with homomorphic encryption is so far so small as to be mostly useless. It'll take a lot of research before it becomes practical, if it ever does, for anything but very specialised operations.
It's entirely possible to move encrypted data into the cloud, process it, retrieve the results, then decrypt. Welcome to the future.