Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. However, if all answers can be found easily as well as checked, if only we knew how, then P equals NP. The area has intrigued mathematicians and computer scientists since Alan Turing, in 1936, found that it’s impossible to decide in general whether an algorithm will run forever on some problems. Resting on P versus NP is the security of all online transactions which are currently encrypted: if it transpires that P=NP, if answers could be found as easily as checked, computers could crack passwords in moments.
Tagged with “encryption” (4)
Who’s right in Apple’s court battle with the FBI over California shooter’s phone data?
Recent revelations about the extent of NSA surveillance have put even the standards by which encryption systems are designed into question. Encryption experts Matthew Green, Phillip Zimmerman, and Martin Hellman discuss what makes a code secure and the limits of privacy in the modern age.
The NSA can already crack most cryptography; now it’s working on a quantum computer to bust the rest. Is it the end of for-your-eyes-only?
The world’s been up in arms because the US National Security Agency, the NSA, has been tapping and hacking and buying its way into private data all over the place. What if it didn’t have to tap and hack and buy? What if the NSA could build a quantum computer that could break any encryption out there and walk right in? The latest news out of the revelations from super-leaker Edward Snowden says it’s trying. Racing for a computer exponentially more powerful than anything now. This hour On Point: the NSA, quantum computing, and the future of cryptography.
– Tom Ashbrook
Steven Rich, database editor for the investigative at The Washington Post. (@dataeditor)
Seth Lloyd, professor of mechanical engineering at the Massachusetts Institute of Technology.
Matthew Green, cryptographer and research professor at Johns Hopkins University. Author of the blog, “A Few Thoughts On Cryptographic Engineering.” (@MatthewDGreen)
From Tom’s Reading List
Washington Post: NSA seeks to build quantum computer that could crack most types of encryption — “The development of a quantum computer has long been a goal of many in the scientific community, with revolutionary implications for fields such as medicine as well as for the NSA’s code-breaking mission. With such technology, all current forms of public key encryption would be broken, including those used on many secure Web sites as well as the type used to protect state secrets.”
Wired: The quest to make encryption accessible to the masses — “Kobeissi’s challenge, to make encrypted online messaging user-friendly, has long been a bugbear of the crypto community. A paper, written in 1999, demonstrated that the encryption program PGP completely baffled most users in a series of tests. The study, now fourteen years old, is still frequently cited today as a long-unanswered call to arms.”
A Few Thoughts On Cryptographic Engineering: How does the NSA break SSL?
— “You see, the NSA BULLRUN briefing sheet mentions that NSA has been breaking quite a few encryption technologies, some of which are more interesting than others. One of those technologies is particularly surprising to me, since I just can’t figure how NSA might be doing it. In this extremely long post I’m going to try to dig a bit deeper into the most important question facing the Internet today. Specifically: how the hell is NSA breaking SSL?”