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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I thought the current state of the art for fully homomorphic encryption was Brakerski, Gentry and Vaikuntanathan's scheme (BGV) based on standard/ring LWE employing modulus switching for noise management.

I recently came across a paper by Zvika Brakerski on a "scale invariant" FHE scheme, based on gapSVP, that does not require modulus switching.

Is there an opinion on whether the latter "scale invariant" scheme (I haven't fully read the paper as yet) represents the current state of the art in the FHE world?

share|improve this question
I believe this is the paper: – mikeazo Oct 21 '13 at 23:23
Let me clarify what you ask. What do you mean "The current state of the art"? Newest? Fastest? Most compact? Most secure? – xagawa Oct 26 '13 at 5:32
I'm primarily interested in implementation, so I would say speed and compactness are primary concerns. – Rohit Khera Oct 28 '13 at 19:47
@RohitKhera, you may find this paper interesting: Apparently the scale invariant idea has been applied to BGV and to an NTRU based scheme. – mikeazo Feb 20 '14 at 17:48
up vote 4 down vote accepted

I think arguments could be made for either, but I would still call BGV the state of the art for FHE for the following reasons:

  1. A public implementation exists
  2. We have benchmark info
  3. Other protocols have successfully applied it with real world use and analysis here and here (though presumably the scale-invariant system could replace BGV in this work)

All of this could change though. Someone could release an implementation of the cipher and benchmark the benefits. Recent papers are beginning to mention the scale-invariant system. The authors list a number of potential benefits of their system. And a recent blog post details the simplistic nature of the cipher.

There are reasons to believe that the scale-invariant system will not become state of the art though. This system uses rationals (fractional ciphertexts modulo 1) which is different and I'm not sure how that affects implementation. The blog post talks about this and mentions using reals, truncated and that this does not affect correctness. But what about performance?

One popular optimization to FHE ciphers is ciphertext packing (putting multiple plaintexts into a single ciphertext). This allows SIMD like computations on encrypted data. The authors of the paper you mention do not mention packing in $\S$4.2-Implications and Optimizations. Though it appears to be at least an option (see comment by Chris below). Multiplication in the scale-invariant cipher appears to be less efficient too.

share|improve this answer
Regarding your last paragraph: Brakerski's "scale invariant" scheme can be easily adapted to ring-LWE and to "packed" ciphertexts. ("Packed" ciphertexts come immediately from having a plaintext ring of $R_p$, which comes directly from the ring-LWE variant.) The main difference between BGV and scale-invariant is that the latter makes modulus-switching "optional," but has a somewhat less efficient multiplication operation. – Chris Peikert Jun 12 '14 at 3:09

Your Answer


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.