The research area is "Quantum One-Wayness" and here's the paper with the main result being discussed: https://arxiv.org/abs/2310.11526
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!
Public-key encryption is based on trapdoor functions, which is a strictly stronger definition. So they wouldn't have got that far yet.
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.
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.
based on what?
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.
bawolff•6mo ago
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