The microblog: 2019.06.23 20:01:25

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 I heard @ChrisPeikert give a talk to a 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 ( 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?