To prove that you have the private key, they should send you a challenge message and make you send back that message with a signature. If you can send any signed message, anyone who has ever received a signed message from a person can upload it and revoke that person's key.
