4 ms·
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 consid
by Strilanc 4y ago
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. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2].
The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA".
How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them.
Is there somewhere where I can bet money that this doesn't amount to anything?
1: https://arxiv.org/abs/quant-ph/9508027 https://arxiv.org/abs/quant-ph/9508027
2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493 https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2...
3: https://arxiv.org/abs/2212.12372 https://arxiv.org/abs/2212.12372
- miga 4y agoIt is fair to say, that in security assessment you estimate lower bound on complexity of hacking. Schor proved upper bound.
- px43 4y agoThere are two cryptographers being discussed here. Peter Shor, and (Claus) Peter Schnorr. Neither are Schor.
- rezonant 4y agoShor, Schnorr, Schor and Schneier.
- coolspot 4y agoThey all are the same person - Satoshi.
- monktastic1 4y agoYou mean Schnatoshi?
- conjectureproof 4y agoLenny Baum, Lloyd Welch, and their colleagues at IDA were using the EM algorithm for code cracking well before they were able to prove anything about its convergence. 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.
- jackmott42 4y agoI think you are right that this paper may not amount to anything but it should also be a big wakeup call that maybe we need to switch or enhance our public key crypto starting now rather than later, in case similar ideas can work, or in case quantum computers get a little bit better faster than we thought, etc.
- HWR_14 4y agoThe difference is Shor is attempting to prove something. This article is by a security researcher who cares about staying ahead of threats. That is, a 10% chance that RSA-2048 was broken means he's screaming about changing to -4096 or another standard. Because he is trying to make security systems reliable. Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being true in what the paper is saying. In some other cases, "being right" means that the action you take is correct. Trying reading it as not a paper on "is RSA-2048 cracked" but "is RSA-2048 still safe".
- rezonant 4y agoIt sounds like you are talking about Schneier (the blog author and well known security researcher) and the parent post is talking about the paper Schneier is blogging about. And comparing it to another paper by a different author. I don't think there was a comparison between Schneier and Shor, or I missed it.
- HWR_14 4y agoI am talking about Schneier. I may have misread the parent post
- Strilanc 4y agoI agree that it makes sense for cryptographers to be jumpy around papers claiming improvements in quantum factoring, even if those papers are low quality and likely to be wrong. But that doesn't mean you stop calling the papers low quality and likely to be wrong. I guess I'd also be a lot more sympathetic if the paper had a paragraph in the abstract, or at least the intro and conclusion, where they explicitly positioned the paper as a wild idea that could work but probably won't but is still worth considering because of the risks.
- rubberband 4y agoLet 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.
- EGreg 4y agoJust deploy a smart contract on, say, Ethereum MainNet. One side will publish the public keys for RSA and the private key signature can take the money. The other side will likewise lock up some money, but that money can be moved by a smart contract method after a certain date, if the first account still has money in it. You can have multiple dates, for removing some or all of the money in the multiple bets against it. For example, "$200 that it's cracked by 2004". The main problem with bets and contests is that the side which knows the private key can simply withdraw the money itself. That’s why you need the private key to be generated by all parties involved in a ceremony.
- Strilanc 4y agoFor 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 https://www.nature.com/articles/s41586-021-03373-x
- 4y ago