What happens if P=NP?
Results 1 to 4 of 4

Thread: What happens if P=NP?

Hybrid View

  1. #1

    What happens if P=NP?

    Did you know there is a remote possibility that all codes are weaker than your expect and there is nothing you can do about it? Believe it or not, there is an unsolved math problem that says this is possible.

    Few of us realize how much mathematics lie behind our ciphers. The P vs. NP Problem has been out there so long that few cryptologists have plans should P=NP. The P vs. NP Problem basically asks how quickly can you solve a problem. Should P=NP be the answer, then all codes are weaker than one would expect.

    This article is a contingency plan for information security experts should they ever have to deal with P=NP. First, do no panic. Only if a faster integer factorization algorithm is found will you have to worry immediately. The solution was not found in a day, nor will it be the end of the universe. It will be a long-term threat.

    You can reassure everyone that there is a major threat on the horizon, no one can exploit it for now, so they are safe. You are aware of the issue and are taking all precautions.

    Next, do your home work. Just because P=NP says our ciphers are weaker, it does not show us how to use this information to attack codes. This is because we know that if any NP or EXPONENTIAL time problem can be reduced to P, P=NP. Chances are it will not have any immediate cryptologic usefulness save P=NP.

    Given the number of encryption algorithms available, you have some wiggle room because codes will most likely be attacked in groups, so some codes will become weaker as new math research becomes available. This means math research is no longer option in being ignored.

    Also, lawyers will have a field day. Since there are secure data laws, they will have to tell you what your legal risks are. Although the courts will most likely allow a grace period since it would jeopardize many companies to get back into compliance.

    This plan is sufficient to satisfy your needs should you have to react to P=NP. Given the nature and numbers of those who have big stakes on the P vs. NP Problem, should P=NP happen everyone will have to respond to the same news. Since this is a low probability event, P=NP would force all who have a stake to get the same news causing a denial of service attack on all relevant information. This plan will help you avoid that and be prepared should P=NP happen.

  2. #2
    StOrM™
    Join Date
    Aug 2004
    Posts
    1,003
    Parth Maniar,
    CISSP, CISM, CISA, SSCP

    *Thank you GOD*

    Greater the Difficulty, SWEETER the Victory.

    Believe in yourself.

  3. #3
    StOrM™
    Join Date
    Aug 2004
    Posts
    1,003
    I just realized i need some soup ..
    Parth Maniar,
    CISSP, CISM, CISA, SSCP

    *Thank you GOD*

    Greater the Difficulty, SWEETER the Victory.

    Believe in yourself.

  4. #4
    Super Moderator: GMT Zone nihil's Avatar
    Join Date
    Jul 2003
    Location
    United Kingdom: Bridlington
    Posts
    17,191
    What happens if P=NP?
    That's an easy one.............I take the proof to the Clay Mathematics Institute and collect the $1 million (USD) they are offering for the solution. I am afraid it will have to wait a bit though as I am still working on a quantitative solution to Fermat's Last Theorem

    I was always taught that you should assume that any crypto algorithm can be cracked; some just take longer than others. That is the real issue IMO: is your encryption strong enough for your purpose?

    In this matter you need to consider the usefulness of the data, its value or sensitivity, how much effort a potential attacker is prepared to devote to cracking it, and what time frame is involved. Basically this would be a part of your risk analysis.

    At the end of the day you will still get back to the question of how the bad guys got hold of your data in the first place..............cryptography should not be your first line of defence.

    Also, lawyers will have a field day. Since there are secure data laws, they will have to tell you what your legal risks are. Although the courts will most likely allow a grace period since it would jeopardize many companies to get back into compliance.
    I am not aware of any European legislation that even mandates encryption, let alone the algorithms to be used. This isn't surprising given that lawyers and courts don't "do" complex mathematics They also avoid IT technical issues where possible.

    The issue will be the same as it is now...............did you practice due diligence? In Europe at least, we haven't reached the stage where the victim is the criminal So long as you have taken reasonable steps to secure your data you will not be blamed for the criminal being smarter than you.

    EDIT:

    should you have to react to P=NP
    Nobody will................it is irrelevant because it is simply a mathematical concept rather than an actual compromise. I am not really concerned if it would take someone with the resources of the CIA 500 years to crack my data rather than 5,000.

    1. They still have to get their hands on the data.
    2. They have to crack it whilst it is still of value.

    In real life, not many data are encrypted, other than whilst in transit. Changing your data transmission encryption method is not going to cause any kind of global meltdown, as it is pretty much transparent.
    Last edited by nihil; August 17th, 2009 at 02:36 PM.
    If you cannot do someone any good: don't do them any harm....
    As long as you did this to one of these, the least of my little ones............you did it unto Me.
    What profiteth a man if he gains the entire World at the expense of his immortal soul?

Similar Threads

  1. P=NP?
    By Overlord_77520 in forum Cryptography, Steganography, etc.
    Replies: 6
    Last Post: January 31st, 2008, 02:59 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •