121–130 of 161 posts
Who was the guy and what was the flawed and retracted paper mentioned in the below quote from Schneier's article? >In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.
I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work.…
EM worked in practice, so they spent a long time trying to prove convergence. Modern proofs are simpler.
Could be the case that this method also works in practice. I haven't the faintest idea whether it will.
> A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. If a quantum computer can break 2048-bit RSA, what about elliptic curves?
Elliptic curves are also vulnerable to Shor's algorithm. However, there are several new algorithms for asymmetric cryptography, such as Google's NewHope: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...
Earlier quoted context omitted.
Let me know if you find such a betting venue... I'll take the same side. I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.
For the Microsoft one I'm assuming you're referring to the retraction of the detection of Majoranas [1]. Do you have a reference for a Google quantum paper being retracted? I don't recall an instance of that (disclaimer: I am on the Google quantum team; my views do not represent them). 1: https://www.nature.com/articles/s41586-021-03373-x
Huge, if true. However, many such claims have surfaced before and turned out to be dudds. For now, I am taking it with a spoon of salt but with an interest of any follow-ups and peer review.
It also contains some links to critique of the Schnorr's algorithm paper. It looks like either much more p_n-smooth integer pairs are needed or the size of the p_n-smooth integers should be much bigger than estimated by original Schnorr's paper. Or both estimations are off.
As the paper discussed Schneier relies on the assumptions of the (classic) Schnorr's algorithm, it may also be off in the calculations as well.
Earlier quoted context omitted.
In the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetche…
Isn't the problem with one time pads distributing the pad? Like, you would have to walk to a bank and have them hand you a piece of paper... and tellers could read the paper before handing it to you. So basically so ineffective in practice as to be unusable?
And most banks still have brick-and-mortar stores where customers could come and identify themselves and collect their one time pad.
And a GByte of keypads would cover your banking need for a long time.
The problem is more that it works for some one-to-many relationsships such as banks, but not many-to-many relationships, such as emails, websites, etc. There have to be second or third parties.
On the hand, a lot of people seems to log in everywhere with Google Sign In or similar anyway.
And we could instead all have Google or Amazon devices with GBytes of one time pads. And that could be used to set up symmetric encryption, which should be more resistant to quantum computer attacks.
The only drawback is that we would have to trust the third party and everyone who could compromise the third party and every government that could put pressure on the third party :-)
You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap
1) If the paper is right, they are claiming they need 300ish physical qubits that can sustain about 1000 gates before decohering. No need for scalable error correction.
2) Independently of the veracity of the paper, if you actually need logical error corrected (and fault tolerant) qubits, you need error correcting codes with much more severe overhead than the 5-qubit code. The 5-qubit code is a pedagogical example, not something that would actually work under realistic conditions. And even the 5-qubit code needs quite a few extra ancillary qubits for fault tolerance (which is more expensive than simple error correction).
so just increase to 4096 or 8192 bits or beyond?
Why is this downvoted? Ain't it exponentially harder to break RSA using qubits each time you double the key length? Until we switch to quantum resistant algorithms, we can keep doubling the key length for some time no? 8192 bits should still be acceptable speed wise (if we consider that 2048 bits is broken, then I'll take slower operations over broken keys any day of the week).
Earlier quoted context omitted.
I would think most encryption at rest done using AES128/256, which is already quantum-resistant. It's mostly the key management which is at risk due to more heavily used RSA for asymmetric wrapping of keys.
AES-128 is effectively AES-64 when quantum computers exist which can run Grover's algorithm. That's not a huge exponent.