1
$\begingroup$

I'm computer guy having trouble with cryptography.

I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions.

I was implementing Threshold version of BGV encryption [AJW12] using HElib optimized under the RLWE assumption, and I found out that [AJW12] proved the security under the LWE assumption.

A paper [LN16] says that the RLWE is a special instance of the LWE problem.

So, I think that [AJW12] encryption under RLWE parameters is still secure, but I'm not sure.

Am I right?

$\endgroup$
1
$\begingroup$

Am I right?

Possibly, but it's not guaranteed, even if we assume that LWE is secure.

RLWE is a special instance of LWE; however that doesn't mean that RLWE is secure if LWE is. The LWE assumption holds if we have a random instance; that is, one chosen from a specific probability distribution. The RLWE problem has a different probability distribution; one in which the vast majority of LWE instances have probability 0. The probability that the LWE will choose an instance which has a nonzero probability for being a RLWE instance is negligible. It may be that the RLWE instances happen to be weak; that would not practically impact the security of LWE.

Now, it's not known that any such weakness applies specifically to RLWE; however it's also not proven that there isn't, either.

$\endgroup$

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.