7
$\begingroup$

I read this paper https://eprint.iacr.org/2012/078.pdf and I didn't understand what does the author mean with scale-invariance perspective.

The perspective in which we view the ciphertext is accomplished by the algorithms used ? I refer to BitDecomp, PowersOfTwo and the tensor product.

Or the perspective is achieved by decryption with divide q ?

Should I view scale invariance perspective of the ciphertext as I view Fourier transform of a signal ?

|improve this question
$\endgroup$
  • $\begingroup$ The difference between BGV and its scale invariant version FV is where the plaintext is hidden in the scalar product between ciphertext and secret key: Normally you can recover it by reducing mod $p$ ($p$ being the plaintext modulus). For FV you have to multiply with $p/q$ and round to integer instead ($q$ being the ciphertext modulus). Functionally you do not need to do the modulus switching for the scale invariant version to keep the noise level down (but you might do it anyway for efficiency). For comparison between the systems look also at ia.cr/2015/889. $\endgroup$ – j.p. Nov 5 '15 at 13:38
  • $\begingroup$ Rereading my comment I realize that I should have mentioned that the modulus switching operation is also called scaling. $\endgroup$ – j.p. Nov 5 '15 at 16:15
9
$\begingroup$

While @j.p. is correct that the scale-invariant scheme encodes the plaintext a bit differently than in other FHE schemes, this is mostly just a syntactic point that doesn't really get to the heart of scale invariance. (Indeed, it is easy to switch between the two encodings of the plaintext, simply by multiplying the ciphertext by an appropriate scalar. See Appendix A of this paper for details.)

The key property of scale-invariant schemes is that homomorphic multiplication increases the error "rate" (relative to the ciphertext modulus $q$) by a fixed factor, independent of the magnitude of the errors in the ciphertexts. For example, it doesn't matter whether the ciphertexts have error $\approx 10^2$ for modulus $q=10^6$, or error $\approx 10^5$ for modulus $q=10^9$ (for the same error rate of $10^{-4}$): the error rate in their homomorphic product will be, say, $10^{-2}$. (I'm using artificially small numbers here for the sake of illustration.)

By contrast, homomorphic multiplication in non-scale-invariant schemes is very sensitive to the magnitude of the errors, because the errors are essentially multiplied. So in the first case above we would end up with error $\approx 10^4$ for modulus $q=10^6$ (which is fine), but in the second case we would get error $\approx 10^{10}$ for modulus $q=10^9$, which would yield garbage upon decryption.

Non-scale-invariant schemes use modulus reduction to convert the second case into something more like the first, to make the ciphertext safe for multiplication. Scale-invariant schemes don't need to do this (though it's still useful as an optimization, because decreasing precision leads to faster operations). More significantly, scale-invariant schemes can be based on a parameterization of LWE that is classically (not just quantumly) as hard as worst-case lattice problems, where we need to use a huge $q \approx 2^n$ and a (still huge, but relatively much smaller) error $\approx q \cdot n^{-d}$, where $d=O(\log n)$ (for example) is the multiplicative depth we want the scheme to be able to handle.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the nice explanation! Looking at the formulas of BGV and its scale-invariant version FV I wonder what makes the latter system scale-invariant. Do I understand it correctly that this effect is caused exclusively by moving the plaintext info from the bottom to the top by multiplying the scalar (and adapting the formulas)? Can one interpret this also as switching from working in $\mathbb{Z}$ (modulo a big number) to working in $\mathbb{Q}/\mathbb{Z}$ (times a big number) which frees one from looking at two different kind of errors (relative vs. absolute)? Or is my understanding wrong? $\endgroup$ – j.p. Nov 6 '15 at 13:01
  • $\begingroup$ NB: Brakerski's scheme was the first scale-invariant one. When the plaintext is represented in the "most significant" position, one needs a quite different homomorphic multiplication algorithm. As you mention, one useful way of looking at it is to "scale down" $\mathbb{Z}/q\mathbb{Z}$ to $\mathbb{Q}/p\mathbb{Z}$ (with sufficient finite precision), so that error rate and magnitude are essentially equal. With this perspective, the homomorphic multiplication algorithm is explained in this blog post: windowsontheory.org/2012/05/02/building-the-swiss-army-knife $\endgroup$ – Chris Peikert Nov 6 '15 at 15:35
  • $\begingroup$ Thanks for answering my comment. I do not understand why write that multiplication is quite different. (I'm starting to get comfy with BGV, and my knowledge if FV is just its formulas next to BGV's in ia.cr/2015/889.) To me the formulas for multiplication and SwitchKey of BGV and FV look very much alike. I'll try to understand the differences over the weekend. (I've read the blog post before, but even rereading it didn't help much. Splitting the operation in Multiplication with a result in a different key format and then SwitchKey is easier to grasp for me.) $\endgroup$ – j.p. Nov 6 '15 at 17:00
  • $\begingroup$ The short answers is that in BGV, homomorphic multiplication is "just" multiplication in $\mathbb{Z}/q\mathbb{Z}$, which implicitly multiplies the errors. (Let's ignore all the key-switching and other post-processing...) In the scale-invariant setting, it isn't meaningful to multiply elements of $\mathbb{Q}/p\mathbb{Z}$ (the result wouldn't belong to $\mathbb{Q}/p\mathbb{Z}$). Instead, Brakerski's algorithm bit-decomposes the elements and multiplies (tensors) the results, before resorting to post-processing. $\endgroup$ – Chris Peikert Nov 6 '15 at 17:07
  • $\begingroup$ After looking at Brakerski's Crypto'12 paper I do not understand your last comment. My understanding is that if the system is ring-based you multiply polynomials, if not you take a tensor product of vectors. The difference between scale-invariant or not is only which error term grows most by multiplying. For scale-invariant this term is bounded by the norm of the secret key, so you do bit-decomposition to get it dependent on $n$ instead of $q$. For BGV a similar error term depending on the ciphertext shows up, when trying to switch back to the original key, and is handled accordingly. $\endgroup$ – j.p. Nov 6 '15 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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