Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

  • What are the current roadblocks making FHE impractical?
  • Which proposed system would you say is currently the most practical?
share|improve this question
1  
A paper in EUROCRYPT seems to be here, but I'm not sure this is available on the "free internet". Ah, he has a home page with his PHD thesis, too. –  Paŭlo Ebermann Sep 5 '11 at 14:32
    
@paulo-ebermann: Here is the full paper Implementing Gentry’s Fully-Homomorphic Encryption Scheme. –  fgrieu Mar 5 '12 at 17:33
add comment

2 Answers

up vote 9 down vote accepted

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.

share|improve this answer
add comment

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:

These resources may be of interest:

See also the following research papers:

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.

share|improve this answer
1  
To add to D.W., the talk given by Halevi is also online on IACR's channel on youtube. It was a very nice talk. –  Jalaj Mar 5 '12 at 17:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.