Craig Gentry recently gave the first fully homomorphic cryptosystem. Quite a bit of work has been done since extending his work. It seems, however, that no system is practical for real world use.
Bottom line. The short answer is that none of them are practical ... yet. But there is a lot of active research, and if we're lucky, maybe that will lead to enough improvements that it might become practical. We'll see.
More information. You can find some useful information at the following questions:
What Partial Homomorphic Encryption implementations exist and how do I leverage them? discusses some schemes that fall short of being fully homomorphic but are more practical and are enough to be useful in some settings.
In what ways does Full or Partial Homomorphic Encryption benefit the cloud? discusses applications of fully homormophic encryption and links to some papers that discuss the state-of-the-art and how practical the best schemes are.
These resources may be of interest:
Shai Halevi's Homomorphic Encryption Tutorial, presented at CRYPTO 2011.
Helger Lipmaa's collection of research papers on fully homomorphic encryption.
See also the following research papers:
Kristin Lauter and Michael Naehrig and Vinod Vaikuntanathan. Can Homomorphic Encryption be Practical?
Jean-Sebastien Coron and David Naccache and Mehdi Tibouchi. Optimization of Fully Homomorphic Encryption.
Marten van Dijk and Craig Gentry and Shai Halevi and Vinod Vaikuntanathan. Fully Homomorphic Encryption over the Integers.
Damien Stehle and Ron Steinfeld. Faster Fully Homomorphic Encryption.
This is a rapidly-evolving space, so anything I write here may become out of date quickly. You will need to follow the research literature to learn the latest and greatest.
Roadblocks
Some further research answers one of my questions. In "Fully Homomorphic Encryption over the Integers with Shorter Public Keys", the authors state:
We obtain similar performances as the Gentry-Halevi implementation of Gentry's scheme 7. More precisely we use four security levels inspired by the levels from 7 (though they may not be directly comparable due to different notions of security bits): toy, small, medium and large, corresponding to 42, 52, 62 and 72 bits of security respectively. For large parameters, encryption and recryption take 3 minutes and 14 minutes respectively, with a public key size of 800 MBytes. Decryption is always close to instantaneous. This shows that fully homomorphic encryption can be implemented with a simple scheme.
So, it looks like key size and speed are major limiting factors. Another interesting resources comes from Gentry's presentation "A Working Implementation of Fully Homomorphic Encryption" from the rump session at Eurocrypt 2010. In it, for the strongest version they tested, key generation took 2 hours, public key size was 2.3 gigabytes, and re-encryption took 30 min.
Implementations
"Optimization of Fully Homomorphic Encryption" (thanks @D.W. for the reference) lists 3 currently proposed schemes. I'll need to read that paper before I can (hopefully) comment on which is the "most" practical currently. Though my guess is that they are probably roughly the same.
Update from March 2012
Since this is such a rapidly changing field, I wanted to put in some updates to include the state of the art. I hope to do this on occasion. The BGV seems to be the most popular. A number of optimizations were given recently which bring the overhead down to polylogarithmic. One really interesting optimization presented in that paper is the "batch" mode or SIMD operations, which should provide significant performance increases. Further generic optimizations were discovered when implementing AES-128 Homomorphically. That paper also provides some specific optimizations used in implementing AES-128.
Another system was just recently proposed by Brakerski, which is similar to the BGV scheme, but claims a significant breakthrough, namely, the noise in the cipher grows linearly with each multiplication (as opposed to quadratically), without the trick of the BGV system (modulus switching). The performance of this system, however, has not been compared to the BGV system (with or without optimizations).
Update from May 2013
HElib has been released just recently. It implements BGV with some of the optimizations listed above. It seems that for a year now BGV with some of these optimizations is the "most efficient" at this point in time.
