If this works out, this is a big breakthrough. One of the encryption schemes described in the paper also looks like it should be reasonably efficient to implement (the scheme "E_1"). That scheme doesn't give you everything you'd need for fully homomorphic encryption, but it is part of the way there.
This looks very intriguing. Unfortunately, I can't find a free copy of this paper nor any articles talking about it. Can anyone else dig up either a copy or some additional information?
There's a pdf link in the article.
Even though it's on the ACM site, I downloaded the paper with no problem.