How can we authenticate a public key with limited secure side channel?
PGP supports a so-called fingerprint of the public key, which really is a 20-byte hash expressed in hexadecimal as 10 groups of 4 characters. The recommendation is to read it over the phone. That's doable, but seldom done.

In the context, we only need second-preimage resistance, thus 20 bytes are a bit overkill. With a slow password hash (scrypt, argon2) we can safely get this down to 5 groups of 5 characters in a 25-character alphabet 0123456789CFGHJKMPRTVWXZ+, for $5\cdot5\log_2(25)&gt;116$ bit.
Note: that alphabet is likely to produce reasonably safe-to-spell-at-work codes, and is easily keyable if the software remaps Sto 5, Bto 8, ODQto 0, IJLto 1, UYto V, and so on)

With a challenge-response we can reduce this further. We can use a slow password hash using the (hash of) the public key as password and the challenge as salt.


please enter CK9Z 5H7C what do you get ?
got 01W8 RR4G


A substitution has probability $&lt;2^{-37.1}$ (one in 150 thousand millions) of going undetected, which is perfectly fine in practice.