4 ms·
Even a quantum computer?
by rospaya 5y ago
Even a quantum computer?
- seibelj 5y agoMy understanding is that one-way functions are not broken by quantum computers.
- thaumasiotes 5y agoMy understanding is that in the general case you can see a quadratic speedup, so a 256-bit search space would suddenly collapse to what is effectively a 128-bit search space. Not a big deal by itself.
- tromp 5y agoBitcoin's hashcash PoW is not a 256-bit search problem though. At current difficulty levels, it's closer to an 86-bit problem, so Grover's algorithm reduces that to the equivalent of a 43 bit search space.
- Filligree 5y agoDepends on the function. But not sha256, no. I think you'd almost have to design it to be vulnerable, if you want that.
- MauranKilom 5y agoIt reduces the strength of SHA256 to that of SHA128, roughly speaking. 2^128 is still outside any practical reach whatsoever. (Google breaking SHA-1 after cryptanalysis still required some 2^60 operations iirc).
- ben_w 5y agoI always assume security is worse than the most effective known attack, but IIRC it’s currently thought to be safe against quantum computers: https://eprint.iacr.org/2016/992 https://eprint.iacr.org/2016/992 2^166 ~= give a separate quantum computer that does as many QOPS as the the most powerful supercomputer does FLOPS to each human who has ever lived and have each of them run for a thousand times the age of the universe.
- unixhero 5y agoAsk Grover, google it
- deleted 5y ago[deleted]
- ohhhhhh 5y agoeven if that did happen in the far future, there are quantum proof encryption methods
- a1369209993 5y agoIIRC, a quantum computer reduces preimage attacks (first or second) to the difficulty of collision attacks, but doesn't improve collision beyond the best classical attacks, which can be run on faster and cheaper hardware. It also may or may not benefit from any cryptanalysis applicable to collision attacks. So if you're secure against (classical) collision attacks, you don't need to worry about quantum attacks (collision or preimage).
- zinekeller 5y agoThe main reason that asymmetric (RSA, eliptic curves) encryption are broken (on quantum computers) is simply due to relying on certain assumptions that haven't been fully proven (and instead has been disproven over time). Symmetric and one-way functions are provably secure, within those characteristics that they define. Notably, they are not designed with "until the end of the universe" promise (and the only proven "until the end of the universe" encryption anyway is a proper one-time pad (or disk) encryption). The reason that certain hashing and encryption algorithms have been broken are due to both compromises inherent in design goals (notably, AES have been simplified from the reference encryption Rjindael to ease up hardware acceleration) and the march of technology simply rolling with faster chips. Quantum computing can speedup this process a bit (a quadratic speedup in most cases), but not enough to outbeat these types of encryption.
- tptacek 5y agoThe march of technology has done essentially nothing to weaken AES against direct attacks. AES, of course, has not been broken the way SHA-1 and MD5 were.