[Cryptography] Quantum computers and the Government

[Kristian Gjøsteen]

1. sep. 2021 kl. 21:12 skrev John Levine <johnl at iecc.com>:
> Some calculations are amenable to quantum methods, some aren't.


Just the usual standard comments:

* Any classical algorithm can in some sense be run on a quantum computer. You probably don’t want to, but that’s beside the point.
* Some specific problems have a very large quantum speedup. Examples include factoring and d.log. Unfortunately.
* There are very generic algorithms that provide «small» quantum speedup for many problems, for some values of «small» (perhaps surprisingly big values, depending on what value you expect «small» to have). Examples include breaking block ciphers. Which is why we have AES-256. I believe there are similar results for finding hash preimages etc.
* Some problems seem not to have a very large quantum speedup. Examples include many lattice-based problems, some isogeny-based problems, etc.
* There are many interesting results in this area. I am no expert.

As for reversible computations, anything you do with quantum computers must in some sense be reversible, apparently because of quantum physics, but that’s less of an obstacle to computation than you might think. In particular, there’s no problem computing SHA-x on a superposition, if you have a sufficiently large quantum computer.

-- 
Kristian Gjøsteen

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210906/b53d5031/attachment.htm>