2022.01.20 13:52:19 (1484146772624633857) from Daniel J. Bernstein:
Heard that MLWE is provably at least as safe as RLWE? Also less structured, so within lattice KEMs it's the more conservative choice? One easy way to understand the fundamental flaw in this argument is to look at what the same argument says for pre-quantum discrete-log systems.
2022.01.20 13:52:54 (1484146920855539715) from Daniel J. Bernstein:
Imagine that your discrete logarithms are using the traditional multiplicative group of an n-bit prime field F_p, as in the original DH paper. A salesman is trying to convince you that it's safer to switch to some matrix version of DH using r-by-r matrices over an n/r-bit field.
2022.01.20 13:53:27 (1484147056658681859) from Daniel J. Bernstein:
"Matrices are guaranteed to be at least as secure as fields," the salesman tells you. "Look, here's a simple proof." The proof says that if the n/r-bit field is secure then matrices over the n/r-bit field must be secure too. But this is useless: the n/r-bit field is too small!
2022.01.20 13:53:53 (1484147169309310976) from Daniel J. Bernstein:
"I understand your concern," the salesman says. "Look at this new proof I just received. Simple _and_ preserves size! Definitely the proof for sophisticated customers like you. This proof shows that these matrices are guaranteed to be at least as secure as fields _with n bits_."
2022.01.20 13:54:26 (1484147306014248966) from Daniel J. Bernstein:
Say the n/r-bit field is F_q. The field F_(q^r) has about n bits. The proof says that multiplication by an element of the field F_(q^r) can be viewed as an r-by-r matrix over F_q, so if there's a security problem with matrices then there's also a security problem with F_(q^r).
2022.01.20 13:54:55 (1484147428827664385) from Daniel J. Bernstein:
But wait a minute. You weren't using F_(q^r). You were using a prime field F_p. F_(q^r) is a special type of n-bit field, with F_q as a subfield. What happens if attackers can exploit the presence of this small field F_q to break F_(q^r), and also to break the matrix system?
2022.01.20 13:55:19 (1484147526345191426) from Daniel J. Bernstein:
In that scenario, the proof is simply relating one weak system to another weak system. The proof relies on exactly the F_q structure that the attacker is exploiting. The salesman is using this proof to convince you to add that structure, switching away from a stronger system!
2022.01.20 13:55:41 (1484147621300113409) from Daniel J. Bernstein:
This isn't hypothetical. Exploiting subfields is a major theme of today's discrete-log attacks. F_(q^r) is now known to be weak for many values of r, sometimes _very_ weak. Also, a 1997 paper by Menezes and Wu shows that matrices don't add any security compared to fields.
2022.01.20 13:56:12 (1484147750987911171) from Daniel J. Bernstein:
One can see the fundamental flaw in the salesman's logic without seeing any of the attacks. The proof was portrayed as comparing the matrices to the entire class of fields with n bits, but looking at the proof shows that it compares only to specially structured fields F_(q^r).
2022.01.20 13:56:43 (1484147881703395328) from Daniel J. Bernstein:
This example also shows how dangerous it is to measure cryptography by its success in writing down "security proofs", judging systems as less risky when they have more "security proofs". What these proofs are proving isn't security. Enabling proofs often means adding weaknesses.