4 ms·
The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum p
by Ar-Curunir 3y ago
The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum polynomial time.
The proposed post-quantum encryption schemes use a much smaller noise ratio which (at the moment) is not affected by these attacks.
- da-bacon 3y agoI didn’t say the runtime did I? The approximation ratio went from exponential to polynomial noise ratio. This just went from 2^n to n^4.5 and everyone seems to say “oh this is fine”.
- Ar-Curunir 3y agoThe attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.
- da-bacon 3y agoYes sub exponential which is splitting hairs. Exp(O(n log log n / log n)). Thanks for the acknowledgment that I didn’t say runtime.