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!

▲

jasperry a day ago | parent | next [-]

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.

▲

bawolff a day ago | parent [-]

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)

	▲	jasperry a day ago \| parent [-]
		That's also what I heard about traditional one-way hash functions and quantum. It's a theoretical result for now...

▲

cycomanic 15 hours ago | parent | prev [-]

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.

	▲	jasperry 9 hours ago \| parent [-]
		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.