4 ms·

The most powerful cyberweapon is making sure every human understands an inkling of number theory

wizzwizz4 5y ago
So everyone's invented their own cryptography. Great! I'll just buffer-overflow the TCP stack and let myself in; then I can read all their messages after they've decrypted them. Rock, meet paper.
- eointierney 5y ago
  So we have evolved best practice in secure commumication using the most rigorous scientific review methods available to math. We just need to help each other understand how we're modelling this stuff.
  - wizzwizz4 5y ago
    All cryptography is based on the assumption that the inverse of some operation is hard to compute, because nobody's found an easy way to do it (yet). RSA is based on the assumptions that factoring prime numbers and finding discrete logarithms are both hard. ECC is based on the assumption that the subtraction analogue of that weird additiony thingy is hard. Afaik, neither of these things has been proven.
    - dane-pgp 5y ago
      > Afaik, neither of these things has been proven. It's not even clear (at least to me) what a proof of "difficulty" would look like. You would have to prove that no mathematical process could exist that was capable of (for example) factoring a composite number N in less than M steps (where M is a function of N), and prove that each step has some minimum energy or time requirement, to ground the "difficulty" in terms of things that we can use our current understanding of physics to reason about.
      - AlexCoventry 5y ago
        It would be a reduction of discrete-log/factorization to some algorithm with known lower bounds on runtime/space for a given probability of success.
        dane-pgp 5y ago
        But could there ever be a guarantee that no more efficient algorithm could be found? I agree that, given an algorithm, you can reason about the runtime/space/probability requirements that it places on an implementation, but you also have to contend with different models of computation. According to Wikipedia, the "quantum complexity-theoretic Church–Turing thesis" states that: "A quantum Turing machine can efficiently simulate any realistic model of computation."[0] but even assuming this is true, and that we could build a practical general purpose quantum computer, the word "efficiently" here only means "up to polynomial-time reductions", and I don't think we can know in advance what polynomial-time reductions could be discovered. [0] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V...
      - dboreham 5y ago
        Something like this? https://en.m.wikipedia.org/wiki/Halting_problem https://en.m.wikipedia.org/wiki/Halting_problem
        dane-pgp 5y ago
        We can prove that it is a logical impossibility for some algorithm to exist, but I don't think we can say, given an algorithm with a certain set of steps, that there isn't an equivalent algorithm that requires fewer steps. Also, "steps" here would have to be measured in terms of operations on a physical machine (or at least an idealised perfectly efficient physical machine), but different architectures would allow different operations, and that's before we start considering different models of computation.

So everyone's invented their own cryptography. Great! I'll just buffer-overflow the TCP stack and let myself in; then I can read all their messages after they've decrypted them. Rock, meet paper.

eointierney 5y ago
So we have evolved best practice in secure commumication using the most rigorous scientific review methods available to math. We just need to help each other understand how we're modelling this stuff.
- wizzwizz4 5y ago
  All cryptography is based on the assumption that the inverse of some operation is hard to compute, because nobody's found an easy way to do it (yet). RSA is based on the assumptions that factoring prime numbers and finding discrete logarithms are both hard. ECC is based on the assumption that the subtraction analogue of that weird additiony thingy is hard. Afaik, neither of these things has been proven.
  - dane-pgp 5y ago
    > Afaik, neither of these things has been proven. It's not even clear (at least to me) what a proof of "difficulty" would look like. You would have to prove that no mathematical process could exist that was capable of (for example) factoring a composite number N in less than M steps (where M is a function of N), and prove that each step has some minimum energy or time requirement, to ground the "difficulty" in terms of things that we can use our current understanding of physics to reason about.
    - AlexCoventry 5y ago
      It would be a reduction of discrete-log/factorization to some algorithm with known lower bounds on runtime/space for a given probability of success.
      - dane-pgp 5y ago
        But could there ever be a guarantee that no more efficient algorithm could be found? I agree that, given an algorithm, you can reason about the runtime/space/probability requirements that it places on an implementation, but you also have to contend with different models of computation. According to Wikipedia, the "quantum complexity-theoretic Church–Turing thesis" states that: "A quantum Turing machine can efficiently simulate any realistic model of computation."[0] but even assuming this is true, and that we could build a practical general purpose quantum computer, the word "efficiently" here only means "up to polynomial-time reductions", and I don't think we can know in advance what polynomial-time reductions could be discovered. [0] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V...
    - dboreham 5y ago
      Something like this? https://en.m.wikipedia.org/wiki/Halting_problem https://en.m.wikipedia.org/wiki/Halting_problem
      - dane-pgp 5y ago
        We can prove that it is a logical impossibility for some algorithm to exist, but I don't think we can say, given an algorithm with a certain set of steps, that there isn't an equivalent algorithm that requires fewer steps. Also, "steps" here would have to be measured in terms of operations on a physical machine (or at least an idealised perfectly efficient physical machine), but different architectures would allow different operations, and that's before we start considering different models of computation.