27 ms·
In brief, a quantum computer of ~10000 qubits running Grover's algorithm can find a structured preimage in expected time O(2^(N/2)), which breaks the security c
by Robin_Message 16y ago
In brief, a quantum computer of ~10000 qubits running Grover's algorithm can find a structured preimage in expected time O(2^(N/2)), which breaks the security claims of 11 of the candidates, who claim no attack better than brute force is possible (which is O(2^N)).
Of the other three, 2 make no explicit claim, and only one explicitly states the quantum attack.
That said, O(2^(N/2)) on N of 224 bits is still O(2^112) operations on a quantum computer several orders of magnitude larger than those we have already, so the problem here is an inaccurate claim of security by the submissions, not a practical attack. (2^112 is a million computers, working at one operation per nanosecond, running for 164646653302 years, but attacks do only get better...)