In theory if you have arbitrary addition and arbitrary multiplication (i.e. a ring structure) you can perform any transform on the cyphertext that you could on the (finite) plaintext.
As a practical matter conplext transforms tend to produce enormous cyphertexts that can't be evaluated in any reasonable time. Which is why a lot of the cutting edge work is in renormalizing, even at the cost of restricting operations (thus somewhat rather than fully homomorphic).
I gave the same statement to a coworker who inquired about fully homomorphic encryption, but I didn't have the data to back it up. Can someone help me find performance numbers relevant to this library, or at least a recent comparable implementation?
I don't see benchmarks for this particular implimentation yet, but the readme references the Gentry-Halevi-Smart optimizations as an inspiration. That paper Homomorphic Evaluation of the AES Circuit (http://eprint.iacr.org/2012/099.pdf), discusses three FHE methods of computing AES-128. The fastest disclosed implementation has an amortized run time (on a beast of a machine -- 18MB cache, 256GB RAM) of around 19 seconds per byte. In contrast some CPU have native instructions that can run AES-128 on the order of cycles per byte. So we are roughly talking a 10 billion fold slowdown.
I thought the Gentry method solved the problem of enormous cyphertexts (via 'bootstrapping') while still preserving addition and multiplication operations. Is that not true?
Sure but that method just trades time for space. Later work did reduce the overall complexity by substituting different "hard problems" as the cryptographic primitive, but it's still in the realm of unusable scaling characteristics.
On the other hand, so far as I know, no one has published any papers that suggest a fundamental barrier to improvement. Here's hoping!
As a practical matter conplext transforms tend to produce enormous cyphertexts that can't be evaluated in any reasonable time. Which is why a lot of the cutting edge work is in renormalizing, even at the cost of restricting operations (thus somewhat rather than fully homomorphic).