Quantum Scientists Have Built a New Math of Cryptography | Hacker News Reader

Quantum Scientists Have Built a New Math of Cryptography

quantamagazine.org

39 pointsDocFeind11 comments

A pretty middling article from quanta--I expect better science writing from them. This one seems to be trying too hard to avoid being concrete, leaning into vague, unhelpful analogies. Still, I appreciate their work to publicize important theory results.

The research area is "Quantum One-Wayness" and here's the paper with the main result being discussed: https://arxiv.org/abs/2310.11526

The big question I'd want to answer here is: are we discussing symmetric encryption or public-key encryption, because they live in different worlds. I was sort of hoping that one of the experts would chime in with this.

Looking at the paper (for literally 30 seconds) I found a result stating that public-key encryption (in their model where secret keys are quantum and pubkeys/ciphertexts are classical) implies their one-way puzzles. That's good, because it implies that one-way puzzles are a necessary building block for public-key encryption. But it doesn't mean that one-way puzzles are sufficient to build public-key encryption. I was hoping to see the opposite implication, that one-way puzzles imply public-key encryption, but I didn't see that.

Maybe that's elsewhere in the paper, and isn't yielding to my sophisticated "search for one word" analysis.

ETA: I know as much quantum information theory as I do paragliding, so please chime in with knowledgeable thoughts here!

This is about the foundations of symmetric encryption. The authors are looking for constructions that give similar security guarantees to one-way functions if you live in the quantum world, and one-way functions are the theoretical foundation of symmetric cryptography.

Public-key encryption is based on trapdoor functions, which is a strictly stronger definition. So they wouldn't have got that far yet.

Well that sounds theoretically interesting, is there a practical application here? As far as i know traditional hash functions are just as safe in the quantum world as in the classical world (up to a sqrt for grover)

That's also what I heard about traditional one-way hash functions and quantum. It's a theoretical result for now...

Controversial opinion, but many in the quantum community actively contribute to and take advantage of this confusion.

Prime example: The whole idea of QKD (Quantum Key Distribution), if you listen to many talks they often motivate the talk using Shor's algorithm and the idea that a quantum computer would possibly break many classical encryption algorithms in the future (that's so far still largely a theoretical result). They then sell QKD as the solution because it's "quantum secure", but QKD is a key distribution mechanism for symmetric encryption (which can't be broken by quantum algorithms). Moreover it's really just a physical layer "sensing" solution, where you can transmit data (over a special link) and detect if someone has listened in on your transmission.

So they sell a solution to the public key encryption possibly being broken by quantum computers in the future, but their solution can not replace public key encryption, because it can only secure a link between two predetermined endpoints. It's an dishonest marketing ploy.

One of the primary uses of public-key encryption is key exchange at the beginning of a session that is subsequently encrypted using symmetric encryption. That's how every TLS session works, because public-key encryption is too slow for large amounts of data. Since QKD is a solution for key exchange, it can replace public-key algorithms in this respect.

The other main application of public-key encryption is digital signatures, which is vital for certificate checking and identity verification in general. At first glance, it seems QKD won't solve that, as you said, but I haven't looked into quantum research relating to signatures.

Quantum computing and cryptography research is important, but are some researchers taking advantage of hype to stay funded by letting people think practical applications are closer than they really are? Possibly. Nonetheless, the research is important.

>I expect better science writing from them.

based on what?

Based on the experience that Quanta consistently provides the highest-quality publications of science developments for the moderately-technical layperson?

I totally agree! It's the first article from quanta that made me afraid.ofnthe direction they're going. Scientific American kept drifting to looser and looser footing through bad analogies and not talking about the underlying mathematics in an effort to appeal to more people, the end result though was terrible.

This article was almost unreadable. Anyone with an interest in this is going to be familiar with ther term "matrix" and P vs NP. Most would likely have at least hear do BQP problems as well. What's the point ofndumbing it down any further than that. There comes a point where further distillation is to lossy, like an overly compressed jpeg that has lost any value as an image.

I found this kind of hard to follow (maybe reading the original paper would be better).

Did i understand right:

- they want to make a crypto system that that still works even if p=np

- they came up with a trapdoor function where the trapdoor is not in NP but is in BQP

Reply on news.ycombinator.com