5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I believe this is the paper: eprint.iacr.org/2012/078.pdf $\endgroup$
    – mikeazo
    Oct 21, 2013 at 23:23
  • 1
    $\begingroup$ Let me clarify what you ask. What do you mean "The current state of the art"? Newest? Fastest? Most compact? Most secure? $\endgroup$
    – xagawa
    Oct 26, 2013 at 5:32
  • $\begingroup$ I'm primarily interested in implementation, so I would say speed and compactness are primary concerns. $\endgroup$
    – Rohit Khera
    Oct 28, 2013 at 19:47
  • $\begingroup$ @RohitKhera, you may find this paper interesting: eprint.iacr.org/2014/062.pdf Apparently the scale invariant idea has been applied to BGV and to an NTRU based scheme. $\endgroup$
    – mikeazo
    Feb 20, 2014 at 17:48

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Chris Peikert
    Jun 12, 2014 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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