Good news for blockchains! Really?
The NZZ recently reported that Norbert Blum (University of Bonn) appears to have solved the P vs NP Problem, one of the Millennium Problems. The NZZ article also claims that this proof indicates that cryptographic methods such as those applied in blockchains will remain secure. The graphic was cleverly borrowed from Wikipedia and enhanced by the NZZ designers. However, a glance at the Wikipedia article immediately reveals that the above conclusion regarding security is false: it’s described as a common misconception. There was never anything to be concerned about from this quarter.
In his article in the NZZ science section, George Szpiro writes: ‘If this proof turns out to be correct and complete, cryptographers can breathe a sigh of relief, as current encryption methods – for example, those used for online banking or internet shopping payments – will remain secure.’ The Wikipedia article describes ‘If P=NP, all cryptographic ciphers can be broken’ as a ‘common misconception’, with the following explanation: ‘A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. For example, ciphers with a fixed key length, such as Advanced Encryption Standard, can all be broken in constant time (and are thus already in P), though with current technology that constant may exceed the age of the universe.’
LINKS:
https://www.nzz.ch/wissenschaft/p-versus-np-ist-das-zweite-der-sieben-millenniums-probleme-geknackt-ld.1311307
https://en.wikipedia.org/wiki/NP-completeness
https://arxiv.org/abs/1708.03486
http://shell.cas.usf.edu/~wclark/baez2000problems.html
