Re: cryptology, complexity, and quantum cryptology

From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 02/15/05

  • Next message: Mitchell Harris: "Re: FW: Regular expressions / FSA question" 
    Date: Tue, 15 Feb 2005 09:22:50 -0500

    Mitch Harris wrote:
    > Ralph Hartley wrote:
    >> A *proof* that a cypher is NP complete to break, can make it
    >> vulnerable to known (or is it chosen?) plaintext attacks. The
    >> reduction used in the proof lets you solve the NP complete problem if
    >> you can get plaintext cyphertext pairs.
    >
    > That's neat. How does that work?

    I can only reconstruct this from vague memories, so excuse me if it is
    garbled. I also wish I could remember where I read this, but there is no
    chance of that.

    Suppose you have a public key cryptosystem where the secret is the solution
    to a (public) problem x from the class X. You want to be sure that applying
    the secret key is at least as hard as finding that solution, otherwise
    knowing that x is hard to solve is irrelevant.

    To prove that, you find a reduction from X to applying the secret key.
    Assuming x really is a hard, randomly chosen, instance of X, from a purely
    computational viewpoint you have proven the system hard to break.

    But suppose I can trick you into applying the secret key for me. I can
    apply the reduction to x, let you apply the secret key, and you will tell
    me the solution to x.

    Depending on whether the secret key is being used for signing or
    decryption, this is either a chosen plaintext or a chosen cyphertext attack.

    You would have been much better off with a system where all attempts over a
    long time to apply the secret key without knowing the solution to x had
    failed, but no proof by reduction was known or considered likely.

    No one knows how to break RSA without doing the factoring problem, but to
    prove that breaking RSA is really as hard as factoring, by finding a
    reduction, would be very bad news.

    There may be ways other than reduction to prove a problem hard, but they
    are very unusual.

    Ralph Hartley

  • Next message: Mitchell Harris: "Re: FW: Regular expressions / FSA question"

    Relevant Pages
    Loading