> Is there a technical way to implement a service like that in a non-compromising way? I.e. user sends you his public key, you brute-force some nonce value, unt

> Is there a technical way to implement a service like that in a non-compromising way? I.e. user sends you his public key, you brute-force some nonce value, until the key's ID is "nice"? No. That is not possible.