News for hackers. Stuff that matters.
Re:The battle for the world’s most powerful cyberweapon by wizzwizz4 on Friday January 28, 2022 @09:02PM (#30123031)
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.

Re:The battle for the world’s most powerful cyberweapon by dane-pgp on Friday January 28, 2022 @09:58PM (#30123351)
> 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.

Re:The battle for the world’s most powerful cyberweapon by AlexCoventry on Friday January 28, 2022 @11:28PM (#30123792)
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.
Re:The battle for the world’s most powerful cyberweapon by dane-pgp on Saturday January 29, 2022 @01:23PM (#30128870)
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#V...

Re:The battle for the world’s most powerful cyberweapon by dboreham on Friday January 28, 2022 @11:35PM (#30123822)
Re:The battle for the world’s most powerful cyberweapon by dane-pgp on Saturday January 29, 2022 @01:30PM (#30128942)
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.