Instead of asking the user to provide his public key, he could just provide his digital signature from the terms and have the public key extracted from it.
This requires some changes to the UI, I'm still not quite sure how to integrate it exactly.
(thanks, ninja_parade!)