2022.06.01 19:16:00 (1532048328170479617) from Daniel J. Bernstein:
Yet another paper appears claiming to chop a further percentage out of lattice security levels against quantum attacks: https://eprint.iacr.org/2022/656 But we keep hearing that we're not supposed to worry about continual lattice security degradation. Let's look at the logic behind this.
2022.06.01 19:22:57 (1532050080559116289) from Daniel J. Bernstein:
First of all, we're told to ignore the (im)maturity of the security analysis, as reflected by the (in)stability of quantitative security levels. Quantification is dumbed down into a yes/no question: is this attack as expensive as a brute-force attack against a single AES-128 key?
2022.06.01 19:28:13 (1532051405267038208) from Daniel J. Bernstein:
Max cost of an AES-128 key search is 2^128 AES evaluations, about 2^143 bit ops. Quantum attacks sound much cheaper, about 2^64 quantum AES evaluations, but we're not supposed to worry: a qubit op probably costs roughly 2^40 bit ops; also, P-way parallel attacks gain only 2^64/P.
2022.06.01 19:32:37 (1532052509929353216) from Daniel J. Bernstein:
Whenever there's an improved quantum attack against lattices, we're told to ignore it because (1) the speedup is still smaller than the quantum AES speedup; (2) the lattice parameters are chosen to be as hard to break as AES-128 pre-quantum; (3) ergo they're also ok post-quantum.
2022.06.01 19:45:36 (1532055777338281984) from Daniel J. Bernstein:
But is it true that parameters are chosen this way? We already have ECC for pre-quantum security. Consider Lyubashevsky in https://archive.today/JVn42 saying that the lattice quantum speedup was "just a dozen or so bits" and, on this basis, recommending smaller lattice parameters.
2022.06.01 19:52:27 (1532057504015736832) from Daniel J. Bernstein:
Furthermore, it's not just quantum attacks getting better. During NISTPQC, Kyber's pre-quantum AES comparison has degraded from (1) "conservative" to (2) bleeding edge in bit ops to (3) apparently broken in bit ops and bleeding edge in AT, despite tweaks to try to add security.
2022.06.01 20:23:17 (1532065260886032384) from Daniel J. Bernstein:
The latest everything-is-fine narrative emphasizes that attacks aren't feasible yet. Cryptanalysts aren't even acknowledged for successfully breaking the original as-strong-as-AES claim. This is a big regression from the traditional emphasis on quantitative algorithm speedups.
2022.06.01 20:30:29 (1532067071911022593) from Daniel J. Bernstein:
Systematically encouraging publication of algorithm speedups is by far the community's best way of finding out whether proposed cryptosystems are breakable. This means measuring and acknowledging the speedups, not making one excuse after another to downplay or deny the speedups.