5 ms·

I have a problem with encryption being breakable, regardless of who's doing the breaking. I want encryption to be mathematically solid with the only option bein

by smtddr 13y ago

I have a problem with encryption being breakable, regardless of who's doing the breaking. I want encryption to be mathematically solid with the only option being brute-force older-than-age-of-earth time. When we get to quantum computing, then I don't know what we'll do...

gizmo686 13y ago
Quantom computing cannot break all of crypto. Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
- mcherm 13y ago
  > Quantom computing cannot break all of crypto. Correct (except for the spelling of "Quantum"). > Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers. An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better. Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer. For more details, see http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf or frankly ANYTHING written by Scott Aaronson (http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/).
  - mcpherrinm 13y ago
    > the ones that CANNOT be done on polynomial time is "NP". I see you've solved one of the great open problems! NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
    - Filligree 13y ago
      The latter of which sounds suspiciously like what a quantum computer does. How sure are we that BQP != NP?
      - mcppherrinrinm 13y ago
        We aren't: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy. I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
        Filligree 13y ago
        I've seen post-selection demonstrated in a laboratory. It definitely isn't just a philosophical construct, except inasmuch as what it says about time making people want it to be less than real, and logic doesn't work that way. As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
      - gizmo686 13y ago
        The latter of which is exactly what a quantom computer does. The problem is that when we make a measurement, we randomly select one of the execution paths and see its result. The problem is that once we make a measurement, we would have to repeat the experiment in order to make another measurement.
tubbzor 13y ago
Everyone focuses on the decrypting power of quantum computing, which is warranted as it will break _modern_ cryptography (in theory). However, think about the encrypting power a quantum computer will have; being able to generate completely random keys among other facets of crypto that seem implausible with modern computers. I think it will just open the door to a whole new science of crypto we haven't reached yet.
- Everlag 13y ago
  The most concerning point is that transitional point where all of the old, quantum breakable, standards are in place when quantum systems roll around. Either everything will fall apart or we'll have wised up before hand.
  - tubbzor 13y ago
    We've seen this phenomenon, just on a smaller scale. When an encryption standard is compromised, people either switch to something stronger or face the consequences of essentially leaving their data in the open. DES was an acceptable standard until the late 90s, but you'd be foolish to use it now. RSA is the accepted standard now, but it is said to fall within 5 years or so. At that point, people will either start paying for a license to use Elliptic curve encryption algos or something new will be found. It's a vicious cycle, but I certainly don't think encryption ends with quantum computing, but maybe disrupts it quite a bit for some time.
6d0debc071 13y ago
If we get quantum cryptography out the door in a reasonable space of time, then we can do secure one time pad exchanges on there. Doesn't matter what you throw at that, since with the right keys you can derive any message of the same length from it.

by smtddr 13y ago

gizmo686 13y ago

Quantom computing cannot break all of crypto. Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP

mcherm 13y ago
> Quantom computing cannot break all of crypto. Correct (except for the spelling of "Quantum"). > Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers. An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better. Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer. For more details, see http://www.scottaaronson.com/papers/bqpph.pdf http://www.scottaaronson.com/papers/bqpph.pdf or frankly ANYTHING written by Scott Aaronson (http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/).
- mcpherrinm 13y ago
  > the ones that CANNOT be done on polynomial time is "NP". I see you've solved one of the great open problems! NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
  - Filligree 13y ago
    The latter of which sounds suspiciously like what a quantum computer does. How sure are we that BQP != NP?
    - mcppherrinrinm 13y ago
      We aren't: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy. I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
      - Filligree 13y ago
        I've seen post-selection demonstrated in a laboratory. It definitely isn't just a philosophical construct, except inasmuch as what it says about time making people want it to be less than real, and logic doesn't work that way. As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
    - gizmo686 13y ago
      The latter of which is exactly what a quantom computer does. The problem is that when we make a measurement, we randomly select one of the execution paths and see its result. The problem is that once we make a measurement, we would have to repeat the experiment in order to make another measurement.

tubbzor 13y ago

Everyone focuses on the decrypting power of quantum computing, which is warranted as it will break _modern_ cryptography (in theory). However, think about the encrypting power a quantum computer will have; being able to generate completely random keys among other facets of crypto that seem implausible with modern computers. I think it will just open the door to a whole new science of crypto we haven't reached yet.

Everlag 13y ago
The most concerning point is that transitional point where all of the old, quantum breakable, standards are in place when quantum systems roll around. Either everything will fall apart or we'll have wised up before hand.
- tubbzor 13y ago
  We've seen this phenomenon, just on a smaller scale. When an encryption standard is compromised, people either switch to something stronger or face the consequences of essentially leaving their data in the open. DES was an acceptable standard until the late 90s, but you'd be foolish to use it now. RSA is the accepted standard now, but it is said to fall within 5 years or so. At that point, people will either start paying for a license to use Elliptic curve encryption algos or something new will be found. It's a vicious cycle, but I certainly don't think encryption ends with quantum computing, but maybe disrupts it quite a bit for some time.

6d0debc071 13y ago

If we get quantum cryptography out the door in a reasonable space of time, then we can do secure one time pad exchanges on there. Doesn't matter what you throw at that, since with the right keys you can derive any message of the same length from it.