The new paper by Albrecht describes a new attack on "unusually" small secrets that are used in homomorphic encryption schemes.

In the paper the talk about binary secrets or LWE Normal form i.e $\sigma_s=\sigma_e$, error and secrets from the same distribution or secrets are in binary distribution. The online tool supports only the following distributions

"normal": normal form instances, i.e. the secret follows the noise distribution (alias:True) -"uniform": uniform mod q (alias:False) -(a,b): uniform in the interval `[a,…,b]` -((a,b), h)`` : exactly h components are ∈ [a,…,b]∖\{0\}, all other components are zero

I am wondering what will be the effect of this kind of attack on when $\sigma_s<\sigma_e$ but not binary. I don't have concrete parameter but if $\sigma_e/\sigma_s\approx 1000$ will this attack very significant advantage? As far as I understood from the paper, they use combinatorial algorithms like BKW to decrease the complexity of the Dual attack. But is it applicable when the distribution of error is not binary but from a discrete Gaussian?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.