Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 ?
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.
