2019.06.23 20:01:25 (1142855190174928897) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (1142851051751477248):
There's a previously identified problem for common dimensions such as 1024; see https://eprint.iacr.org/2016/360. I heard @ChrisPeikert give a talk to a https://nap.edu committee where he claimed "a few thousand" would allow proofs. I'd love to see a complete proof handling 10000.
2019.06.23 09:46:09 (1142700355484041216) from Daniel J. Bernstein:
Have you heard (repeatedly) about the worst-case-to-average-case reduction for LWE? Sarkar and Singha (https://eprint.iacr.org/2019/728) say that a step in Regev's proof requires the lattice dimension to be at least 187150. New research question: Can an optimized proof get down to 10000?
2019.06.23 19:44:58 (1142851051751477248) from "Paulo Barreto (@pbarreto)":
Why stop at 10000? Can a really optimized proof get down to 1024 or less?