producing GnuPG keys as proof of work

[Robert J. Hansen]

> It struck me that a GnuPG key, produced as proof of work, would be
> more generally useful than an arbitrary hash. But now I see that 
> challenge-based proof of work could just be used to authenticate a
> GnuPG key for signing and message encryption.

How?  What is there about the proof of work that can somehow
authenticate a GnuPG certificate?