You shouldn't need to cryptographically prove that an old username is unavailable. You should be able to simply send a request to Signal servers asking if it's available and receive "no" as a response.

You'd have to take their word that this wouldn't change, though.