also that paper (IMO) is ridiculously conservative. Just using 1GB keys is plenty sufficient since it would require a quantum computer with a billion bits to decrypt.
How long does it take to generate a key that big? What probabilities do you need to put on generating a composite number and not a prime? Does the prime need extra properties?
Based on https://eprint.iacr.org/2017/351.pdf it would be about 1900 core hours (but I'm pretty sure optimized implementations could bring it down a bunch). No extra properties needed and moderate probability is sufficient.
About 8x just for key agreement and 40x for signatures. It's a lot. For key agreement it's worth it, and now about 1/3 of browsers in the wild use it. http://radar.cloudflare.com/adoption-and-u…
One third of all human traffic with Cloudflare is using a post-quantum KEM. I'd say that counts as enabled. We want that to be 100% of course. Chrome (and derivates) enabled PQ by default. https://radar.cloudflare.com/adoption-and-usage