I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm
Cryptosystems based on discrete logarithms and factoring are vulnerable to Shor's algorithm.
These cryptosystems do not comprise the entirety of "public-key cryptography", because "public-key cryptography" includes digital signatures, not just public-key encryption and key agreement.
The following types of cryptosystems are not completely broken by quantum algorithms:
So "public key cryptography is totally broken by quantum computers" is too broad of a conclusion.
It is more accurate to say "The most common schemes such as RSA, DH, and ECC are broken again quantum computers, but there are more schemes in existence then just those three."
...while symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.
This is more or less accurate. There is some debate whether or not an actual doubling of key sizes is strictly necessary. And it should be noted that Grover's algorithm also influences hash functions.
Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it?
What does it do
Shor's algorithm uses a combination of a classical computation algorithm and the quantum fourier transform to factor numbers.
The problem of integer factorization is hard when the product to be factored consists of large prime numbers. A typical RSA modulus consists of two large prime numbers multiplied together $N = p * q$.
Shor's algorithm uses the quantum fourier transform to find how long it takes $f(x) = a^x \bmod N$ to cycle through all the possible outputs back to the beginning. So it looks for an $r$ such that $a^{x + r} \bmod N \equiv a^x \bmod N$, with the additional condition that $r$ is even so that $r/2$ can be obtained. The rest of the algorithm actually uses classical computation, finding the value of $r$ is the hard problem that the quantum algorithm solves. Finally, $gcd(a^{r/2} + 1, N)$ and $gcd(a^{r/2} - 1, N)$ are both nontrivial factors of $N$. (Where "nontrivial" means "not counting $1, N, -1, -N$", because those aren't helpful). The complete algorithm can be found in the wikipedia article about Shor's algorithm.
You can also use Shor's algorithm to compute discrete logarithms, which breaks Diffie-Hellman type cryptosystems. I don't understand the details of how to do so, so I will refrain from going into details.
How bad is it?
On a quantum computer, to factor an integer $N$, Shor's algorithm runs in polynomial time (the time taken is polynomial in $log\ N$, which is the size of the input)
It's bad. We really need the best attack to take exponential or at least sub-exponential time in order to have security with reasonable and practical sized values. A polynomial time algorithm for solving a problem basically makes that problem not useful for cryptography. Of course, you can technically try to use (much) larger parameters to make up for the difference... but that's not nearly as practical or graceful as we would like.
How exactly are symmetric key ciphers not susceptible to this?
The ability to find the period of a function is not necessarily useful for breaking a symmetric cipher. In order to do anything, you would need access to (at least) an encryption oracle. There is a paper about using Simon's algorithm to break symmetric modes of operation, but the attack model they use is pretty powerful: The adversary must prepare a superposition of all possible plaintext-ciphertext pairs, which is not trivial.
Basically, symmetric block ciphers and stream ciphers tend to use highly non-linear components which destroy any useful relations between inputs/outputs. Asymmetric designs tend to rely on such relations in order to achieve their goals. This means that asymmetric designs tend to incorporate more structure, and the structure can be exploited as a weakness.
How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible?
Because it has been proven that:
...any quantum solution to the problem needs to evaluate the function $Ω(\sqrt{N})$ times, so Grover's algorithm is asymptotically optimal.
What are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?
They are built on problems that are not known to be vulnerable to quantum algorithms. Using non-abelian groups seems to be helpful in regards to resisting quantum algorithms.
Note that "not known to be vulnerable" does not mean "It is proven that there cannot exist a quantum algorithm that solves the problem", it just means that there is no publicly known quantum algorithm for solving these types of problems.
