[HN Gopher] Quantum Scientists Have Built a New Math of Cryptogr...
       ___________________________________________________________________
        
       Quantum Scientists Have Built a New Math of Cryptography
        
       Author : DocFeind
       Score  : 26 points
       Date   : 2025-07-25 15:25 UTC (7 hours ago)
        
 (HTM) web link (www.quantamagazine.org)
 (TXT) w3m dump (www.quantamagazine.org)
        
       | bawolff wrote:
       | 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
        
       | jasperry wrote:
       | 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
        
         | matthewdgreen wrote:
         | 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 wrote:
           | 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 wrote:
             | 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 wrote:
               | That's also what I heard about traditional one-way hash
               | functions and quantum. It's a theoretical result for
               | now...
        
         | noqc wrote:
         | >I expect better science writing from them.
         | 
         | based on what?
        
       ___________________________________________________________________
       (page generated 2025-07-25 23:01 UTC)