On the Concrete Security of LWE with Small Secret
Calvin Lab Auditorium
This talk will present our experimental study of the success probability of BKZ2.0 on uSVP lattices, with the motivation of understanding the concrete security of LWE in the setting of homomorphic encryption where the secret vector is often sampled from the binary or ternary distribution. We run experiments by generating instances of LWE in small dimensions, where we consider secrets sampled from binary, ternary or discrete Gaussian distributions. We convert each LWE instance into a uSVP instance and run the BKZ2.0 algorithm to find an approximation to the shortest vector. When the attack is successful, we can deduce a bound on the Hermite factor achieved for the given blocksize. We find that the security levels for certain values of q and n may be smaller than expected, due to higher success probabilities for small blocksizes 30, 35, 40, 45 on these uSVP lattices. We also ran our experiments on generated instances of the TU Darmstadt LWE challenges and observed significantly lower running times for successful attacks on those instances generated with the binary distribution for the secret vector. We observe that sampling the secret from the discrete Gaussian error distribution yields greater security than the binary or ternary distributions for the same set of parameters. Joint work with Kristin Lauter, Hao Chen, and Yongsoo Song.