Authentication failed upgrading from 19.04 to 19.10

bentolor's answer led me to a different command which seemed to ultimately fix the problem:

sudo apt-get install --reinstall ubuntu-keyring

I'm guessing this restores the keyring to defaults, something must have changed since the package was last installed. Now I can run the command sudo do-release-upgrade -m desktop without the Authentication failed error.

I ran into the exact same problem. The problem is a missing signing gpg key 871920D1991BC93C. apt-key adv --keyserver http://keyserver.ubuntu.com:80 --recv-keys 871920D1991BC93C did not solve the issue as the key doesn't seem to publicy available.

But

$ sudo apt-key update
Warning: 'apt-key update' is deprecated and should not be used anymore!
gpg: key 3B4FE6ACC0B21F32: 3 signatures not checked due to missing keys
gpg: key 3B4FE6ACC0B21F32: public key "Ubuntu Archive Automatic Signing Key (2012) <[email protected]>" imported
gpg: key D94AA3F0EFE21092: 3 signatures not checked due to missing keys
gpg: key D94AA3F0EFE21092: public key "Ubuntu CD Image Automatic Signing Key (2012) <[email protected]>" imported
gpg: key 871920D1991BC93C: 1 signature not checked due to a missing key
gpg: key 871920D1991BC93C: "Ubuntu Archive Automatic Signing Key (2018) <[email protected]>" not changed
gpg: Total number processed: 3
gpg:               imported: 2
gpg:              unchanged: 1

helped. After that I was able to start the upgrade. This was a very long-term installation continuously updated.