2
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't believe that it is universally true that people specify $\lambda$ in such a way that the best known attack takes $O(2^\lambda)$ time; one reason for this would be the concern if someone were to find a somewhat better attack, they'd need to redo the mapping between $\lambda$ and the actual sizes within the primitive (rather than just saying "use a bigger $\lambda$). Hence, I suspect that comparing two different protocols with the same $\lambda$ might be quite misleading... $\endgroup$ – poncho May 16 '17 at 17:25
  • $\begingroup$ @poncho Notice that choosing $\lambda$ such that the underlying problem is hard is somehow the same thing, since we estimate the hardness of a problem based on the known algorithms to it, right? $\endgroup$ – Hilder Vítor Lima Pereira May 16 '17 at 21:20
  • 1
    $\begingroup$ That'd make sense, if you were comparing things that used the same hard problem; it's trickier if (say) you are comparing something that used the LWE problem to one which used the SIDH assumption... $\endgroup$ – poncho May 16 '17 at 21:22
  • $\begingroup$ And I think I miss understood what you said... When some new attack (or new algorithm to the hard problem in which the scheme relies on) is discovered, we don't need to update $\lambda$, we need to update the other parameters to achieve the same level of security (ist est $\lambda$). $\endgroup$ – Hilder Vítor Lima Pereira May 16 '17 at 21:23
  • $\begingroup$ @poncho I agree that comparisons between different primitives and protocols are complicated... There are some details that must be taken into account (for instance, maybe the parameters of one were developed to guarantee CPA security and the other to guarantee CCA). But if all those details are clear, I think we could compare... $\endgroup$ – Hilder Vítor Lima Pereira May 16 '17 at 21:37

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.