21–30 of 41 posts
Earlier quoted context omitted.
Any time I hear something sensational about quantum computing, I check Scott Aaronson's blog for the real story. Here's his blog post on this topic: https://www.scottaaronson.com/blog/?p=3827 .
That webpage is the hardest thing to read on a phone screen. Dark grey on black, why would he ever think that's a good choice??
Can't quantum computers be simulated on classical computers? Doesn't that mean that any problem solvable by a quantum computer can be solved by a classical computer, given enough resources? If so, isn't the headline that "Only Quantum Computers Will Ever Be Able to Solve" misleading? I don't know much about this subject, so I'm assuming one of my assumptions is wrong.
This is basically the TCS version of a clickbait headline. It's a separation of BQP and PH by an oracle. Certainly a nice result, but to put it into context, we also have a separation of P and NP by an oracle. Yet, we are very far away from actually proving that P and NP are distinct.
Any time I hear something sensational about quantum computing, I check Scott Aaronson's blog for the real story. Here's his blog post on this topic: https://www.scottaaronson.com/blog/?p=3827 .
Quantum computing is coming. How quickly isn’t clear, although the first versions of this technology are expected to begin showing up over the next few years, with the rollout across more markets and applications expected by the middle of the next decade. https://semiengineering.com/quantum-computing-becoming-real/
This is basically the TCS version of a clickbait headline. It's a separation of BQP and PH by an oracle. Certainly a nice result, but to put it into context, we also have a separation of P and NP by an oracle. Yet, we are very far away from actually proving that P and NP are distinct.
Any time I hear something sensational about quantum computing, I check Scott Aaronson's blog for the real story. Here's his blog post on this topic: https://www.scottaaronson.com/blog/?p=3827 .
My first thought was "Oh, I have forgotten the address of that nice blog of that Prof. with all kind of interesting CS stuff that shows 'NP' and 'BQP' and 'P' connected with lines in the right upper corner. That blog will likely have more useful insights. How to find that blog again? I have so many bookmarks and not all tagged correctly, hmm".
But after reading the article and coming back here there is the right link near the top! :-)
People on HN are so great, love that! (Especially when they think in the same direction as me^^).
Imagine you have two random number generators, each producing a sequence of digits. The question for your computer is this: Are the two sequences completely independent from each other, or are they related in a hidden way? That, right there, should tell absolutely everyone, by intuition alone, that, despite assurances from industry experts that flaws leading to breaks ( plain-text discovery faster than brute force )…
For the benefit of us with a poor intuition, do you mind walking us through how you arrived at your conclusion?
The "not-so-random-but-seemingly-unrelated" nonces possessing relatable properties that permit discovery of secret keys, through little known, obscure relationships, preferably difficult to establish computationally, thus placing them on a shelf that not only few would look for, but also few could reach.
With this capacity to force the selective production of relatable private keys, given a public key generated according to said relationship, only a small audience would know to search for the related private key.
Ideally, the production of linked, discoverable public/private key pairs would be the default for the open public, and thus a deniable "accident" but with options to enable select, preferred chipsets (e.g. intel/amd brand only) to activate buses that will produce hardened, secure, unrelatable keys to those that have extra solder in all the right places.
Meanwhile, figure everything focuses on primes for integral quotients to prove clear relationships in most crypto problems, because it's easiest to reason correctness, so stacking tons and tons of layers on top of a desirable quotient will usually obscure such a fact from most snoops.
But, now we have new technology which binds massively parallel calculations (mostly by way of fast fourier transforms) to speed-of-light waveform oscillations. Such calculations that were not previously trivial, are reduced to, perhaps smallish functions with only the number of iterations to perform-and-test-output, before returning.
Determining whether the introduction of quantum computing is the only way such back doors could possibly be exposed to the general public, would be a necessity, prior to making advanced technology widely available.
If it does result in a high probability of exposure, then a narrative of controlled exposure also needs to be crafted, so that the old back doors can be retired in an orderly fashion, while ramping up new covert information vectors compatible with powerful quantum waveform calculations that put an exponentially larger amount of calculation cycles in the hands of civilians, which were previously unavailable with 20th century solid state electronics. Whether people have a clue how to use all those extra cycles or not.
Probably.
Imagine you have two random number generators, each producing a sequence of digits. The question for your computer is this: Are the two sequences completely independent from each other, or are they related in a hidden way? That, right there, should tell absolutely everyone, by intuition alone, that, despite assurances from industry experts that flaws leading to breaks ( plain-text discovery faster than brute force )…
I'm not 100% sure which side you are taking, but I think you are saying all common crypto is backdoored. That seems like a giant logical leap with absolutely no hints as to why you landed at that conclusion based on your quote.
are they related in a hidden way?
Probably.
P != quickly solvable by a classical computer. P means solvable in polynomial time relative to the size of the problem, which could still take longer than the universe has existed
>So instead, computer scientists measure something else that they hope will provide insight into the computation times they can’t measure: They work out the number of times a computer needs to consult an “oracle” in order to come back with an answer. An oracle is like a hint-giver. You don’t know how it comes up with its hints, but you do know they’re reliable.
This is not how it works, at all.