Security: No "Natural Proof" that certain computational problems used in cryptography are hard to solve

ACM Group Honors Research Team for Rare Finding in Computer Security
AScribe Newswire (05/16/07)

ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) announced that Alexander A. Razborov and Steven Rudich, two computer scientists who developed a rare finding that addresses the P vs. NP Problem, will receive the 2007 Godel Prize for outstanding papers in theoretical computer science at the ACM Symposium on Theory of Computing, which takes place June 11-13, 2007, in San Diego. P vs. NP is a fundamental problem in computer and network security techniques and many security optimization techniques. For years, questions on the limits of proof and computation raised by P vs. NP has hindered computer scientists. These questions affect complex mathematical problems common in creating security solutions for ATM cards, computer passwords, and electronic commerce. In a paper titled "Natural Proofs," originally presented at the ACM Symposium on Theory of Computing in 1994, Razborov and Rudich addressed what is widely considered to be the most important question in computing theory, and is one of seven $1 million reward Prize Problems by the Clay Mathematics Institute in Cambridge, Mass. The questions asks if the solution to a question is easily checked, is the problem easy to solve? Razborov and Rudich proved that there is no "Natural Proof" that certain computational problems used in cryptography are hard to solve, and though they are widely thought to be unbreakable, there is no natural proof that they are secure. Such cryptographic methods are critical to electronic commerce. Razborov is the leading researcher at the Russian Academy of Science Steklov Mathematical Institute in Moscow, Russia, and Rudich is an associate professor of computer science at Carnegie Mellon University.
Click Here to View Full Article