3 ms·

I think the scare of quantum computing was that it could solve an nP problem in polynomial time. Encryption uses "lock-in functions" that can be verified quickl

I think the scare of quantum computing was that it could solve an nP problem in polynomial time. Encryption uses "lock-in functions" that can be verified quickly, but not solved quickly. Prime factorization for RSA or finding the inverse function for EDDSA. Don't know where the idea first surfaced, but Grovers algorithm is an example where quantum computing can have an advantage compared to conventional machines: https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm If true, our lock-in functions for encrypted data might need to be revised because a quantum computer could solve them faster.

dontbenebby 4y ago
Thanks... I lack the math background to grok "ould solve an nP problem in polynomial time." without doing some refreshing, but I really appreciate you distilling that into one plain sentence. (I never took Calc, I'd get impatient because I skipped geometry and trig and a few other things before I went off to uni.) >If true, our lock-in functions for encrypted data might need to be revised because a quantum computer could solve them faster. Yikes, though it was my understanding symmetric ciphers (ex: AES) wouldn't be as impacted. I tried to find a cite, and all I found was an attack paper backing up the assertion previous attacks were mostly on asyymetric ciphers. (Not a cryptographer, so I often can just repeat the takeaways from what others explained in detail their reasoning on): > So far, in cryptography, the impact of quantum computing is analyzed mostly for asymmetric cryptography and less is known about its consequences on symmetric cryptography [0] https://www.sciencedirect.com/science/article/abs/pii/S0045790622003743 https://www.sciencedirect.com/science/article/abs/pii/S00457... I try to keep things offline, but it's hard to keep up with all these... heuristics :-)

dontbenebby 4y ago

Thanks... I lack the math background to grok "ould solve an nP problem in polynomial time." without doing some refreshing, but I really appreciate you distilling that into one plain sentence. (I never took Calc, I'd get impatient because I skipped geometry and trig and a few other things before I went off to uni.) >If true, our lock-in functions for encrypted data might need to be revised because a quantum computer could solve them faster. Yikes, though it was my understanding symmetric ciphers (ex: AES) wouldn't be as impacted. I tried to find a cite, and all I found was an attack paper backing up the assertion previous attacks were mostly on asyymetric ciphers. (Not a cryptographer, so I often can just repeat the takeaways from what others explained in detail their reasoning on): > So far, in cryptography, the impact of quantum computing is analyzed mostly for asymmetric cryptography and less is known about its consequences on symmetric cryptography [0] https://www.sciencedirect.com/science/article/abs/pii/S0045790622003743 https://www.sciencedirect.com/science/article/abs/pii/S00457... I try to keep things offline, but it's hard to keep up with all these... heuristics :-)