search

lducas / FHEW

Other
221 stars 46 forks source link

Security parameter? #7

Closed matlink closed 8 years ago

matlink commented 8 years ago

In your paper, you talk about the security of your scheme, leading to determine the value of the scheme parameters. However, I can't see where the security parameter (say lambda=80 nowadays) appears.

lducas commented 8 years ago

As a ``proof of concept'', the concrete security has not been studied very thoroughly, but we give an estimate of 2^100 nodes to enumerate to break the scheme, so at least 100 bits of security against the current state of the art in cryptanalysis. This is most likely far from a definitive answer, as I expect significant progress on attacks on all lattice assumptions.

Please read this 100-bit of security as an estimate for comparison with other FHE schemes and scientific discussion. IMHO none of the FHE parameters proposed in the literature are conservative enough for serious deployment. I can give you pointers to a much more conservative security estimation methodology if you are targeting deployment.

2016-04-26 9:19 GMT+01:00 Matlink notifications@github.com:

In your paper, you talk about the security of your scheme, leading to determine the value of the scheme parameters. However, I can't see where the security parameter (say lambda=80 nowadays) appears.

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/lducas/FHEW/issues/7

matlink commented 8 years ago

Alright, helpful answer. I do not target to deploy such a scheme, however I needed the security parameter estimation to compare it with other FHE scheme published backwards and afterwards on practical execution times on the same machine.

matlink commented 8 years ago

Do you think that the security parameter can be changed by any way?

lducas commented 8 years ago

It is tricky. In theory, of course it can, but in practice everything is fined tuned according to architecture and parameters constraints. For example, increasing q to much will make the double-precision FFT having more errors. I think the performancesof quad-double FFT are disastrous.

If you want to decrease security, then, this is a bit more doable. One could for sure decrease n a bit, but N must be a power of two (unless you start making very big changes to the scheme). I remember trying N=512, but this lead to very low security...

What is your target security parameter ?

Best -- Leo

2016-05-03 9:56 GMT+02:00 Matlink notifications@github.com:

Do you think that the security parameter can be changed by any way?

— You are receiving this because you commented. Reply to this email directly or view it on GitHub https://github.com/lducas/FHEW/issues/7#issuecomment-216462051

matlink commented 8 years ago

What is your target security parameter ?

10 and 128

lducas commented 8 years ago

I'm not sure 10 means anything: evaluating the scheme itself is already around 2^30 operations !

For 128, I am afraid one would start to need larger N = 2048, and high-precision FFT. It is not impossible, but it would need changing a lot of things, replacing FFT by NTT, etc...

2016-05-03 18:32 GMT+02:00 Matlink notifications@github.com:

What is your target security parameter ?

10 and 128

— You are receiving this because you commented. Reply to this email directly or view it on GitHub https://github.com/lducas/FHEW/issues/7#issuecomment-216586633

matlink commented 8 years ago

Well, if to set the lambda the scheme must be re-written then it's not within my capabilities. lambda=10 was just a toy example I use in other schemes to compare very very inefficient schemes with usable ones.