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
FHE schemes claim to use some security parameter $\lambda$ for deriving the other parameters of the scheme, the size of the key and the possible circuits that can be evaluated. Like in Fully Homomorphic Encryption over the Integers. What does this parameter signify ?
Is something that applies only to FHE schemes and puts them on hierarchy of security ? How does this parameter compare to classical schemes, like RSA or AES ? How can be compared the security of a FHE scheme with RSA or AES ?
What does this parameter signify ?
It's a tweakable parameter that varies (typically) the sizes of various objects in the cipher, and while any non-silly value will work (e.g. encrypt and decrypt properly), it does have an influence on the security of the system (typically, how hard of a 'hard problem' the system relies on).
Is something that applies only to FHE schemes and puts them on hierarchy of security ?
Actually, it's fairly common for public key systems to have such a parameter; it's not limited to FHE systems.
How does this parameter compare to classical schemes, like RSA or AES ?
Actually, RSA does have a 'security parameter'; it's the modulus size. When you generate an RSA keypair, you select the size of the modulus; that's your security parameter. Now, we typically don't call that a security parameter, however I believe that's for mostly historic reasons; RSA predates much of modern nomenclature, and so uses its own terminology.
As for AES, no, it doesn't - AES comes in three flavors (128 bit keys, 192 bit keys, 256 bit keys), and those are the only variations you are allowed.
Symmetric ciphers, in generally, usually don't have security parameters; I suspect that's because they're not usually based on preexisting 'hard problems' (and so don't need to choose the size of hard problem to rely on).
Roughly speaking, the security parameter gives you an idea of how much time (or many operations) an attacker needs to break the scheme: that is, any algorithm that "breaks" the scheme has complexity at least $O(2^\lambda)$.
For example, on the end of section 5.2 of that paper, they conclude that successful attacks would take time $2^{\frac{\gamma}{\eta^2}}$. This is why, in section 3, they choose $\eta = \lambda^2$ and $\gamma = \lambda^5$, which means that the attack will take
$$2^{\frac{\gamma}{\eta^2}} = 2^{\frac{\lambda^5}{(\lambda^2)^2}} = 2^\lambda$$
Therefore, when we increase $\lambda$, the scheme becomes more secure. But of course, it has some impact on the scheme (otherwise, we could just pick $\lambda$ as large as we wanted and we would have an unbreakable cipher...). It means that other properties of the scheme must depend on $\lambda$ (for instance, the keys' size or the encryption time may increase when we choose bigger values for $\lambda$).
Almost all (modern) public-key schemes are presented in that way: with all the other parameters as functions of the security parameter $\lambda$. So, it is not exclusive to FHE schemes.
And even if a scheme is not presented in this way, we may reason in the same way the paper did in order to obtain a security parameter. For instance, let's pretend that the best attack against the RSA takes $2^{2\sqrt{n}}$. Then, to guarantee that attackers will take at least $2^\lambda$, we set $n = \frac{\lambda^2}{4}$. In practice, when we instantiate the scheme, we choose some value for $\lambda$, for instance, $128$. In this case, our $n$ should be $128^2 / 4 = 4096$. In other words, in this scenario, to guarantee a security of $128$ bits, we must choose the modulus size as $4096$ bits.
And about the comparisons... Well, you don't really want to compare the security parameters... You usually want to compare the keys' sizes and the timings (encryption, decryption, and key generation) to the same security parameter.
