NoKnowledge

This claims to be well-documented and secure by default, but I cannot find a link to the documentation (or is it just the README)? What actual algorithm is used for encryption and for signing?

The README has a major red flag:

From the math perspective, there is no difference between private and public keys, they both can be used to encrypt messages that only can de be decrypted by the other. Most of the security tools, including enc, artificially forbid using the public key for decrypting messages because that's not how it should be used (encrypting messages that anyone can decrypt is pointless).

Most security tools forbid that because it is dangerous! Also, this description sounds like textbook RSA is being used...

Oh absolutely, the theory behind QKD is fascinating! And I do think that some day there may be actually secure practical implementations, maybe even ones that are practical for more than a few niche applications.

But you mentioned the assumptions on the implementation, not on the underlying mathematics. The thing that concerns me is that QKD introduces additional hardware to operate, and there have been many demonstrations of weaknesses in that hardware that threaten the overall security of the system. With DIQKD you ensure that those issues no longer affect security (again it is absolutely remarkable that this is possible at all), but now you still have to concern yourself with all the implementation vulnerabilities that also plague classical cryptography. In that sense I mean that the implementation assumptions are now the same.

Yes, otherwise how would you know you are indeed communicating with that party?

Otherwise the standard Person-in-the-Middle attack would apply: Eve (claiming to be Bob) first runs a full protocol session (quantum + classical communication) with Alice, resulting in a shared key X. Then she does the same to Bob, resulting in a key Y. When Alice wants to encrypt a message to Bob, she encrypts with X. Eve can decrypt (and optionally re-encrypt with Y and forward the message to Bob).

Rather, device-independent quantum key distribution allows you to scale back the assumptions on your implementation to a well-motivated, minimal set. To me, this is already intriguing enough without the need for hyperbole!

Would it be accurate to say it is scaled back to the level achieved by classical (non-quantum) cryptography?

The article suggests that quantum key distribution (QKD) is a replacement for a courier, but that is not true. Distributing an initial small secret key (which allows authenticity of the post-processing of the quantum measurements) is still required.

Also I think the added value of device-independence is overstated. While it does indeed prevent loss of security by faulty quantum hardware (even if constructed maliciously), there is still a lot of classical post-processing required. That device still needs to be trusted. For example, when the device is outputting the shared key, it still needs to be trusted that it isn't also delivering that key back to Eve.

That's simply a logical fallacy: P => Q does not imply (not P) => (not Q). Here: "If it is inaccurate, then it is wrong" does not imply "If it is accurate, then it is right."

No configuration, curve or key-size would protect any of the asymmetric crypto mentioned in the book from quantum computing. You really have to switch to something mentioned in the post-quantum chapter.

This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of work on implementing those methods as fast as possible.

The blog post says the paper mentions 8.4e10 operations for factoring, but I can't find that number in the paper anywhere. The post then states: "The 800-bit claims would be 36 bits of work." I don't know what that means.

[edit]: the numbers are in the new version (https://eprint.iacr.org/2021/232). I was looking at the old version uploaded yesterday.

It's broken for me, thanks to the "responsive" design. When the browser window occupies half my screen (1920x1080px), the top-right menus (bell, plus, profile) get replaced with only a bell icon. How am I supposed to reach the settings page now?

That is apples to oranges, you're citing a lattice reduction algorithm? Maybe you meant the number field sieve https://en.wikipedia.org/wiki/General_number_field_sieve?

In that case the answer is: never. We've tried to generously interpret earlier factoring annealing results (there is nothing new in the top-posted paper) and had to conclude that the overall method just doesn't scale well: https://arxiv.org/abs/1902.01448

This study considers seven semi-primes (without justification why these seven) and reports an average(?) runtime of factoring each with D-Wave. No conclusions should be drawn on so few data-points. The proposed "Block Multiplication Table Method" will only affect the constants and thus has no effect on the asymptotics. The embedding from logical to physical qubits appears to have an exponential gap (but again, we shouldn't draw conclusions from so few data-points). However, if this is indeed true then even a polynomial runtime for annealing would still result in an exponential runtime for factoring. All in all, it eludes me why authors conclude that the obtained results are promising.

It's strange that the authors pick integer factorization as the problem to solve on their machine. Although their machine may provide a speedup for optimization problems, these speedups are not relevant for the problem of integer factorization, as shown in https://arxiv.org/abs/1902.01448 (disclaimer: I am a co-author of that paper).

Skimming over the paper it seems their method of translating factorization to the optimization problem consists of simplifying equations without justification that this can be done efficiently. I suspect that their preprocessing step is already NP-hard.

The second and more important issue, is that the overall strategy---of translating a problem with a sub-exponential classical complexity (via the Number Field Sieve) to an optimization problem with exponential runtime---is not expected to succeed, as confirmed by careful measurements in our paper.

The so called quantum key-exchange requires a shared secret, so it is actually doing key-expansion. Besides that it has practical problems in side-channel protection and cannot achieve a high enough bandwidth to be of interest in most practical settings.

When quantum computers break existing algorithms, we do not need to resort to quantum key exchange, but we can make the switch to post-quantum crypto, as also indicated by the other comment[0].

However, switching to the next generation of crypto only after the current generation is broken is not a solution. Much data needs to be kept secret for a long time. Internet traffic is currently being stored so that when the current crypto is broken all data can be decrypted retroactively.

[0] https://news.ycombinator.com/item?id=18327175

Hi Scott,

Do you think we will see a Quantum Winter (or even several), similar to how we've had several AI Winters?

We see tremendous amounts of funding in academia (and also industry) to build ambitious projects that still have significant issues to overcome (both theoretical and engineering) before being any close to being implemented. At the same time there (still) seems to be much misunderstanding, such as Vivek Wadhwa's recent post[0] or various reports about an unhackable internet based on quantum information. I am afraid that this may lead to people having unrealistic expectations on what can be built and how fast it can be built, with the consequence that we will see less and less funding and investments in the nearby future.

[0] https://www.scottaaronson.com/blog/?p=3645

They do that, with the extra step of allowing k-anonimity (https://www.troyhunt.com/were-baking-have-i-been-pwned-into-...)